Сокращение времени анализа парсером Стэнфорда путем обрезания предложения

Question

Мы уже знаем, что время разбора Стэнфордского Парсера увеличивается с увеличением продолжительности предложения. Мне интересно найти творческие способы, в которых мы сокращаем предложение таким образом, чтобы время разбора уменьшалось без ущерба для точности. Напр. мы можем заменить известные существительные фразы одним словом существительные. Точно так же могут быть и другие умные способы угадывать поддерево перед рукой, скажем, используя информацию тега POS? У нас есть огромный корпус неструктурированного текста. Поэтому мы хотим изучить некоторые общие шаблоны, которые в конечном итоге могут сократить время разбора. Также будут высоко оценены некоторые ссылки на общедоступную литературу в этом отношении.

P.S. Мы уже знаем, как многопоточно использовать Stanford Parser, поэтому мы не ищем ответов с этой точки зрения.

Answer 1

Вы запросили «креативные» подходы - Закрытие ячейки Метод обрезки может стоить того. См. Серию публикаций Брайана Роарка, Кристи Холлингсхед и Натана Боденстаба. Документы: 123. Основная интуиция:

• Каждая ячейка в таблице синтаксического анализа CYK «охватывает» определенный промежуток (например, первое 4 слова предложения или слова 13-18 и т.д.)
• Некоторых слов - в частности, в определенных контекстах - очень вряд ли начнет синтаксическую составляющую многословных слов; другие также вряд ли кончат составную часть. Например, слово «the» почти всегда предшествует словосочетанию, и почти невозможно представить, что оно закончит составляющую.
• Если мы сможем обучить узнаваемый машиной классификатор, чтобы идентифицировать такие слова с очень высокой точностью, мы можем тем самым идентифицировать ячейки, которые будут участвовать только в синтаксических выражениях, помещающих указанные слова в крайне маловероятные синтаксические положения. (Обратите внимание, что этот классификатор может использовать линейный тег POS или другие высокоскоростные этапы предварительной обработки.)
• . Закрывая эти ячейки, мы можем значительно уменьшить как асимптотические, так и средние сложности. теории, от кубической сложности до линейного; практически, мы можем достичь приблизительно n^1,5 без потери точности.

Во многих случаях это сокращение фактически увеличивается точность незначительно по сравнению с перебором, поскольку классификатор может включать в себя информацию, которая не доступна для PCFG. Обратите внимание, что это простая, но очень эффективная форма грубой тонкой обрезки с одной грубой стадией (по сравнению с 7-этапным подходом CTF в Berkeley Parser).

Насколько мне известно, Стэнфордский парсер в настоящее время не реализует эту технику обрезки; Я подозреваю, что вы найдете его достаточно эффективным.

Shameless плагин BUBS Parser реализует этот подход, а также несколько других оптимизаций, и, таким образом, достигается пропускная способность около 2500-5000 слов в секунду, как правило, с точностью, по крайней мере равно, что я измеряется с Стэнфордский Парсер. Очевидно, что если вы используете остальную часть трубопровода в Стэнфорде, встроенный парсер уже хорошо интегрирован и удобен. Но если вам нужна улучшенная скорость, BUBS может стоить того, чтобы посмотреть, и он включает в себя некоторый пример кода, который поможет внедрить движок в более крупную систему.

Memoizing Общие подстроки Что касается ваших мыслей о заранее анализирующих известно существительного фраз или других часто наблюдаемых последовательностей с последовательной структурой: Я сделал некоторые оценки подобной идеи несколько лет назад (в контексте совместного использования общих подструктур через большой корпус, при анализе на массивной параллельной архитектуре). Предварительные результаты не были обнадеживающими. В корпусах, на которые мы смотрели, просто не было достаточно повторных подстрок значительной длины, чтобы сделать это стоящим. И вышеупомянутые методы закрытия клеток обычно делают эти подстроки действительно дешевыми для синтаксического анализа.

Однако, если ваши целевые домены связаны с большим количеством повторений, вы можете прийти к другому выводу (может быть, это было бы эффективным для юридических документов с большим количеством копий-и-паттернов) или новостных историй, которые повторяются из разных источники или переизданы с изменениями?)