Parsing Natural Languages

IntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionParsingNaturalLanguagesNitinGuptaundertheguidanceofProf.PushpakBhattacharyaDepartmentofComputerScienceandEngg,IITBombayApril17,2005NitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionParsingProblemsinNLPIntroductionIParsingisafunctionthat,givenanaturallanguagestringasinput,outputsadescriptionofitsconstituentstructure.NitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionParsingProblemsinNLPIntroductionIParsingisafunctionthat,givenanaturallanguagestringasinput,outputsadescriptionofitsconstituentstructure.IParsingisthetaskofidentifyingphrasesofasentenceanddescribingthesyntacticrelationsamongthem.SVPADJNPNVflyingplanesaretheypronNPBDCEFNitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionParsingProblemsinNLPIntroductionIParsingisafunctionthat,givenanaturallanguagestringasinput,outputsadescriptionofitsconstituentstructure.IParsingisthetaskofidentifyingphrasesofasentenceanddescribingthesyntacticrelationsamongthem.SVPADJNPNVflyingplanesaretheypronNPBDCEFIMostcommonuseofparsersistoparsecomputerprogramminglanguages.NitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionParsingProblemsinNLPIntroductionIParsingisafunctionthat,givenanaturallanguagestringasinput,outputsadescriptionofitsconstituentstructure.IParsingisthetaskofidentifyingphrasesofasentenceanddescribingthesyntacticrelationsamongthem.SVPADJNPNVflyingplanesaretheypronNPBDCEFIMostcommonuseofparsersistoparsecomputerprogramminglanguages.IStatisticalNLP:determinehowtomodelthelanguagebyderivingprobabilityestimatesforunseenevents.NitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionParsingProblemsinNLPCentralProblemsIGrammaticalagreement:ensurethatparseracceptsasgrammaticalonlyagreement-legalstrings,andrejectsthoseinwhichagreementfails.NitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionParsingProblemsinNLPCentralProblemsIGrammaticalagreement:ensurethatparseracceptsasgrammaticalonlyagreement-legalstrings,andrejectsthoseinwhichagreementfails.IAmbiguity:It’swellknownthatsomeEnglishsentencesareambiguous.SVPADJNPNVflyingplanesaretheypronNPSVPpronNPAUXVNtheyflyingplanesareNitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionParsingProblemsinNLPCentralProblemsIGrammaticalagreement:ensurethatparseracceptsasgrammaticalonlyagreement-legalstrings,andrejectsthoseinwhichagreementfails.IAmbiguity:It’swellknownthatsomeEnglishsentencesareambiguous.SVPADJNPNVflyingplanesaretheypronNPSVPpronNPAUXVNtheyflyingplanesareIClassificationintogrammaticalandungrammatical.NitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionParsingProblemsinNLPCentralProblemsIGrammaticalagreement:ensurethatparseracceptsasgrammaticalonlyagreement-legalstrings,andrejectsthoseinwhichagreementfails.IAmbiguity:It’swellknownthatsomeEnglishsentencesareambiguous.SVPADJNPNVflyingplanesaretheypronNPSVPpronNPAUXVNtheyflyingplanesareIClassificationintogrammaticalandungrammatical.IThestructureanduseoflanguagealsochangesovertime.NitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionParsingProblemsinNLPIntroductionParsingProblemsinNLPDeterministicParsingChomskyHierarchyBasicAlgorithmsChartParserProbabilisticParsingProbabilisticCFGHiddenMarkovModelsOtherConceptsCharniak’sFirstParserProbabilisitcChartParserEntropyInspiredParsingDependencyGrammarIntroductionAdvantagesASimpleAlgorithmConclusionNitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionChomskyHierarchyBasicAlgorithmsChartParserChomskyHierarchyIContainmenthierarchyofclassesofformalgrammarsthatgenerateformallanguages.1.RegularLanguages2.Context-freeGrammar3.Context-sensitiveGrammar4.PhrasestructureGrammarNitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionChomskyHierarchyBasicAlgorithmsChartParserChomskyHierarchyIContainmenthierarchyofclassesofformalgrammarsthatgenerateformallanguages.1.RegularLanguages2.Context-freeGrammar3.Context-sensitiveGrammar4.PhrasestructureGrammarIThisdiscussionassumesthatnaturallanguagesasaclassarecontextfree,thatis,capableofbeinggeneratedbycontextfreegrammars.NitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionChomskyHierarchyBasicAlgorithmsChartParserBasicAlgorithmsIBottomupparsingNitinGuptaParsingNaturalLanguagesIntroductionDeterministicParsingProbabilisticParsingDependencyGrammarConclusionChomskyHierarchyBasicAlgorithmsChartParserBasicAlgorithmsIBottomupparsingITopdo