Lecture

• homeworks
• attendance to practicals is mandatory, 3 absences allowed at maximum
• final test

$A\subseteq\Omega$

• we divide the number of $A$ occurring by the number of experiments
• maximum likelihood estimation

• $p(A)\in[0,1]$
• $p(\Omega)=1$
• $p(\bigcup A_i)=\sum p(A_i)$

nothing can be more uncertain than the uniform distribution

$G(p)=2^{H(p)}$

$H(X,Y)=H(Y\mid X)+H(X)$

entropy … the least average number of bits needed to encode a message

• $I(X,Y)=D(p(x,y)\Vert p(x)p(y))$
• we can derive that $I(X,Y)=H(X)-H(X\mid Y)$
  • by symmetry $I(X,Y)=H(Y)-H(Y\mid X)$

• original input $A$ = the message in someone's mind
• noised output $B$ = the written/spoken representation

• $p(A\mid B)=p(B\mid A)\cdot\frac{p(A)}{p(B)}$
• $A^*=\text{argmax}_A\;p(B\mid A)\cdot p(A)$
  • $p(B\mid A)$ … acoustic model
  • $p(A)$ … language model

• we need to model the probabilities of sequences of words
• we will use n-gram probabilities so that we don't need many parameters
  • $p(w_i\mid w_{i-1},w_{i-2})=\frac{c(w_{i-2},w_{i-1},w_i)}{c(w_{i-2},w_{i-1})}$
• number of parameters
  • uniform … 1
  • unigram … $|V|-1$
  • bigram … $\sim|V|^2$
  • trigram … $\sim|V|^3$
    • for $|V|\approx 60k$, it is larger than the number of parameters of the Llama model

• we can add 1 to all of the counts
  • ADD-1 smoothing
  • $p(w\mid h)=\frac{c(w,h)+1}{c(h)+|V|}$
  • what if there is an word that we did not see in the training set? we will have a special word for that <unk>
• we can add $\lambda$ to all of the counts
  • ADD-$\lambda$
  • $p(w\mid h)=\frac{c(w,h)+\lambda}{c(h)+\lambda\cdot |V|}$
  • how to estimate $\lambda$
  • we want to minimize the cross-entropy
  • we cannot use training (nor test) data for that, we need holdout (dev) data
  • $p(w_i\mid w_{i-2},w_{i-1})=\lambda_0\cdot p_0+\lambda_1 \cdot p_1(w_i)+\lambda_2\cdot p_2(w_i\mid w_{i-1})+\lambda_3\cdot p_3(w_i\mid w_{i-1},w_{i-2})$
    • $\sum\lambda_i=1$
  • expectation maximization (EM) algorithm
    • expectation: $c(\lambda_j)=\sum\lambda _jp_j(w\mid h)/p'(w\mid h)$
    • maximization: $\lambda_j=\frac{c(\lambda_j)}{\sum c(\lambda_h)}$

• language identification using char-level language model
• at least 2 languages

POS tags

• English: Penn Treebank (45 tags), Brown Corpus (87), Claws c5 (62), London-Lund (197)
• Czech: Prague Dependency Treebank (4294; positional), Multext-East (1485; Orwell 1984 parallel corpus), Prague Spoken Corpus (over 10000)
• Universal Dependencies: 17 universal POS tags, 27 universal features (each with 1–37 possible values)

• positions: part of speech, subpos, gender, number, case, poss gender, poss number, person, tense, degree, polarity, voice, (reserved), (reserved), style
• gender ambiguities → more values of the position

• prepositions and subordinate conjunctions have the same tag (hard to distinguish)
• “to” has its own tag (it denotes and infinitive or works as a preposition, not easy to distinguish)

noun, proper noun, verb, adjective, adverb, interjection, pronoun, determiner, auxiliary, numeral, adposition, subordinating conjunction, coordinating conjunction, particle, punctuation, symbol, unknown

• adjectives are missing
  • they are a relatively new invention from France
  • in French, adjectives behave quite differently than nouns

• English: noun, verb, adjective, adverb, pronoun, preposition, conjunction, interjection
• Czech: noun, adjective, pronoun, numeral, verb, adverb, preposition, conjunction, particle, interjection

• open classes (take new words)
  • verbs (non-auxiliary), nouns, adjectives, adjectival adverbs, interjections
  • word formation (derivation) across classes
• closed classes (words can be enumerated)
  • pronouns/determiners, adpositions, conjunctions particles
  • pronominal adverbs
  • auxiliary and modal verbs/particles
  • numerals
  • typically thay are not base for derivation
• even closed classes evolve but over longer period of time

• input: word form (token)
• output
  • set of analyses (possibly empty)
  • an analysis
    • lemma (base form of the lexeme)
    • tag (morphological, POS)
      • POS
      • features and their values

• tagging … context-based disambiguation
• most taggers employ ML methods
• taggers may or may not work on top of morphological analysis

• finite-state automaton/machine
• example: FSA checking correct spelling of Czech dě, tě, ně

• composed of multiple sublexicons (prefixes, stems, suffixes)
• notes (glosses) at the end of every sublexicon
  • e.g. POS tags
