IN1140 · UiO

Studieguide for IN1140 Introduksjon til språkteknologi

Komplett pensumoversikt for introduksjon til språkteknologi ved UiO — med forklaringer, sentrale begreper, eksamenstips og vanlige fallgruver. Eksamensoptimalisert basert på tidligere eksamener.

Introduksjon

IN1140 Introduksjon til sprakteknologi er et tverrfaglig emne ved Institutt for informatikk, UiO, som kombinerer lingvistikk og informatikk. Kurset gir en bred innforing i hvordan datamaskiner kan analysere, forsta og generere menneskelig sprak -- fra grunnleggende tekstbehandling med regulaere uttrykk til maskinlaering med Naive Bayes-klassifisering.

To gjennomgaaende rammer er nyttige aa ha i bakhodet. (1) Lingvistiske analysenivaer: fonetikk/fonologi (lyder), morfologi (ordstruktur), syntaks (setningsstruktur), semantikk (betydning) og pragmatikk (betydning i kontekst) -- temaene i kurset foelger i stor grad disse nivaaene, og et eget teori-spoersmaal kan be deg liste nivaaene og kort beskrive fokuset for hvert. (2) Metodologiske paradigmer: regelbaserte metoder (manuelt definerte regler/kunnskap fra en ekspert) vs. empiriske/statistiske metoder (en modell laeres automatisk fra et annotert treningskorpus med maskinlaering). Mange oppgaver -- f.eks. om ordklassetagging -- ber deg sammenligne disse to tilnaermingene.

Eksamen folger et fast monster med 7-13 oppgaver fordelt pa sju hovedtemaer: regulaere uttrykk, morfologi og ordklasser, sprakmodeller (n-gram), syntaks og grammatikk, semantikk (leksikalske relasjoner og semantiske roller), klassifisering (Naive Bayes), og sprakteknologiske anvendelser (NER, koreferanse). Typisk vekting: regulaere uttrykk (10-15%), ordklasser og morfologi (10-15%), sprakmodeller (10-15%), syntaks og grammatikk (15-25%), semantikk (10-15%), Naive Bayes og maskinlaering (15-20%), og NER/anvendelser (5-10%).

Viktig: Eksamen tester bade teoretisk forstaelse (definisjoner, begreper) og praktisk ferdighet (skrive regex, tegne treer, regne Naive Bayes). Oev pa regneoppgaver og regex-skriving -- det er ikke nok a bare lese teorien. Eksamenene gjennom flere ar har testet noyaktig de samme kjerneemnene, bare med ulike eksempler og ordlyd: regex-skriving, ordklassetagging, n-gram-telling og bigram-utregning, frasestrukturtraer og rekursjon, leksikalske relasjoner og semantiske roller, og en fullstendig Naive Bayes-klassifisering. Lar du deg ikke lure av at eksempelordene endrer seg fra ar til ar -- selve oppgavetypene gar igjen nesten identisk.

Regulaere uttrykk

Regulaere uttrykk (regex) er monstre som brukes til a soeke etter, matche og trekke ut tekst. Et sentralt verktoy i all tekstbehandling og sprakteknologi.

Oversikt

Regulaere uttrykk (regex) er et formelt sprak for a beskrive monstre i tekst. De brukes i nesten alle sprakteknologiske systemer -- fra tokenisering og informasjonsekstraksjon til datavalidering. I IN1140 er regex en av de mest praktiske ferdighetene du testes i, og oppgavene krever at du kan skrive presise uttrykk som matcher akkurat det som spesifiseres.

Grunnleggende byggeklosser

De viktigste operatorene i regex er: tegnklasser [abc] matcher ett av tegnene a, b eller c; [0-9] matcher et siffer; [a-zA-Z] matcher en bokstav. Disjunksjon a|b matcher enten a eller b -- merk at disjunksjon har lav presedens, sa ab|cd|efg matcher hele strengen "ab", "cd" eller "efg" (ikke bare enkeltbokstaver). Kvantitatorer: ? (0 eller 1), * (0 eller flere), + (1 eller flere), {n} (noyaktig n), {n,m} (mellom n og m). Grupperinger med parenteser () styrer presedens og fanger grupper.

Spesialtegn og escaping

