Exploring algorithmic reasoning and memorization in transformers : challenges and insights
department or school: Applied Science, Faculty of
department or school: Electrical and Computer Engineering, Department of
data provider: DSpace
degree campus: UBCV
creator: Mahdavi, Seyed Mohammad Sadegh
issued: 2023-08-23T15:34:56Z
issued: 2023
related degree: Master of Applied Science - MASc
degree grantor: University of British Columbia
description: In this thesis, we investigate the ability of neural networks, particularly Transformers, to reason and memorize. First, we focus on graph neural networks and Transformers, and analyze their performance on algorithmic reasoning tasks. We show that while models can achieve high accuracy on data from the same distribution as their training data, their performance drops significantly when faced with new, out-of-distribution data. We further show that even high performance on benchmark numbers may be misleading and true reasoning capability of these models remains limited. We identify several challenges involved in achieving true reasoning abilities and generalization to new data. We propose solutions to some of these challenges, including fixing input representation issues, hybrid models, and enlarging the training dataset. We also examine the expressivity of Transformers, providing a theoretical analysis of their ability to memorize data points. The results show a linear relationship between a Transformer's memory capacity and both the number of its attention heads as well as the input's context size.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/85578
note: Exploring Algorithmic Reasoning and Memorization inTransformers: Challenges and InsightsbySeyed Mohammad Sadegh MahdaviB.Sc. Computer Engineering, Sharif University of Technology, 2021A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of Applied ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Electrical and Computer Engineering)The University of British Columbia(Vancouver)August 2023© Seyed Mohammad Sadegh Mahdavi, 2023The following individuals certify that they have read, and recommend to the Facultyof Graduate and Postdoctoral Studies for acceptance, the thesis entitled:Exploring Algorithmic Reasoning and Memorization in Transformers:Challenges and Insightssubmitted by Seyed Mohammad Sadegh Mahdavi in partial fulfillment of therequirements for the degree of Master of Applied Science in Electrical andComputer Engineering.Examining Committee:Renjie Liao, Assistant Professor, Electrical and Computer Engineering, UBCCo-SupervisorChristos Thrampoulidis, Assistant Professor, Electrical and Computer Engineering,UBCCo-SupervisorPurang Abolmaesumi, Professor, Electrical and Computer Engineering, UBCSupervisory Committee MemberNick Harvey, Professor, Computer Science, UBCSupervisory Committee MemberiiAbstractIn this thesis, we investigate the ability of neural networks, particularly Transformers,to reason and memorize. First, we focus on graph neural networks and Transformers,and analyze their performance on algorithmic reasoning tasks. We show that whilemodels can achieve high accuracy on data from the same distribution as theirtraining data, their performance drops significantly when faced with new, out-of-distribution data. We further show that even high performance on benchmarknumbers may be misleading and true reasoning capability of these models remainslimited. We identify several challenges involved in achieving true reasoning abilitiesand generalization to new data. We propose solutions to some of these challenges,includin…
has type: Thesis/Dissertation
date issued: 2023-11
is shown at: 10.14288/1.0435551
language: eng
degree discipline: Electrical and Computer Engineering
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
contributor: Liao, Renjie
contributor: Thrampoulidis, Christos
type: Text
identifier URI: http://hdl.handle.net/2429/85578