• lexicon is a DAG, not a tree

• two-level mophology solves that
  • upper (lexical) language
  • lower (surface) language
• two-level rules
  • lexical: baby+0s
  • surface: babi0es
• zero is treated as a normal symbol (but corresponds to an empty string)

• transudcer is a special case of automaton
• checking (finite-state automaton)
  • does the word belong to the language (lexicon)?
• analysis (finite-state transducer)
  • surface string → lexical string
• generation (finite-state transducer)
  • lexical string → surface string

• a:b <=> l:l _ r:r
• lexical a must be realized as surface b in this context and only in this context
  • context … between l and r
• FST can be constructed from that
• disadvantage: capturing of long-distance dependencies is clumsy
  • example of long-distance dependencies – Czech adjectives (superlatives in particular)
  • nej- prefix is legal only if there is -ší suffix

• dependency tree – we need only „pointers“ to parent elements and labels of the connections
• ways of annotation differ (e.g. Prague Dependency Treebank vs. Universal Dependencies)

• relations between sentence parts
• sentence part = token (word, number, punctuation)
• we do not restore elided constituents at this level
• different shapes in different theories, hierarchical structure (tree)
  • phrasal (constituent) tree, parse tree
  • dependency tree
• constituent vs. dependencies
  • there exist multiple constituent tree for one dependency tree
  • in dependency tree, the phrases have “heads” (parent nodes of the words of the phrases)
• phrases
  • phrase replaceability – a phrase can be replaced by a different phrase of the same type
  • different POS phrases
  • propositional phrase attachment ambiguity
  • verb phrase × clause
  • coordination
  • ellipsis

• transition-based Malt parser
  • complete for projective trees
    • there are extensions that can produce non-projective trees
  • transitions
    • Shift – move word from buffer to stack
    • Larc – connect two topmost stack words, higher is parent (remove child from stack)
    • Rarc – connect two topmost stack words, lower is parent (remove child from stack)

• queries are boolean expressions
• search engine returns documents that satisfy the expression
• term-document incidence matrix
• for bigger collections, the incidence matrix would be very sparse
  • we will use a different way of storage
  • inverted index
    • for each term in a dictionary, we store a list of all documents that contain the term (postings list)
• the tokens are usually normalized (lemmatized?), also we sort the whole list of (token, document) pairs
• we want to have the dictionary in the memory, the postings can be stored on the disk
• data structures for looking up term – hashes and trees
  • is there a fixed number of terms or will it be growing?
  • what are the frequencies with which various keys will be accessed?
  • how many terms are we likely to have?
• hashing tables
  • term → integer, try to avoid collisions
  • fast lookup time
  • no way to find minor variants, no prefix search
  • might need to be rehashed
• trees
  • prefix can be searched
  • slightly slower search
  • need to be rebalanced
  • …
  • binary tree
  • B-tree
• simple conjunctive query (two terms)
  • we need to find the intersection of two postings
  • that is linear if the postings are sorted
• boolean queries
  • use and, or, not
  • each document is considered to be a set of terms

• format, language, character set
• normalization, tokenization
• hyphens and compound words are problematic
  • accents and umlauts too
• capital letters
• stop words – extremely common words
  • older IR systems usually ignored them
  • you need stop words for phrase queries like “King of Denmark”
• more equivalence classing
  • phonetic equivalence (Soundex)
  • semantic equivalence (thesauri)
• lemmatization – we reduce the word to its proper dictionary headword form
  • inflectional
  • derivational
• stemming
  • uses heuristics to chop off the end of the word
  • Porter stemmer
    • conventions + 5 phases of reductions applied sequentially
    • each phase consists of a set of commands
    • sample command – delete final ement if what remains is longer than 1 character (replacement → replac)
  • stemming is usually good enough (we don't need lemmatization)

• most users are not capable (or don't want) to write boolean queries
• we usually get either too few or too many results

$w_{t,d}=(1+\log\text{tf}_{t,d})\cdot\log\frac N{\text{df}_t}$

• distance does not work well – longer documents are far from the shorter ones
• we will use angle (cosine similarity)
• cosine similarity for normalized vectors is just the dot product

• precision, recall, F-score
• accuracy is usually not helpful in information retrieval as $TP\ll TN$
• precision and recall are computed for unranked sets
  • we can compute it for top $n$ results (for different values of $n$)

• words are not vectors of continuous numbers :((
• one-hot encoding
• prediction of next word
• result has interesting properties, similar words have similar weight vectors

• RNN = information pipeline
• CNN = information in tree-like data structure (used in speech-recognition)
• self-attentive = Transformers = information flow in a weighted complete bipartite graph

• originally for machine translation
• attention weights = similarity matrix between all pairs of states
• the $\sqrt{d}$ helps the numerical stability
• feed-forward layer

• for each word, we predict the following one
• we need to modify the attention not to attend the right context
• otherwise, it could look in the future and predict the word

• precision: n-gram counting
• recall: brevity penalty

• the morphology is in the dictionary – there are the exact forms of the words
• there are both longer and shorter units in the dictionary