Natural language and computation
85 flashcards · Mathematics · by Daniel Vente
How are regular expressions matched?
The first occurrence of a pattern and then the longest match
Define a regular language
A language that can be obtained by concatenation, union and Kleene closure by the languages consisting of the letters of the alphabet
When does a finite automata accept a string?
A string of input symbols is accepted (or: recognised) if we can go from initial state to some final state by reading all symbols left-to-right, following some appropriate sequence of transitions
What is an epsilon translation?
When is an FA deterministic?
name 7 operations that regular languages are closed under
union concatenation kleene closure intersection complementation set difference reversal
Define a rational transduction
they are similar to finite automata but the transitions are labeled with pairs of strings (input and output strings). They are used to translate between input and output (in either direction!)
Are rational transductions always functions from input to output? Clarify your answer by means of an example
No not always. Sequential transducers are (analogous to deterministic FAs)
What opperations are FST closed under?
inversion, concatenation, inversion and composition, but not intersection, difference and complementation.
Define the minimum edit distance
the minimum number of insertions deletions and substitutions to change one string to another
give an algorithm for computing the minimum edit distance
define a morpheme
The smallest unit of a language containing meaning
Name the possible morphemes
stems: core meaning-bearing units ("main" morpheme of the word, supplying the main meaning) affixes: bits and pieces that adhere to stems to change their meanings and grammatical functions (add "additional" meanings of various kinds). prefix suffix infix interfix (-o- in speedometer in English) circumfix (ge- -t in sagen -> gesagt in German)
Name 4 ways of combining morphemes
Inflection, combining stem with grammatical morpheme ( I walk) derivation (computer -> computerise) compounding (dog & house -> doghouse) clitisation
Define a clitic
A clitic is a morpheme that acts as a word but is typically reduced in form and is attached to another word (English: we've, French: l'opera) it sits somewhere between a word and an affix.
define a concatenative morphology
A morphology where words are build up of concatinated morphemes
define a template-morphology
a root-and-pattern morphology such as Hebrew, where words are not simply a stem plus some affixes. Rather, in these systems a word consists of several obligatory and optional affixes, where each obligatory affix has its own position in the string and optional affixes are slotted into this string, at the appropriate point in the sequence
use relative frequency estimation to give a formula for the probability of a trigram
What is the Markov assumption and what language model to they correspond to?
That the probability of a word only depends on the previous one. This corresponds to bi-grams, and hidden markov models
What is the difference between a type and a token?
types are the distinct words in the corpus tokens are all individual word occurrences (think set vs. list)
Define the perplexity and give a formula
Define Laplace/add-one smoothing
Define a hapax legomenon
an event which is observed only once
produce the formulas for Good-Turing smoothing
The basic insight of Good-Turing smoothing is to re-estimate the amount of probability mass to assign to N-grams with zero counts by looking at the number of N-grams that occurred one time.
Produce the formulas for Katz backoff
Produce the formula for the way HMMs will calculate the most likely POS tagging for a sentence
What probabilities does and HMM need to predict a sequence?
Emission and transition probabilities
Define transition probabilities in terms of relative frequency estimation
Define emission probabilities in terms of relative frequency estimation
What is a trellis?
A graph often used to illustrate the forward algorithm. It has an initial node, then a node for each symbol at each input position. Arcs between nodes are labelled by transition and emission probabilities
Explain what the forward, backward and Viterbi's algorithms are used for
Viterbi: Decoding an HMM. i.e. determining the most likely sequence of states given an observed sequence of symbols Forward and backward: Evaluation an HMM i.e. compute how likely a given sequence is using an HMM
define a phoneme
an abstract class of sounds that is perceived as one distinctive sound in a given language
define a word lattice
Word lattice is labelled, directed acyclic graph, with states roughly corresponding to points in time
define a constituent
sequence of words acting as a single unit within a hierarchical structure
when is a sentence considered grammatical
When it has at least one derivation according to a CFG
what is meant with agreement?
By agreement we mean that word forms in different parts of a constituent must correspond (in number, person, case, gender, etc.)
what is recognition?
Given grammar and input sentence, decide whether the input is correct
What is parsing?
Given grammar and input sentence, assign parse tree(s) (or some other kind of structure) to the sentence
When is a language in Chomsky normal form?
when all the right hand sides of the CFG consists of either one terminal or precisely two nonterminals
what are cross-serial dependencies? What do they say about a language?
they occur when the lines representing the dependency relations between two series of words cross over each other. languages containing an arbitrary number of them are non-context-free.
When is a grammar lexicalised?
all rules deal with actual words rather than human-invented categories
when is a PCFG proper?
If it holds that for each A it holds that ∑αP(A→α)=1\sum_\alpha \mathbb{P}(A \to \alpha) = 1∑αP(A→α)=1 i.e. the PCFG describes a probability distribution over all the rules for a particual string
When is a PCFG consistent?
if it holds that ∑wP(w)=1\sum_w \mathbb{P}(w) = 1∑wP(w)=1 i.e. the PCFG describes a probability distribution over the strings
describe feature-value pairs
The features are atomic symbols (they act as names of certain values) The values can be atomic, or feature structures themselves
what is typology?
The study of differences and similarities between languages
How is a language called where single words can express what we would think of as one sentence? Give an example of such a language
polysynthetic (inuit)
How is a language called where every word has only one morpheme? Give an example of such a language
Isolating, Chinese
How is a language called that had clean boundaries between morphemes? Give an example
Agglutinative (Finnish, Turkish)
How is a language called where one affix can function as several morphemes merged together?
Fusion
Give a taxonomy of languages acording to their word order and name an example for each
SVO (english, German) VSO (Arabic Hebrew) SOV (Japanese)
What are Neo-Davidsonian event semantics?
A way to quantify events in predicate logic in such a way that arbitrary information can be added by just adding predicates
what is β\betaβ -reduction?
The lambda-calculus equivalent of function evaluation
what is α\alphaα -conversion?
the lambda-calculus version of renaming variables
what is an interlingua?
A language independent meaning representaion
What is an inflection?
Combination of a stem + grammatical morpheme to create a word of the same class eg: cat -> cats (cat + s) (plural) Adam -> Adam's (Adam + 's) (possessive)
What is an derivation?
Combination of a stem with a morpheme to create a word of a different class. computation (n) -> computational (adj) fuzzy (adj) -> fuzziness (n) Not productive (ie: not universally applicable) and not very predictable.
what are morphotactics
A set of rules that explain which types of morphemes can follow which other types of morphemes, in a word (think of it as an ordering list). Can be modelled with a FSA. eg: in English, -s for plural follows a noun (ie: not preceding it).
what is a lexicon
A list of stems and affixes, with basic information about them (eg: if stem is verb stem/noun stem etc)
what are orthographic rules?
Spelling rules that indicate how spelling changes in a word, when two morphemes combine. city -> cities (city + -s)
what is tokenisation
It is the splitting of a corpus into sentence segments and those sentence segments in to word segments.
Compare morpheme segmentation with tokenisation
morpheme segmentation is where you separate the morphemes (stem + affix(es)) of a word while tokenisation is where you separate the words in a corpus.
Explain the maximum matching (maxmatch) algorithm for tokenisation
1) set pointer to beginning of string. 2) find the longest matching substring in the string (from the pointer to the end of the string), that exist in the dictionary. 3) advance the pointer to the location after this substring. 4) repeat 5) if no match is found, treat the current letter as a single character and increment the pointer
What problem can the maximum matching (maxmatch) algorithm encounter?
There may be unknown words in the dictionary, hence the algorithm may incorrectly skip letters.
in POS, what are closed class types?
they are a relatively fixed set of members. ie: prepositions
In POS, what are open class types?
They do not have a fixed set of members. ie: nouns, verbs etc
What is a noun?
a word that can take a determiner (the ship), take possessives (ship's crew) and (potentially) have a plural form (ships)
define proper nouns, common nouns , count nouns and mass nouns
proper nouns - names of people/entities common nouns - things that aren't proper nouns count nouns - common nouns that can be enumerated (pl/sg) mass nouns - common nouns that are homogeneous in their numbers (eg: snow, rain).
what is a verb?
a word that describes an action or a process.
what is an adjective?
a word that describes a property or quality.
describe the rule-based tagging process
First, assign tags to all words in the corpus with a dictionary Then, cut down these tags for the words based on a set of hand crafted rules, for each word.
Describe the transformation based tagging training process
assign most probable tags for each word, based on unigram model. find the rule that maximises the success metric apply said rule repeat 2 and 3 until a termination condition is met. These are your new trained rules
what are dependency grammars?
they are grammars which utilise semantic (eg: obj subj and some syntactic structure). They are free of word ordering, which makes them suitable for modelling languages with high cross dependencies.
The formula of N-gram probability approximation.
What are extrinsic and intrinsic evaluation?
Extrinsic evaluation Use the model in some application (e.g. speech recognition) and measure performance of that application Problem with extrinsic evaluation: difficult to do reliably, time consuming Intrinsic evaluation Look at performance of model in isolation, without concern for any larger application.
Can each CFG be transformed into CNF?
Yes, only need to eliminate epsilon rules eliminate unit rules we need to break up long rules
What's the difference and similarity between CYK and Earley's algorithm?
CKY realises a bottom-up parsing strategy, in combination with dynamic programming, only works with CNF. Earley’s algorithm combines dynamic programming with a top-down strategy. Both of them have cubic complexity.
Explain the basic idea of chunking
Dividing a sentence into a sequence of non-overlapping phrases, and tries to classify each words as one of I: inside a chunk O: outside a chunk B: beginning of a chunk
Projective and non-projective dependency structure
Projective: ‘project’ all nodes downwards, then we get all the words in the sentence in the exact order, without any edges crossing Non-projective: where edges can cross each other
What is the parent notation in grammar parsing and how does it help?
incorporate parent category in name of child category: e.g. it helps refine the grammar to reduce ambiguity.
How to evaluate parsers?
Take parsed corpus (e.g. Penn Treebank) Automatically parse sentences (without their ‘gold standard’ trees), and choose highest probability tree We could now count how often we get the correct tree relative to gold standard But this could be almost never for very long sentences So we prefer to measure accuracy of parsers with finer granularity
what is Reentrancy
Shared substructures, to save space
what is subsumption relation between
F subsumes G if F is ‘less specific’ than G
What is the advantage of sequential transducers over the non-sequential transducer?
Sequential transducers can be processed in time proportional to the number of symbols in the input. Unlike having to use search algorithm to for the non-deterministic states.
What is a garden path
It is the sentence that tricks human, i.e. sometimes you don’t understand a sentence correctly by reading it word by word from left to right. You may get the meaning after reading whole sentence. e.g. The complex houses married and single student. How human process language is by reading it word by word from left to right and try to get an understanding as reading it.