Quantifiers and Complexity: The distinct neural signatures of verification algorithms for natural language quantifiers.

Abstract

Sammendrag

Denne avhandlinga utforsker hvordan komputasjonell kompleksitet påvirker hvordan kvantorer i naturlig språk verifiseres. Mer spesifikt handler den om de nevrale konsekvensene av såkalt minimal kompleksitet: den enklest mulige algoritmen for å beregne en funksjon. Det kan bevises matematisk at kvantorer i naturlig språk kan deles inn i klasser avhengig av den minimale kompleksiteten til algoritmen for å avgjøre om ei setning med en gitt kvantor er sann. Blant disse klassene er det bare proporsjonale kvantorer – slik som ‘de fleste’ – som beviselig behøver en algoritme med en form for minne. Siden de matematiske bevisene garanterer minimal kompleksitet – det er ingen strategier som kan forenkle oppgaven – forventer vi at hjernesystemer forbundet med minne skal være aktive når proporsjonale kvantorer, men ikke andre kvantorer som ‘alle’, ‘tre av’ osv., verifiseres.

I tre EEG-eksperimenter der deltakerne måtte bedømme om setninger med kvantorer var sanne om et bilde, undersøkte vi om setningsprosessering hos mennesker er underlagt disse komputasjonelle prinsippene. Eksperimentene demonstrerer at de ulike algoritmene som kvantorer må verifiseres med, reflekteres i distinkte svingninger i hjernepotensialet; dersom setninga inneholdt en proporsjonal kvantor, kunne vi påvise kvalitative og kvantitative forskjeller relativt til andre typer kvantorer. Disse forskjellene har i tidligere studier blitt forbundet med bruk av minneressurser.

Resultatene indikerer at setningsprosessering hos mennesker er underlagt de samme kravene som hos abstrakte datamaskiner. Avhandlinga diskuterer konsekvensene av disse funnene og argumenterer for at bruken av analysemetoder fra informatikk kan bidra til teoretisk velbegrunnede og empirisk testbare hypoteser om hvilken type algoritmer hjernen benytter seg av.

Abstract

This thesis concerns the impact of computational complexity on the verification of natural language quantifiers. In particular, it deals with the neural consequences of so-called minimal complexity: the simplest possible algorithm to compute a function. It can be shown mathematically that quantifiers in natural language divide into classes depending on the minimal complexity of determining the truth value of a quantified sentence with that quantifier. Among these classes, only proportional quantifiers – like ‘most’ – demonstrably require an algorithm with a memory component. Since the formal proofs delineate a lower bound on the complexity of the verification algorithm – there is no strategy that can simplify the nature of the task – this leads to the prediction that proportional quantifiers, but not other quantifiers like ‘all’, ‘three’, etc., should recruit memory systems during verification, also in human subjects.

In three EEG experiments with a picture-sentence verification paradigm, the cognitive reality of this distinction in complexity is investigated. The experiments demonstrate that the computational complexity of the verification algorithm for natural language quantifiers is reflected in distinct neural responses: proportional quantifiers led to specific effects in the event-related potential (ERP), compared to the other classes, at different positions in a sentence in which verification occurs. Previous research has linked these effects to the recruitment of memory resources.

This compelling evidence suggests that human language processing is subjected to the same constraints as those applicable to abstract machines. On the basis of these results, the thesis goes on to explore open questions at the intersection of computer science and psycholinguistics and argues that formal proofs about the complexity of specific computational problems can inform us about which class of algorithms is plausibly implemented by the brain.