CS-498 Signals AI•Themes•Much of AI occurs at the signal level•Processing data and making inferences rather than logical reasoning•Areas such as vision, speech, NLP, robotics•methods bleed into other areas (graphics, animation, ...)•Linked by the use of statistical tools and ideas from machine learning•Much domain knowledge is required to make progress in areas•However, they do share toolsActivities•Mainly lecture•but I will require that groups present research papers•Evaluation•4 projects, which will have a competitive component•build a part-of-speech tagger•build a face finder•build a word spotter•build a styleIK (we’ll talk about what this means)•Final project•by choice•ParticipationNatural Language - Applications•Machine Translation•e.g. South Africa’s official languages: English, Afrikaans, the Nguni languages, isiZulu, isiXhosa, isiNdebele, and Siswati, and the Sotho languages, which include Setswana, Sesotho and Sesotho sa Leboa. The remaining two languages are Tshivenda and Xitsonga.•български (Bălgarski) - BG - Bulgarian; Čeština - CS - Czech; Dansk - DA - Danish; Deutsch - DE - German; Eesti - ET - Estonian; Elinika - EL - Greek; English - EN; Español$- ES - Spanish; Français - FR - French; Gaeilge - GA - Irish; Italiano - IT - Italian; Latviesu valoda - LV - Latvian; Lietuviu kalba - LT - Lithuanian; Magyar - HU - Hungarian; Malti - MT - Maltese; Nederlands - NL - Dutch; Polski - PL - Polish; Português - PT - Portuguese; Română - RO - Romanian; Slovenčina - SK - Slovak; Slovenščina - SL - Slovene; Suomi - FI - Finnish; Svenska - SV - SwedishMore NLP applications•Question answering•Information extraction•Text summarisation•Information retrieval•Improved understanding of language, linguisticsWhy is NLP hard?•Meaning is a complex phenomenon•Sentences are often radically ambiguousTime flies like an arrowFruit flies like a bananaIs this grammatical?•John I believe Sally said Bill believed Sue saw.•What did Sally whisper that she had secretly read?•John wants very much for himself to win.•Those are the books you should read before it becomes difficult to talk about.•Those are the books you should read before talking about becomes difficult.•Who did Jo think said John saw him?•That a serious discussion could arise here of this topic was quite unexpected.•The boys read Mary’s stories about each other.Is this grammatical? - Answers•Y: John I believe Sally said Bill believed Sue saw. •N: What did Sally whisper that she had secretly read?•Y: John wants very much for himself to win.•Y: Those are the books you should read before it becomes difficult to talk about.•N: Those are the books you should read before talking about becomes difficult.•Y: Who did Jo think said John saw him?•Y: That a serious discussion could arise here of this topic was quite unexpected.•N: The boys read Mary’s stories about each other.Answers due to van Riemsdijk and Williams, 1986, given in Manning and SchutzeAmbiguity in parsing - 1•Note:•S= sentence•NP=noun phrase•VP=verb phrase•Aux=auxiliary•V=verbFigure from Manning and SchutzeAmbiguity in parsing - 2•cf •Our problem is training workersFigure from Manning and SchutzeAmbiguity in parsing - 4•cf•Those are training wheelsFigure from Manning and SchutzeAmbiguity in parsing -4 •a reasonably sophisticated system gives 455 parses for:•List the sales of the products produced in 1973 with the products produced in 1972•Difficulty:•There doesn’t seem to be a single grammar that is right•choice of grammar is not innocuous:•more complex grammars lead to more ambiguous parses•less complex grammars can’t deal with some (possibly important) special casesCounts, frequencies and probabilities•Important phenomena•Some things are very frequent•Most are very rare•This is a dominant phenomenon in natural language•important in vision, tooWhat is a word?•Word token•each actual instance of the word•There are two “the”s in “the cat sat on the mat”•count with multiplicity•e.g. 71, 370 in Tom Sawyer•Word type•“the” occurs in “the cat sat on the mat”•count without multiplicity•e.g. 8, 018 in Tom Sawyer•Are these two the same word?•“ate”, “eat”, “eating”•“stock”, “stocking” (perhaps if they’re both verbs, but...)From Manning and Schutze; recall there are 71, 370 word tokens in Tom SawyerFrom Manning and Schutze; recall there are 8, 018 word typesZipf’s law•rank word types by frequency, highest first•each word type then has:•a frequency, f•a rank, r•Zipf’s law:• f r = constantFigure from Manning and SchutzeZipf’s law •Qualitatively, assuming there are many words•few very common words•moderate number of medium frequency words•very many low frequency words•Implication:•we will spend a lot of effort modelling phenomena we hardly ever observeFigure from Manning and SchutzeCollocations: an example•Collocations are: •turn of phrase or accepted usage where whole is perceived to have an existence beyond sum of parts•compounds - disk drive•phrasal verbs - make up•stock phrases - bacon and eggs; steak and kidney; egg and bacon; etc.Finding possible collocations•Strategy 1: find pairs of words with high frequencyFigure from Manning and SchutzeFinding possible collocations•Strategy 2: find high frequency pairs of words and then filter them, rejecting any pairs(triples) that do not correspond to part of speech patterns.Figure from Manning and SchutzeFinding possible collocations - 3Figure from Manning and SchutzeProbability and models•I assume very basic knowledge of probability and conditional probability.•Build and investigate procedures to•predict words given words•e.g. english given french•evaluate interpretations of wordsModelling strings of letters•Alphabet: 27 tokens (each letter, space; no cases)•Simplest models:•M1: tokens are independent, identically distributed, have uniform probability•M2: tokens are independent, identically distributed, have different probs.•Which is better? and why?•compare P(M1|S) with P(M2|S)•using Bayes’ ruleConditional probability models•M1 and M2 give quite poor results, M2 much better than M1•Now consider conditional models•we condition a letter on some previous letters•1, 2, ....•sometimes known as Markov models•these are significantly
View Full Document
Unlocking...