000000856 001__ 856
000000856 005__ 20260120144839.0
000000856 0247_ $$2DOI$$a10.6083/M40P0X2S
000000856 037__ $$aETD
000000856 245__ $$aPrioritization and pruning: efficient inference with weighted context-free grammars
000000856 260__ $$bOregon Health and Science University
000000856 269__ $$a2012
000000856 336__ $$aDissertation
000000856 502__ $$bPh.D.
000000856 502__ $$gComputer Science & Electrical Engineering (sunsetting)
000000856 520__ $$aThis thesis addresses the challenge of efficient search within the exponential space of parse trees generated by weighted context-free grammars. We introduce four novel probabilistic methods that prioritize and prune the search space, independent of grammar structure or linguistic annotations. Each method leverages lexical cues from the input sentence to guide search effectively. Empirical evaluations demonstrate their integration across multiple parsing architectures, including CKY dynamic programming, best-first graph-based search, and pruned beam search. Combined, these methods achieve state-of-the-art parsing speeds—over 1,500 words per second for English, Chinese, and German—without loss in labeled F1 accuracy. Observed runtime complexity improves from O(N3)O(N^3)O(N3) to O(N1.5)O(N^{1.5})O(N1.5), outperforming traditional coarse-to-fine pruning by more than an order of magnitude.
000000856 540__ $$fCC BY
000000856 542__ $$fIn copyright - single owner
000000856 650__ $$aLinguistics$$021521
000000856 650__ $$aAlgorithms$$014437
000000856 650__ $$aNatural Language Processing$$022716
000000856 6531_ $$apattern recognition
000000856 6531_ $$aautomatic speech recognition
000000856 691__ $$aSchool of Medicine$$041369
000000856 692__ $$aCenter for Spoken Language Understanding$$041388
000000856 7001_ $$aBodenstab, Nathan$$uOregon Health and Science University$$041354
000000856 7201_ $$aRoark, Brian$$uOregon Health and Science University$$041354$$7Personal$$eAdvisor
000000856 8564_ $$9015d2a0f-3b98-4a44-8500-a02568413e36$$s2241334$$uhttps://digitalcollections.ohsu.edu/record/856/files/859_etd.pdf$$ePublic$$2a5c23defdc65a7a14296525b36725dcc$$31
000000856 905__ $$a/rest/prod/fq/97/7t/87/fq977t87t
000000856 909CO $$ooai:digitalcollections.ohsu.edu:856$$pstudent-work
000000856 956__ $$aGet Accessible Copy$$uhttps://ohsu.libwizard.com/f/requestaccessibledocument
000000856 980__ $$aTheses and Dissertations