Linear-Time Structure Prediction in Language and Biology KEC 1001 Wed, 01/18/2017 - 4:00pm
Liang Huang Assistant Prof., School of EECS, Oregon State University Abstract: <pre>Why are computers so bad at processing human languages while so good at programming languages? What’s the key difference between English and C++ that makes the former so much harder? In this talk I'll present a linear-time (approximate) dynamic programming algorithm for incremental parsing inspired by both human sentence processing (psycholinguistics) and compiler theory (LR parsing). This algorithm, being linear-time, is much faster than, but also as accurate as, the dominant O(n^3) algorithms. It overcomes the ambiguity explosion problem by local ambiguity packing similar to those found in psycholinguistics. More interestingly, there is a striking connection between linguistics and biology: natural language parsing and RNA secondary structure prediction use the same very slow O(n^3) algorithms. While natural language sentences are rarely over 100 words, RNA sequences can be as long as 4,000 nucleotides; so there is a critical need for faster algorithms. We can therefore adapt the same linear-time dynamic programming idea to predict secondary structures for RNA sequences in linear-time, which results in orders of magnitude faster predictions without loss of accuracy. </pre> Bio: URL: http://eecs.oregonstate.edu/colloquium/linear-time-structure-prediction-... [1] [1] http://eecs.oregonstate.edu/colloquium/linear-time-structure-prediction-language-and-biology
_______________________________________________ Colloquium mailing list [email protected] https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
