Slide 1Shallow vs. Knowledge Rich TechniquesTodayRegular Expression/Pattern Matching in NLPReviewSlide 6Slide 7Eliza (Weizenbaum)Eliza-style regular expressionsSubstitutions (Transductions) and Their UsesApplicationsThree ViewsFinite-state Automata (Machines)FormallyYet Another ViewRecognitionRecognitionRecognitionInput TapeInput TapeKey PointsNon-Deterministic FSAs for SheepTalkProblems of Non-DeterminismSlide 24FSAs as Grammars for Natural Language: NamesRecognizing Person NamesSumming UpRegular Expressions and Automata in Natural Language AnalysisCS 4705Some slides adapted from Hirschberg, Dorr/Monz, JurafskySome simple problems: ◦How much is Google worth?◦How much is the Empire State Building worth?◦How much is Columbia University worth?◦How much is the United States worth?◦How much is a college education worth?How much knowledge of language do our algorithms need to do useful NLP?◦80/20 Rule: Claim: 80% of NLP can be done with simple methodsWhen should we worry about the other 20%?Shallow vs. Knowledge Rich TechniquesReview some simple representations of language and see how far they will take us◦Regular Expressions◦Finite State AutomataThink about the limits of these simple approaches◦When are simple methods good enough?◦When do we need something more?TodaySimple but powerful tools for ‘shallow’ processing, e.g. of very large corpora◦What word is begins a sentence?◦What word is most likely to begin a question?◦How often do people end sentences with prepositions?With other simple statistical tools, allow us to◦Obtain word frequency and co-occurrence statisticsWhat is this document ‘about’?What words typically modify other words? ◦Build simple interactive applications (e.g. Eliza)◦Recognize Named Entities (NE): people names, company names◦Deception detection: Statement AnalysisRegular Expression/Pattern Matching in NLPReviewA non-blank lineAny character/./Not an NELower case letter/ [^A-Z]/Possible NECapitalized letter/ [A-Z]/Any l.c. letter/[a-z]/Rhyme:/[bckmrs]ite/Any char in set/[bckmsr]/A ‘.’, a ‘?’/\./, /\?/UsesMatchesRERhyme: /[a-z]ite/A statement, a questionRE Description Uses?/a*/ Zero or more a’s /(very[ ])*//a+/ One or more a’s /(very[ ])+//a?/ Optional single a /(very[ ])?//cat|dog/ ‘cat’ or ‘dog’ /[A-Z,a-z]* (cat|dog)//^[Nn]o$/ A line with only ‘No’ or ‘no’ in it/\bun\B/ Prefixes Words prefixed by ‘un’ (nb. union)Patterns: happier and happier, fuzzier and fuzzier, classifier and classifier/ (.+ier) and \1 /Morphological variants of ‘kitty’/kitt(y|ies|en|ens)/E.G.RE plusMen are all alike. IN WHAT WAY? They're always bugging us about something or other. CAN YOU THINK OF A SPECIFIC EXAMPLE? Well, my boyfriend made me come here. YOUR BOYFRIEND MADE YOU COME HERE He says I'm depressed much of the time. I AM SORRY TO HEAR YOU ARE DEPRESSED It's true. I am unhappy DO YOU THINK COMING HERE WILL HELP YOU NOT TO BE UNHAPPY I need some help, that much seems certain. WHAT WOULD IT MEAN TO YOU IF YOU GOT SOME HELP Perhaps I could learn to get along with my mother. TELL ME MORE ABOUT YOUR FAMILY My mother takes care of me. WHO ELSE IN YOUR FAMILY TAKES CARE OF YOU My father. YOUR FATHER You are like my father in some ways. Eliza (Weizenbaum)s/.* YOU ARE (depressed|sad) .*/I AM SORRY TO HEAR YOU ARE \1/s/.* YOU ARE (depressed|sad) .*/WHY DO YOU THINK YOU ARE \1/s/.* all .*/IN WHAT WAY/s/.* always .*/CAN YOU THINK OF A SPECIFIC EXAMPLE/Eliza-style regular expressionsStep 1: replace first person with second person referencess/\bI(’m| am)\b /YOU ARE/gs/\bmy\b /YOUR/gS/\bmine\b /YOURS/gStep 2: use additional regular expressions to generate repliesStep 3: use scores to rank possible transformationsSlide from Dorr/MonzE.g. unix sed or ‘s’ operator in Perl (s/regexpr/pattern/)◦Transform time formats: s/([1]?[0-9]) o’clock ([AaPp][Mm])/\1:00 \2/ How would you convert to 24-hour clock?◦What does this do?s/[0-9][0-9][0-9]-[0-9][0-9][0-9]-[0-9][0-9][0-9][0-9]/ 000-000-0000/ Substitutions (Transductions) and Their UsesPredictions from a news corpus: ◦Which candidate for President is mentioned most often in the news? Is going to win?◦Which White House advisors have the most power?Language usage:◦Which form of comparative is more common: ‘Xer’ or ‘more X’?◦Which pronouns occur most often in subject position?◦How often do sentences end with infinitival ‘to’?◦What words typically begin and end sentences?ApplicationsThree equivalent formal ways to look at what we’re up toThree ViewsRegular ExpressionsRegularLanguagesFinite State AutomataRegular GrammarsFinite-state Automata (Machines)/^baa+!$/q0q1q2q3q4b a a !astatetransitionfinalstate baa! baaa! baaaa! baaaaa! ...Slide from Dorr/MonzFSA is a 5-tuple consisting of◦Q: set of states {q0,q1,q2,q3,q4}◦: an alphabet of symbols {a,b,!}◦q0: a start state in Q◦F: a set of final states in Q {q4}◦(q,i): a transition function mapping Q x  to QFormallyq0q4q1 q2 q3b aaa !Yet Another ViewState-transition tableRecognition is the process of determining if a string should be accepted by a machineOr… it’s the process of determining if a string is in the language we’re defining with the machineOr… it’s the process of determining if a regular expression matches a stringRecognitionRecognitionTraditionally, (Turing’s idea) this process is depicted with a tape.Start in the start stateExamine the current inputConsult the tableGo to a new state and update the tape pointer.Until you run out of tape.RecognitionInput Tapea b a ! bq001 2 3 4b a a!aREJECTSlide from Dorr/MonzInput Tapeb a a aq0q1q2q3q3q4!01 2 3 4b a a!aACCEPTSlide from Dorr/MonzDeterministic means that at each point in processing there is always one unique thing to do (no choices).D-recognize is a simple table-driven interpreterThe algorithm is universal for all unambiguous languages.◦To change the machine, you change the table.Key PointsSlide from JurafskyNon-Deterministic FSAs for SheepTalkq0q4q1 q2 q3b aaa !q0q4q1 q2 q3b a a !At any choice point, we may follow the wrong arcPotential solutions:◦Save backup states at each choice point◦Look-ahead in the input before making choice◦Pursue alternatives in parallel◦Determinize our NFSAs (and then minimize)FSAs can be useful tools for