Punktum . matcher et vilkarlig tegn. Backslash \ brukes for a escape spesialtegn, f.eks. \. for a matche et faktisk punktum. Forkortelser: \d = [0-9], \s = mellomrom/tab/newline, \w = ordtegn [a-zA-Z0-9_]. Ankere: ^ = starten av linjen, $</code> = slutten av linjen.</p><h3>Parenteser og grupperinger</h3><p>Parenteser har to funksjoner: de <strong>grupperer</strong> uttrykk for a styre presedens (f.eks. <code>(ab)+</code> matcher "ab", "abab", osv.), og de <strong>fanger</strong> delstrenger for bruk videre. Pa H2022-eksamen ble du spurt om parenteser i uttrykket <code>(0?[1-9]|1[012])-(31|[123]0|[012]?[1-9])</code> kunne fjernes -- svaret avhenger av om parentesene er nodvendige for a skille alternativene innenfor disjunksjonen fra resten av uttrykket.</p><h3>Praktiske eksamensoppgaver</h3><p>Regex er testet pa <em>alle</em> eksamener, og oppgaven kommer alltid forst. To hovedtyper gar igjen: (1) <strong>Skriv et regex selv</strong> som matcher en spesifikasjon -- f.eks. datoformat, pris, klokkeslett og billettype i ett soekeresultat, eller en flerlinje-postadresse med flere gyldige varianter. (2) <strong>Analyser et gitt regex</strong> -- avgjor hvilken streng som <em>ikke</em> matches, om en parentes kan fjernes, eller om en pastand om uttrykket er sann/usann. En klassisk "skriv selv"-variant er a lage ett uttrykk som gjenkjenner flere boyningsformer av en ordliste (infinitiv, presens, preteritum, imperativ) ved hjelp av en felles stamme og en disjunksjon av endelser, eller a gjenkjenne en klasse forkortelser bygd opp paa samme mate (bokstav(er) etterfulgt av punktum, evt. gjentatt). Nokkelen er alltid a bryte ned kravene i delproblemer og bygge uttrykket steg for steg.</p><h3>Regulaere uttrykk og endelige tilstandsmaskiner</h3><p>Regulaere uttrykk svarer formelt til <strong>endelige tilstandsmaskiner</strong> (finite-state automata): et sett tilstander med transisjoner pa input-symboler, en starttilstand og en eller flere aksepttilstander. En maskin er <strong>deterministisk</strong> (DFA) hvis hver kombinasjon av tilstand og symbol har noyaktig en transisjon -- ellers er den ikke-deterministisk (NFA), f.eks. hvis samme symbol fra en tilstand kan fore til flere tilstander, eller hvis det finnes tomme (epsilon-)transisjoner. Du kan bli bedt om a sette opp en <strong>transisjonstabell</strong> (rader = tilstander, kolonner = symboler, celler = neste tilstand) og begrunne om maskinen er deterministisk.</p><div class="eksempel-boks"><h4>Eksempel 1: Matche norske datoer (H2022-stil)</h4><p>Krav: Match datoer som 5.6.2014, 05.06.2014, 5.6.14, 05.06.14 (dag.maned.ar).</p><pre><code>/([012]?[1-9]|[123]0|31)\.(0?[1-9]|1[012])\.\d\d(\d\d)?/</code></pre><p>Forklaring: Dagen matcher 1-31 (med valgfri ledende null), etterfulgt av punktum, maned 1-12, punktum, og to eller fire sifre for aret.</p></div><div class="eksempel-boks"><h4>Eksempel 2: Matche telefonnumre (H2021-stil)</h4><p>Gitt: <code>((\ +47|0047)\s)?([0-9][0-9]\s){3}([0-9][0-9]){1}</code></p><p>Sporsmalet var om uttrykket <em>kun</em> gjenkjenner numre som <em>begynner med</em> +47/0047, eller om det ogsaa matcher numre <em>uten</em> landskode. Svaret: Gruppen med landskode er valgfri (markert med <code>?</code>), sa uttrykket matcher bade med og uten landskode. Paastand 1 ("kun med landskode") er altsaa usann.</p></div><div class="eksempel-boks"><h4>Eksempel 3: Ett regex for flere boyningsformer (skriv-selv-stil)</h4><p>Oppgave: Skriv ett regulaert uttrykk som gjenkjenner infinitiv, presens, preteritum og imperativ av verbene <em>danse</em>, <em>hoppe</em> og <em>rope</em>.</p><p>Strategi: Samle stammene i en disjunksjon, og legg endelsene utenpaa. Imperativ = stammen alene, infinitiv = stamme + e, presens = stamme + er, preteritum = stamme + et/te. Et mulig uttrykk:</p><pre><code>/(dans|hopp|rop)(e|er|et)?/</code></pre><p>Her er stammen <code>(dans|hopp|rop)</code> felles, og <code>(e|er|et)?</code> dekker de boyde formene mens den valgfrie <code>?</code> tillater imperativen (bar stamme). Legg gjerne til ankere <code>^...$ hvis uttrykket skal matche hele ordet og ikke bare en delstreng. Poenget sensor ser etter er at du faktorerer ut det felles og bruker disjunksjon + valgfrie grupper -- ikke at du lister hver form for seg.

Nøkkelformler

•[abc] -- tegnklasse, matcher ett av tegnene a, b, c
•[0-9] eller \d -- matcher et siffer
•a|b -- disjunksjon, matcher a ELLER b (lav presedens!)
•? = 0/1, * = 0+, + = 1+, {n} = noyaktig n, {n,m} = n til m
•() -- gruppering (styrer presedens) og fangst
•\. -- escaped punktum (matcher bokstavelig punktum)
•\s -- mellomrom, tab, newline

Vanlige feil

⚠️Glemme at disjunksjon (|) har lav presedens. /ab|cd/ matcher 'ab' eller 'cd', IKKE 'a(b|c)d'. Bruk parenteser for aa avgrense.
⚠️Forveksle ? (0 eller 1) med * (0 eller flere). Bruk ? naar noe er valgfritt men maks ett.
⚠️Glemme aa escape punktum. Uescapet . matcher ALLE tegn, ikke bare et faktisk punktum.
⚠️Bygge for brede uttrykk som matcher for mye. Vaer sa spesifikk som mulig med tegnklasser.

Eksamenstips

💡Bryt ned komplekse regex-oppgaver i delproblemer. Skriv regex for dag, maned, ar, pris osv. separat, og sett dem sammen.
💡Test regex-et ditt mentalt mot eksemplene i oppgaveteksten -- bade de som SKAL og de som IKKE SKAL matche.
💡Regex-oppgaven er typisk verdt 10-15% og kommer alltid forst. Den er tidkrevende -- bruk ca. 30 minutter.
💡To oppgavetyper gar igjen: skriv et regex selv (datoer, adresser, billetter, boyningsformer, forkortelser) OG analyser et gitt regex (hvilken streng matcher ikke, kan en parentes fjernes, er pastanden sann). Oev pa begge.
💡Husk koblingen til endelige tilstandsmaskiner: du kan bli bedt om en transisjonstabell og a begrunne om maskinen er deterministisk (DFA) eller ikke (flere transisjoner pa samme symbol = ikke-deterministisk).

Laster...

Introduksjon