Roark, B. Probabilistic Top-Down Parsing and Language Modeling [Імовірнісний низхідний синтаксичний аналіз і мовне моделювання] / Brian Roark // Computational linguistics. – 2001. – Vol. 27. – No. 2. – Pр. 249–276. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120101750300526#.WH57w33sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120101750300526
У статті описується робота універсального імовірнісного низхідного синтаксичного аналізатора і його застосування у розробці мовних моделей для систем розпізнавання мовлення. Спочатку в статті розглядаються ключові поняття мовного моделювання та імовірнісного синтаксичного аналізу, а також коротко описуються деякі попередні підходи до використання синтаксичної структури у мовному моделюванні. Далі описується лексикалізований імовірнісний низхідний синтаксичний аналізатор, який показує дуже гарні результати у порівнянні з найкращими універсальними статистичними синтаксичними аналізаторами як з точки зору правильності отриманих граматичних розборів, так і з точки зору ефективності їх знаходження. Потім описується нова мовна модель на основі імовірнісного низхідного синтаксичного аналізу. Емпіричні результати свідчать, що на відміну від попередніх моделей вона має кращу перплексивність на основі тренувального корпусу. Інтерполяція з триграмною моделлю дозволяє досягти набагато помітнішого покращення результатів, аніж застосування будь-якої іншої моделі, демонструючи ступінь розбіжності між інформацією, отриманою за допомогою нашої моделі синтаксичного аналізу, та інформацією, отриманою за допомогою триграмної моделі. Практичну цінність моделі підтверджує також невеликий експеримент із розпізнавання.
У статті описується робота універсального імовірнісного низхідного синтаксичного аналізатора і його застосування у розробці мовних моделей для систем розпізнавання мовлення. Спочатку в статті розглядаються ключові поняття мовного моделювання та імовірнісного синтаксичного аналізу, а також коротко описуються деякі попередні підходи до використання синтаксичної структури у мовному моделюванні. Далі описується лексикалізований імовірнісний низхідний синтаксичний аналізатор, який показує дуже гарні результати у порівнянні з найкращими універсальними статистичними синтаксичними аналізаторами як з точки зору правильності отриманих граматичних розборів, так і з точки зору ефективності їх знаходження. Потім описується нова мовна модель на основі імовірнісного низхідного синтаксичного аналізу. Емпіричні результати свідчать, що на відміну від попередніх моделей вона має кращу перплексивність на основі тренувального корпусу. Інтерполяція з триграмною моделлю дозволяє досягти набагато помітнішого покращення результатів, аніж застосування будь-якої іншої моделі, демонструючи ступінь розбіжності між інформацією, отриманою за допомогою нашої моделі синтаксичного аналізу, та інформацією, отриманою за допомогою триграмної моделі. Практичну цінність моделі підтверджує також невеликий експеримент із розпізнавання.
Переклад М. Драчової
Tomuro, N. Nonminimal Derivations in Unification-based Parsing [Немінімальні деривати у синтаксичному аналізі на основі уніфікаційних граматик] / Noriko Tomuro, Steven L. Lytinen // Computational linguistics. – 2001. – Vol. 27. – No. 2. – Pages 277–285. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120101750300535#.WH57Nn3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120101750300535
Запропонований для уніфікаційних граматик Б. Шибером [Shieber, 1992] алгоритм абстрактного синтаксичного аналізу є розширенням алгоритму Ерли [Earley, 1970] для контекстно-вільних граматик з метою виділення структур. У статті показано, що за певних умов алгоритм Шибера утворює так званий немінімальний дериват: синтаксичне дерево з додатковими елементами, відсутніми у лицензійних наборах правил. Хоча надане Б. Шибером визначення синтаксичного дерева не виключає подібні немінімальні деривати, стверджується, що їх потрібно уважати помилкою. Описано джерела проблеми немінімальної деривації і запропоновано чітке визначення мінімального синтаксичного дерева і модифікацію алгоритму Шибера, яка забезпечує мінімалізм, щоправда за рахунок продуктивності.
Запропонований для уніфікаційних граматик Б. Шибером [Shieber, 1992] алгоритм абстрактного синтаксичного аналізу є розширенням алгоритму Ерли [Earley, 1970] для контекстно-вільних граматик з метою виділення структур. У статті показано, що за певних умов алгоритм Шибера утворює так званий немінімальний дериват: синтаксичне дерево з додатковими елементами, відсутніми у лицензійних наборах правил. Хоча надане Б. Шибером визначення синтаксичного дерева не виключає подібні немінімальні деривати, стверджується, що їх потрібно уважати помилкою. Описано джерела проблеми немінімальної деривації і запропоновано чітке визначення мінімального синтаксичного дерева і модифікацію алгоритму Шибера, яка забезпечує мінімалізм, щоправда за рахунок продуктивності.
Переклад В. Коломієць
Johnson, M. The DOP Estimation Method Is Biased and Inconsistent [Метод оцінювання синтаксичного аналізу, керованого даними, є необ’єктивним і непослідовним] / Mark Johnson // Computational linguistics. – 2002. – Vol. 28. – No. 1. – Pages 71 – 76. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120102317341783#.WH59DH3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120102317341783
Синтаксичний аналіз, керований даними, або модель керованого даними синтаксичного аналізу, поєднує фрагменти лінгвістичних репрезентацій з чисельними вагами, визначеними шляхом нормалізації емпіричної частоти кожного фрагмента в тренувальному корпусі (див. працю Bod, 1998 і цитовані у ній роботи). У статті повідомляється, що даний метод оцінювання є необ’єктивним і суперечливим. Інакше кажучи, зі збільшенням обсягу тренувального корпусу передбачуваний розподіл загалом не співпадає з реальним розподілом.
Синтаксичний аналіз, керований даними, або модель керованого даними синтаксичного аналізу, поєднує фрагменти лінгвістичних репрезентацій з чисельними вагами, визначеними шляхом нормалізації емпіричної частоти кожного фрагмента в тренувальному корпусі (див. працю Bod, 1998 і цитовані у ній роботи). У статті повідомляється, що даний метод оцінювання є необ’єктивним і суперечливим. Інакше кажучи, зі збільшенням обсягу тренувального корпусу передбачуваний розподіл загалом не співпадає з реальним розподілом.
Переклад І. Снєгурова
Nederhof, M. Weighted Deductive Parsing and Knuth's Algorithm [Зважений дедуктивний синтаксичний аналіз і алгоритм Нута] / Mark-Jan Nederhof // Computational linguistics. – 2003. – Vol. 29. – No. 1. – Pages 135–143. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120103321337467#.WH59VX3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120103321337467
У статті аналізується зважений дедуктивний синтаксичний аналіз і розглядається проблема знаходження дериватів із найнижчою вагою. Показано, що здійснене Нутом узагальнення алгоритму Дійкстра для знаходження найкоротшого шляху є загальним методом вирішення вказаної проблеми. Наш підхід є модульним у тому сенсі, що алгоритм Нута формулюється незалежно від зваженої дедуктивної системи.
У статті аналізується зважений дедуктивний синтаксичний аналіз і розглядається проблема знаходження дериватів із найнижчою вагою. Показано, що здійснене Нутом узагальнення алгоритму Дійкстра для знаходження найкоротшого шляху є загальним методом вирішення вказаної проблеми. Наш підхід є модульним у тому сенсі, що алгоритм Нута формулюється незалежно від зваженої дедуктивної системи.
Переклад В. Коломієць
Oflazer, K. Dependency Parsing with an Extended Finite-State Approach [Розбір залежностей на основі концепції розширеного скінченного автомату] / Kemal Oflazer // Computational linguistics. – 2003. – Vol. 29. – No. 4. – Pages 515–544. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120103322753338#.WH59on3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120103322753338
У статті представлена схема розбору залежностей на основі концепції розширеного скінченного автомату. Аналізатор додає до вхідного представлення «канали», щоб можна було розмістити ребра, які відображають зв’язки синтаксичної залежності між словами, і аналізує вхідні дані багато разів для того, щоб отримати певний результат. Проміжні конфігурації, що порушують різні вимоги до проективних дерев залежностей, такі як відсутність ребер, що перетинаються, і відсутність незалежних елементів за винятком кореня дерева, фільтруються за допомогою фільтрів із скінченним числом станів. Парсер використовувався для синтаксичного аналізу турецької мови на основі граматики залежностей.
У статті представлена схема розбору залежностей на основі концепції розширеного скінченного автомату. Аналізатор додає до вхідного представлення «канали», щоб можна було розмістити ребра, які відображають зв’язки синтаксичної залежності між словами, і аналізує вхідні дані багато разів для того, щоб отримати певний результат. Проміжні конфігурації, що порушують різні вимоги до проективних дерев залежностей, такі як відсутність ребер, що перетинаються, і відсутність незалежних елементів за винятком кореня дерева, фільтруються за допомогою фільтрів із скінченним числом станів. Парсер використовувався для синтаксичного аналізу турецької мови на основі граматики залежностей.
Переклад А. Синящик
Collins, M. Head-Driven Statistical Models for Natural Language Parsing [Вершинні статистичні моделі синтаксичного аналізу природної мови] / Michael Collins // Computational linguistics. – 2003. – Vol. 29. – No. 4. – Pages 589–637. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120103322753356#.WH597n3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120103322753356
У статті описано три статистичні моделі синтаксичного аналізу природної мови. Ці моделі розширюють методи від імовірнісних безконтекстних граматик до лексикалізованих граматик, утворюючи підходи, у яких дерево розбору представлене як послідовність рішень, яка відповідає розбудові дерева згори донизу, починаючи з вершини. Потім припущення про незалежність дозволяють отримати параметри, які програмують Х-штрих-схему, підкласифікацію, послідовність додатків, розміщення обставинних слів, лексичні залежності біграмів, переміщення питальних слів і вибір близького суміщення. Всі ці преференції виражені ступенями імовірності, зумовленими лексичними вершинами. Моделі оцінено за допомогою корпусу Penn Wall Street Journal Treebank і з’ясовано, що за точністю вони не поступаються іншим моделям, описаним у літературі. Для кращого розуміння цих моделей наведено результати для різних типів складників, а також розбивка показників точності й повноти у виявленні різних типів залежностей. Проаналізовано різні характеристики моделей шляхом експериментів з точністю синтаксичного аналізу, шляхом збирання частот різних структур у банку дерев, а також шляхом аналізу цікавих з лінгвістичної точки зору прикладів. Нарешті, досліджувані моделі порівняно з іншими, які застосовувались у синтаксичному розборі банку дерев, для того щоб якось пояснити різницю між продуктивністю різних моделей.
У статті описано три статистичні моделі синтаксичного аналізу природної мови. Ці моделі розширюють методи від імовірнісних безконтекстних граматик до лексикалізованих граматик, утворюючи підходи, у яких дерево розбору представлене як послідовність рішень, яка відповідає розбудові дерева згори донизу, починаючи з вершини. Потім припущення про незалежність дозволяють отримати параметри, які програмують Х-штрих-схему, підкласифікацію, послідовність додатків, розміщення обставинних слів, лексичні залежності біграмів, переміщення питальних слів і вибір близького суміщення. Всі ці преференції виражені ступенями імовірності, зумовленими лексичними вершинами. Моделі оцінено за допомогою корпусу Penn Wall Street Journal Treebank і з’ясовано, що за точністю вони не поступаються іншим моделям, описаним у літературі. Для кращого розуміння цих моделей наведено результати для різних типів складників, а також розбивка показників точності й повноти у виявленні різних типів залежностей. Проаналізовано різні характеристики моделей шляхом експериментів з точністю синтаксичного аналізу, шляхом збирання частот різних структур у банку дерев, а також шляхом аналізу цікавих з лінгвістичної точки зору прикладів. Нарешті, досліджувані моделі порівняно з іншими, які застосовувались у синтаксичному розборі банку дерев, для того щоб якось пояснити різницю між продуктивністю різних моделей.
Переклад А. Синящик
Hwa, R. Sample Selection for Statistical Parsing [Формування вибірки для статистичного синтаксичного аналізу] / Rebecca Hwa // Computational linguistics. – 2004. – Vol. 30. – No. 3. – Pр. 253–267. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/0891201041850894#.WH5-UX3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/0891201041850894
Корпусно-базований статистичний синтаксичний аналіз спирається на використання великих обсягів анотованого тексту в якості прикладів для тренування. Створення такого ресурсу є дорогим і трудомістким процесом. У статті пропонується використовувати формування вибірки для знаходження корисних прикладів для тренування та скорочення людських зусиль, що витрачаються на анотування менш інформативних прикладів. Ми використовуємо декілька критеріїв, щоб спрогнозувати, чи можуть немарковані дані бути корисними навчальними прикладами. Для порівняння ефективності різних критеріїв прогнозування проведено експерименти із використанням двох синтаксичних тренувальних завдань і двох моделей навчання у рамках одного завдання синтаксичного аналізу. Ми виявили, що формування вибірки може значно зменшити обсяг анотованих тренувальних корпусів, і що невизначеність є надійним критерієм прогнозування, який можна легко застосувати для різних моделей навчання.
Корпусно-базований статистичний синтаксичний аналіз спирається на використання великих обсягів анотованого тексту в якості прикладів для тренування. Створення такого ресурсу є дорогим і трудомістким процесом. У статті пропонується використовувати формування вибірки для знаходження корисних прикладів для тренування та скорочення людських зусиль, що витрачаються на анотування менш інформативних прикладів. Ми використовуємо декілька критеріїв, щоб спрогнозувати, чи можуть немарковані дані бути корисними навчальними прикладами. Для порівняння ефективності різних критеріїв прогнозування проведено експерименти із використанням двох синтаксичних тренувальних завдань і двох моделей навчання у рамках одного завдання синтаксичного аналізу. Ми виявили, що формування вибірки може значно зменшити обсяг анотованих тренувальних корпусів, і що невизначеність є надійним критерієм прогнозування, який можна легко застосувати для різних моделей навчання.
Переклад М. Драчової, В. Туз
Bikel, D. Intricacies of Collins' Parsing Model [Тонкощі моделі синтаксичного аналізу Коллінза] / Daniel M. Bikel // Computational linguistics. – 2004. – Vol. 30. – No. 4. – Pр. 479–511. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/0891201042544929#.WH5-qH3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/0891201042544929
У статті наведено таку велику кількість досі неопублікованих подробиць про синтаксичний аналізатор Коллінза, що разом із дисертацією Коллінза (1999) вона містить усю інформацію, необхідну для відтворення результатів тестів Коллінза. Дійсно, ці досі неопубліковані дані пояснюють відносне збільшення на 11% похибки від імплементації, включаючи всі подробиці, до остаточної імплементації моделі Коллінза. Ми також демонструємо чистіший і однаково добре функціонуючий метод обробки пунктуації і сполучників і розкриваємо деякі інші ймовірнісні причуди синтаксичного аналізатора Коллінза. Ми не тільки проаналізували значимість неопублікованих подробиць, але також здійснили повторний аналіз значимості деяких добре відомих деталей, з’ясувавши, що у моделі практично не використовуються подвійні лексичні залежності і що вибір стрижневого слова впливає на загальну продуктивність синтаксичного розбору менше, аніж уважалося раніше. Нарешті, ми провели експерименти, які свідчать, що справжня дискримінаційна потужність лексикалізації можливо полягає в тому, що генерація нелексикалізованих синтаксичних структур відбувається відповідно частиномовної приналежності стрижневого слова.
У статті наведено таку велику кількість досі неопублікованих подробиць про синтаксичний аналізатор Коллінза, що разом із дисертацією Коллінза (1999) вона містить усю інформацію, необхідну для відтворення результатів тестів Коллінза. Дійсно, ці досі неопубліковані дані пояснюють відносне збільшення на 11% похибки від імплементації, включаючи всі подробиці, до остаточної імплементації моделі Коллінза. Ми також демонструємо чистіший і однаково добре функціонуючий метод обробки пунктуації і сполучників і розкриваємо деякі інші ймовірнісні причуди синтаксичного аналізатора Коллінза. Ми не тільки проаналізували значимість неопублікованих подробиць, але також здійснили повторний аналіз значимості деяких добре відомих деталей, з’ясувавши, що у моделі практично не використовуються подвійні лексичні залежності і що вибір стрижневого слова впливає на загальну продуктивність синтаксичного розбору менше, аніж уважалося раніше. Нарешті, ми провели експерименти, які свідчать, що справжня дискримінаційна потужність лексикалізації можливо полягає в тому, що генерація нелексикалізованих синтаксичних структур відбувається відповідно частиномовної приналежності стрижневого слова.
Переклад М. Драчової
Collins, M. Discriminative Reranking for Natural Language Parsing [Диференціальне переранжування у синтаксичному аналізі природних мов] / Michael Collins, Terry Koo // Computational linguistics. – 2005. – Vol. 31. – No. 1. – Pр. 25–70. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/0891201053630273#.WH5_An3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/0891201053630273
У статті розглядаються підходи до переранжування виходу існуючого імовірнісного синтаксичного аналізатора. Основний синтаксичний аналізатор виводить набір можливих граматичних розборів для кожного вхідного речення разом із відповідними ймовірностями, які визначають початкове ранжування цих граматичних розборів. Друга модель потім намагається поліпшити початкове ранжування, використовуючи для цього додаткові характеристики дерева. Сильною стороною нашого підходу є те, що він дозволяє розглядати дерево як довільний набір характеристик, без урахування того, як ці характеристики взаємодіють або перетинаються, і без необхідності визначати дериваційну або породжувальну модель, яка враховує ці характеристики. Ми пропонуємо новий метод переранжування на основі форсуючого підходу до проблем ранжування, описаного у роботі Й. Фройнда та ін. (Freund et al., 1998). Ми застосували форсуючий метод для синтаксичного аналізу банку дерев речень із газети Wall Street Journal. Даний метод являє собою комбінацію логарифмічної функції правдоподібності, яка використовується у базовій моделі (запропонованій М. Коллінзом (Collins, 1999)), і інформації про додаткові 500 тисяч характеристик синтаксичних дерев, які не брались до уваги у вихідній моделі. Нова модель досягла значення F-міри 89,75 %, відносного зниження на 13 % похибки F-міри порівняно з показником базової моделі — 88,2 %. У статті також представлено новий алгоритм форсуючого методу, у якому використано переваги обмеженої кількості характеристик синтаксичних дерев. Експериментально підтверджено, що новий алгоритм забезпечує значне зростання продуктивності у процесі активного використання форсуючого підходу. Ми уважаємо, що запропонований метод є привабливою альтернативою – як з точки зору простоти використання, так і з точки зору продуктивності – розробці методів відбору характеристик у межах логлінійних моделей (моделей максимальної ентропії). Хоча експерименти, описані у цій статті, пов’язані із автоматичним синтаксичним аналізом природних мов, даний підхід може бути застосований для вирішення багатьох інших проблем автоматичної обробки природних мов, які звичайно формулюються як завдання ранжування, наприклад, розпізнавання мови, машинного перекладу або синтезу мови.
У статті розглядаються підходи до переранжування виходу існуючого імовірнісного синтаксичного аналізатора. Основний синтаксичний аналізатор виводить набір можливих граматичних розборів для кожного вхідного речення разом із відповідними ймовірностями, які визначають початкове ранжування цих граматичних розборів. Друга модель потім намагається поліпшити початкове ранжування, використовуючи для цього додаткові характеристики дерева. Сильною стороною нашого підходу є те, що він дозволяє розглядати дерево як довільний набір характеристик, без урахування того, як ці характеристики взаємодіють або перетинаються, і без необхідності визначати дериваційну або породжувальну модель, яка враховує ці характеристики. Ми пропонуємо новий метод переранжування на основі форсуючого підходу до проблем ранжування, описаного у роботі Й. Фройнда та ін. (Freund et al., 1998). Ми застосували форсуючий метод для синтаксичного аналізу банку дерев речень із газети Wall Street Journal. Даний метод являє собою комбінацію логарифмічної функції правдоподібності, яка використовується у базовій моделі (запропонованій М. Коллінзом (Collins, 1999)), і інформації про додаткові 500 тисяч характеристик синтаксичних дерев, які не брались до уваги у вихідній моделі. Нова модель досягла значення F-міри 89,75 %, відносного зниження на 13 % похибки F-міри порівняно з показником базової моделі — 88,2 %. У статті також представлено новий алгоритм форсуючого методу, у якому використано переваги обмеженої кількості характеристик синтаксичних дерев. Експериментально підтверджено, що новий алгоритм забезпечує значне зростання продуктивності у процесі активного використання форсуючого підходу. Ми уважаємо, що запропонований метод є привабливою альтернативою – як з точки зору простоти використання, так і з точки зору продуктивності – розробці методів відбору характеристик у межах логлінійних моделей (моделей максимальної ентропії). Хоча експерименти, описані у цій статті, пов’язані із автоматичним синтаксичним аналізом природних мов, даний підхід може бути застосований для вирішення багатьох інших проблем автоматичної обробки природних мов, які звичайно формулюються як завдання ранжування, наприклад, розпізнавання мови, машинного перекладу або синтезу мови.
Переклад М. Драчової
Garmallo, P. Clustering Syntactic Positions with Similar Semantic Requirements [Кластеризація синтаксичних позицій із подібними семантичними вимогами] / Pablo Gamallo , Alexandre Agustini , Gabriel P. Lopes // Computational linguistics. – 2005. – Vol. 31. – No. 1. – Pр. 107–146. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/0891201053630318#.WH5_b33sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/0891201053630318
У статті описується неконтрольований метод визначення синтактико-семантичних вимог іменників, дієслів та прикметників на основі корпусу з частковою синтаксичною розміткою. Лінгвістичне поняття вимоги, що лежить в основі цього методу, базується на двох конкретних припущеннях. По-перше, уважається, що два слова, які знаходяться у відношеннях залежності, вимагають одне одного. Тут це явище називається взаємовимогою. По-друге, стверджується, що набір слів, які вживаються у схожих позиціях, повністю визначає вимоги, асоційовані з цими позиціями. Основною метою представленого у статті методу навчання є визначення кластерів схожих позицій шляхом визначення слів, які повністю встановлюють свої вимоги. Вказана стратегія дозволяє вивчати синтаксичні та семантичні вимоги слів у різних позиціях. Ця інформація використовується для розв’язання синтаксичної омонімії. В кінці статті проаналізовано результати виконання цього конкретного завдання. Числені експерименти проводились на базі корпусів португальської мови.
У статті описується неконтрольований метод визначення синтактико-семантичних вимог іменників, дієслів та прикметників на основі корпусу з частковою синтаксичною розміткою. Лінгвістичне поняття вимоги, що лежить в основі цього методу, базується на двох конкретних припущеннях. По-перше, уважається, що два слова, які знаходяться у відношеннях залежності, вимагають одне одного. Тут це явище називається взаємовимогою. По-друге, стверджується, що набір слів, які вживаються у схожих позиціях, повністю визначає вимоги, асоційовані з цими позиціями. Основною метою представленого у статті методу навчання є визначення кластерів схожих позицій шляхом визначення слів, які повністю встановлюють свої вимоги. Вказана стратегія дозволяє вивчати синтаксичні та семантичні вимоги слів у різних позиціях. Ця інформація використовується для розв’язання синтаксичної омонімії. В кінці статті проаналізовано результати виконання цього конкретного завдання. Числені експерименти проводились на базі корпусів португальської мови.
Переклад О. Мартинюк, М. Погребної
Kallmeyer, L. Tree-Local Multicomponent Tree-Adjoining Grammars with Shared Nodes [Багатокомпонентні граматики об'єднання дерев із спільними вузлами на початковому дереві] / Laura Kallmeyer // Computational linguistics. – 2005. – Vol. 31. – No. 2. – Pages 187–225. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/0891201054223968#.WIemeX3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/0891201054223968
У статті обговорюється питання про те, що виражальна сила граматик об’єднання дерев (англ. tree-adjoining grammars, скор. TAGs) занадто обмежена, щоб упоратися з певними синтаксичними явищами, зокрема з перестановками у мовах із вільним порядком слів. Варіанти TAG, які досі пропонувалися для пояснення перестановок, не є досконалими. Тому у статті пропонується альтернативне розширення TAG на основі поняття спільних вузлів, так звана (обмежена) багатокомпонентна TAG із спільними вузлами на початковому дереві (англ. (restricted) tree-local multicomponent TAG with shared nodes, скор. RSN-MCTAG). Щоб довести, що це розширення TAG може впоратися з перестановками, коротко описується аналіз деяких перестановок у німецькій мові. Потім демонструється, що для певного типу RSN-MCTAG-граматик можна створити еквівалентні прості граматики склеювання інтервалів (англ. range concatenation grammars). Як наслідок, такі RSN-MCTAG-граматики є слабо контекстно-залежними і при цьому аналізуються за поліноміальний час. Ці специфічні RSN-MCTAG-граматики, можливо, можуть упоратися не з усіма перестановками, але з достатньо великою підмножиною.
У статті обговорюється питання про те, що виражальна сила граматик об’єднання дерев (англ. tree-adjoining grammars, скор. TAGs) занадто обмежена, щоб упоратися з певними синтаксичними явищами, зокрема з перестановками у мовах із вільним порядком слів. Варіанти TAG, які досі пропонувалися для пояснення перестановок, не є досконалими. Тому у статті пропонується альтернативне розширення TAG на основі поняття спільних вузлів, так звана (обмежена) багатокомпонентна TAG із спільними вузлами на початковому дереві (англ. (restricted) tree-local multicomponent TAG with shared nodes, скор. RSN-MCTAG). Щоб довести, що це розширення TAG може впоратися з перестановками, коротко описується аналіз деяких перестановок у німецькій мові. Потім демонструється, що для певного типу RSN-MCTAG-граматик можна створити еквівалентні прості граматики склеювання інтервалів (англ. range concatenation grammars). Як наслідок, такі RSN-MCTAG-граматики є слабо контекстно-залежними і при цьому аналізуються за поліноміальний час. Ці специфічні RSN-MCTAG-граматики, можливо, можуть упоратися не з усіма перестановками, але з достатньо великою підмножиною.
Переклад В. Коломієць
Merlo, P. The Notion of Argument in Prepositional Phrase Attachment [Поняття аргумента у приєднанні прийменникової групи] / Paola Merlo, Eva Esteve Ferrer // Computational linguistics. – 2006. – Vol. 32. – No. 3. – Pages 341–378. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli.2006.32.3.341#.WIEiRn3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli.2006.32.3.341
У статті уточнено формулювання проблеми приєднання прийменникової групи як завдання чотирьохкрокового розв’язання неоднозначності. Стверджується, що для аналізу прийменникових груп потрібні знання про місце приєднання (традиційне розрізнення між приєднанням іменників і дієслів) і про сутність приєднання (розрізнення аргументів і ад’юнктів). Описано метод розпізнавання аргументів і ад’юнктів на основі визначення аргументів як вектора характеристик. У серії контрольованих класифікаційних експериментів спочатку досліджуються характеристики, які дозволяють встановити різницю між аргументами і ад’юнктами. З’ясовано, що у пригоді можуть стати як лінгвістична діагностика аргументів, так і лексичні семантичні класи. По-друге, досліджено найкращий метод здійснення чотирьохкрокової класифікації потенційно неоднозначних прийменникових фраз. З’ясовано, що хоча загалом краще вирішувати проблему як єдину задачу чотирьохкрокової класифікації, аргументи дієслів іноді розпізнаються точніше, якщо класифікація виконується як двокроковий процес: спочатку вибирається місце приєднання, а потім воно маркується як аргумент або ад’юнкт.
У статті уточнено формулювання проблеми приєднання прийменникової групи як завдання чотирьохкрокового розв’язання неоднозначності. Стверджується, що для аналізу прийменникових груп потрібні знання про місце приєднання (традиційне розрізнення між приєднанням іменників і дієслів) і про сутність приєднання (розрізнення аргументів і ад’юнктів). Описано метод розпізнавання аргументів і ад’юнктів на основі визначення аргументів як вектора характеристик. У серії контрольованих класифікаційних експериментів спочатку досліджуються характеристики, які дозволяють встановити різницю між аргументами і ад’юнктами. З’ясовано, що у пригоді можуть стати як лінгвістична діагностика аргументів, так і лексичні семантичні класи. По-друге, досліджено найкращий метод здійснення чотирьохкрокової класифікації потенційно неоднозначних прийменникових фраз. З’ясовано, що хоча загалом краще вирішувати проблему як єдину задачу чотирьохкрокової класифікації, аргументи дієслів іноді розпізнаються точніше, якщо класифікація виконується як двокроковий процес: спочатку вибирається місце приєднання, а потім воно маркується як аргумент або ад’юнкт.
Переклад В. Коломієць
Atterer, M. Prepositional Phrase Attachment without Oracles [Підпорядкування прийменникових груп без оракулів] / Michaela Atterer, Hinrich Schütze // Computational linguistics. – 2007. – Vol. 33. – No. 4. – Pages 469–476. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli.2007.33.4.469#.WH6A4n3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli.2007.33.4.469
Дослідники проблеми підпорядкування прийменникової групи загалом уважають, що існує оракул, який генерує дві гіпотетичні структури, між якими потрібно зробити вибір. Інформація про існування двох можливих способів підпорядкування і інформація про лексичні вершини цих груп звичайно видобувається з еталонних дерев синтаксичного розбору. Показано, що з оракулом продуктивність методу перепідпорядкування є вищою, ніж без нього. Оскільки в програмному забезпеченні для обробки природної мови оракули відсутні, показники продуктивності, отримані за допомогою сучасної методики оцінювання підпорядкування прийменникових груп не є об’єктивними. Стверджується, що підпорядкування прийменникових груп потрібно оцінювати не ізольовано, а як невід’ємну частину системи синтаксичного розбору, не користуючись інформацією від еталонного оракула.
Дослідники проблеми підпорядкування прийменникової групи загалом уважають, що існує оракул, який генерує дві гіпотетичні структури, між якими потрібно зробити вибір. Інформація про існування двох можливих способів підпорядкування і інформація про лексичні вершини цих груп звичайно видобувається з еталонних дерев синтаксичного розбору. Показано, що з оракулом продуктивність методу перепідпорядкування є вищою, ніж без нього. Оскільки в програмному забезпеченні для обробки природної мови оракули відсутні, показники продуктивності, отримані за допомогою сучасної методики оцінювання підпорядкування прийменникових груп не є об’єктивними. Стверджується, що підпорядкування прийменникових груп потрібно оцінювати не ізольовано, а як невід’ємну частину системи синтаксичного розбору, не користуючись інформацією від еталонного оракула.
Переклад В. Коломієць
Clark, S. Wide-Coverage Efficient Statistical Parsing with CCG and Log-Linear Models [Широкомасштабний високоефективний статистичний синтаксичний аналіз на основі комбінаторної категорійної граматики і логлінійних моделей] / Stephen Clark, James R. Curran // Computational linguistics. – 2007. – Vol. 33. – No. 4. – Pр. 493–552. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli.2007.33.4.493#.WH6Bd33sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli.2007.33.4.493
У статті описано велику кількість логлінійних моделей синтаксичного аналізу для автоматично зґенерованої лексикалізованої грамматики. Ці моделі синтаксичного аналізу є «повними» у тому смислі, що імовірності визначаються для завершених розборів, а не для незалежних подій, отриманих шляхом розщеплення дерева розбору. Для оцінки моделей використовувалось дискримінаційне навчання, яке вимагало наявності у тренувальних даних не тільки правильного, але й неправильного дерева розбору для кожного речення. У якості лексикалізованого граматичного формалізму використовувалась комбінаторна категорійна граматика (Combinatory Categorial Grammar, скор. CCG), автоматично отримана з банку CCG, версії банку дерев Penn Treebank на основі CCG. Комбінація дискримінаційного навчання і автоматично отриманої граматики вимагає значного обсягу пам’яті (до 25 ГБ), який забезпечувався шляхом паралельної реалізації алгоритму оптимізації BFGS, що виконувався на кластері Beowulf. Динамічне програмування при упакованій схемі, у комбінації з паралельною реалізацією, дозволило вирішити одне з наймасштабніших завдань оцінювання у літературі зі статистичного синтаксичного аналізу менш ніж за три години.
Ключовим компонентом системи синтаксичного аналізу, як для тренування, так і для тестування, є першокласний розмітник на основі методу максимальної ентропії, який приписує словам у реченні лексичні категорії CCG. Цей розмітник робить можливим дискримінаційне навчання, а також високоефективний синтаксичний аналіз. Незважаючи на «уявну неоднозначність» CCG, швидкість синтаксичного аналізу є значно вищою, ніж швидкість подібних синтаксичних аналізаторів у літературі. Також було удосконалено існуючі методи синтаксичного аналізу на основі CCG шляхом розробки нової моделі і ефективного алгоритму синтаксичного аналізу, який використовує усі відхилення, зокрема нестандартні відхилення CCG. Разом із обмеженнями нормальної форми ці модель і алгоритм синтаксичного аналізу забезпечують високу точність знаходження залежностей предикат-аргумент у банку CCG. Синтаксичний аналізатор також був протестований на банку дерев залежностей DepBank і порівняний із синтаксичним аналізатором RASP. Він показав кращі загальні результати і кращі результати для більшості типів залежностей. Тестування на банку дерев залежностей DepBank виявило багато проблем, пов’язаних із оцінкою синтаксичного аналізатора.
Стаття містить детальні рекомендації щодо розробки широкомасштабного синтаксичного аналізатора на основі CCG. Показано, що CCG може забезпечити точний і вісокоефективний синтаксичний аналіз.
У статті описано велику кількість логлінійних моделей синтаксичного аналізу для автоматично зґенерованої лексикалізованої грамматики. Ці моделі синтаксичного аналізу є «повними» у тому смислі, що імовірності визначаються для завершених розборів, а не для незалежних подій, отриманих шляхом розщеплення дерева розбору. Для оцінки моделей використовувалось дискримінаційне навчання, яке вимагало наявності у тренувальних даних не тільки правильного, але й неправильного дерева розбору для кожного речення. У якості лексикалізованого граматичного формалізму використовувалась комбінаторна категорійна граматика (Combinatory Categorial Grammar, скор. CCG), автоматично отримана з банку CCG, версії банку дерев Penn Treebank на основі CCG. Комбінація дискримінаційного навчання і автоматично отриманої граматики вимагає значного обсягу пам’яті (до 25 ГБ), який забезпечувався шляхом паралельної реалізації алгоритму оптимізації BFGS, що виконувався на кластері Beowulf. Динамічне програмування при упакованій схемі, у комбінації з паралельною реалізацією, дозволило вирішити одне з наймасштабніших завдань оцінювання у літературі зі статистичного синтаксичного аналізу менш ніж за три години.
Ключовим компонентом системи синтаксичного аналізу, як для тренування, так і для тестування, є першокласний розмітник на основі методу максимальної ентропії, який приписує словам у реченні лексичні категорії CCG. Цей розмітник робить можливим дискримінаційне навчання, а також високоефективний синтаксичний аналіз. Незважаючи на «уявну неоднозначність» CCG, швидкість синтаксичного аналізу є значно вищою, ніж швидкість подібних синтаксичних аналізаторів у літературі. Також було удосконалено існуючі методи синтаксичного аналізу на основі CCG шляхом розробки нової моделі і ефективного алгоритму синтаксичного аналізу, який використовує усі відхилення, зокрема нестандартні відхилення CCG. Разом із обмеженнями нормальної форми ці модель і алгоритм синтаксичного аналізу забезпечують високу точність знаходження залежностей предикат-аргумент у банку CCG. Синтаксичний аналізатор також був протестований на банку дерев залежностей DepBank і порівняний із синтаксичним аналізатором RASP. Він показав кращі загальні результати і кращі результати для більшості типів залежностей. Тестування на банку дерев залежностей DepBank виявило багато проблем, пов’язаних із оцінкою синтаксичного аналізатора.
Стаття містить детальні рекомендації щодо розробки широкомасштабного синтаксичного аналізатора на основі CCG. Показано, що CCG може забезпечити точний і вісокоефективний синтаксичний аналіз.
Переклад В. Коломієць
Cahill, A. Wide-Coverage Deep Statistical Parsing Using Automatic Dependency Structure Annotation [Широкомасштабний глибокий статистичний синтаксичний аналіз із використаннням автоматичної розмітки структури залежностей] / Aoife Cahill, Michael Burke, Ruth O'Donovan, Stefan Riezler, Josef van Genabith, Andy Way // Computational linguistics. – 2008. – Vol. 34. – No. 1. – Pр. 81–124. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli.2008.34.1.81#.WH6B5n3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli.2008.34.1.81
Останнім часом багато дослідників здійснили експериментальну перевірку синтаксичних аналізаторів – «глибокого», налаштованого вручну, широкомасштабного і «поверхового», на основі машинного навчання – на рівні дерев залежностей, використовуючи прості і автоматичні методи трансформації дерев, ґенерованих поверховими синтаксичними аналізаторами, у дерева залежностей. У статті повторно розглядаються такі експерименти, цього разу із використанням складних автоматичних методів розмітки f-структур ЛФГ із цікавими результатами. Здійснено порівняння різних синтаксичних аналізаторів на основі імовірнісних контекстно-вільних граматик і на основі історії створення моделі з метою визначення базової системи синтаксичного аналізу, яка найкраще вписується у нашу метод автоматичної розмітки структури залежностей. Ця комбінована система синтаксичного аналізатора і розмітки структури залежностей порівнювалась із двома налаштованими вручну глибокими аналізаторами на основі обмежень, RASP i XLE. Оцінювання здійснювалось із використанням золотих стандартів на основі граматики залежностей, а статистична значущість результатів визначалась за допомогою наближеного критерію рандомізації. Проведені експерименти свідчать, що поверхові граматики на основі машинного навчання, удосконалені додаванням складних методів автоматичної розмітки структури залежностей, є ефективнішими, аніж створені вручну, глибокі, широкомасштабні граматики на основі обмежень. Зараз наша найкраща система має f-міру 82,73% на банку синтаксичних дерев PARC 700, що є статистично значимим поліпшенням на 2,18% останніх результатів 80,55% створеної вручну граматики ЛФГ і системи синтаксичного аналізу XLE і f-міру 80,23% на банку синтаксичних дерев СBS 500, що є статистично значимим поліпшенням на 3,66% результатів 76,57%, досягнутих створеною вручну граматикою і системою синтаксичного аналізу RASP.
Останнім часом багато дослідників здійснили експериментальну перевірку синтаксичних аналізаторів – «глибокого», налаштованого вручну, широкомасштабного і «поверхового», на основі машинного навчання – на рівні дерев залежностей, використовуючи прості і автоматичні методи трансформації дерев, ґенерованих поверховими синтаксичними аналізаторами, у дерева залежностей. У статті повторно розглядаються такі експерименти, цього разу із використанням складних автоматичних методів розмітки f-структур ЛФГ із цікавими результатами. Здійснено порівняння різних синтаксичних аналізаторів на основі імовірнісних контекстно-вільних граматик і на основі історії створення моделі з метою визначення базової системи синтаксичного аналізу, яка найкраще вписується у нашу метод автоматичної розмітки структури залежностей. Ця комбінована система синтаксичного аналізатора і розмітки структури залежностей порівнювалась із двома налаштованими вручну глибокими аналізаторами на основі обмежень, RASP i XLE. Оцінювання здійснювалось із використанням золотих стандартів на основі граматики залежностей, а статистична значущість результатів визначалась за допомогою наближеного критерію рандомізації. Проведені експерименти свідчать, що поверхові граматики на основі машинного навчання, удосконалені додаванням складних методів автоматичної розмітки структури залежностей, є ефективнішими, аніж створені вручну, глибокі, широкомасштабні граматики на основі обмежень. Зараз наша найкраща система має f-міру 82,73% на банку синтаксичних дерев PARC 700, що є статистично значимим поліпшенням на 2,18% останніх результатів 80,55% створеної вручну граматики ЛФГ і системи синтаксичного аналізу XLE і f-міру 80,23% на банку синтаксичних дерев СBS 500, що є статистично значимим поліпшенням на 3,66% результатів 76,57%, досягнутих створеною вручну граматикою і системою синтаксичного аналізу RASP.
Переклад В. Коломієць
Eryiğit, G. Dependency Parsing of Turkish [Синтаксичний аналіз турецької мови на основі граматики залежностей] / Gülşen Eryiğit, Joakim Nivre, Kemal Oflazer // Computational linguistics. – 2008. – Vol. 34. – No. 3. – Pр. 357–389. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli.2008.07-017-R1-06-83#.WH6CNn3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli.2008.07-017-R1-06-83
Важливою темою у синтаксичному аналізі є відповідність різних методів синтаксичного аналізу різним мовам. Особливий інтерес у цьому відношенні являють менш досліджені мови, типологічно відмінні від мов, для яких були розроблені методи. У статті описано дослідження керованого даними синтаксичного аналізу на основі граматики залежностей турецької мови, аглютинативної мови із вільним порядком складників, яку можна уважати типовим представником ширшого класу мов подібного типу. Проведені дослідження свідчать, що важливу роль у знаходженні синтаксичних відносин у такій мові відіграє морфологічна структура. Зокрема, показано, що використання у якості основних одиниць синтаксичного аналізу не словоформ, а сублексичних одиниць, відомих як флективні групи, підвищує точність аналізу. Це твердження тестувалося з допомогою двох різних методів синтаксичного аналізу: одного на основі імовірнісної моделі з променевим пошуком, а другого на основі диференційних класифікаторів і детермінованого синтаксичного аналізу. Продемонстровано, що корисність сублексичних одиниць не залежить від методу обробки. Ретельно проаналізовано значення морфологічної і лексичної інформації, і продемонстровано, що за умови грамотного використання така інформація може значно підвищити точність синтаксичного аналізу. Завдяки використанню описаних у статті методів, було перевершено досягнуту попередніми дослідниками точність синтаксичного аналізу банку дерев турецької мови.
Важливою темою у синтаксичному аналізі є відповідність різних методів синтаксичного аналізу різним мовам. Особливий інтерес у цьому відношенні являють менш досліджені мови, типологічно відмінні від мов, для яких були розроблені методи. У статті описано дослідження керованого даними синтаксичного аналізу на основі граматики залежностей турецької мови, аглютинативної мови із вільним порядком складників, яку можна уважати типовим представником ширшого класу мов подібного типу. Проведені дослідження свідчать, що важливу роль у знаходженні синтаксичних відносин у такій мові відіграє морфологічна структура. Зокрема, показано, що використання у якості основних одиниць синтаксичного аналізу не словоформ, а сублексичних одиниць, відомих як флективні групи, підвищує точність аналізу. Це твердження тестувалося з допомогою двох різних методів синтаксичного аналізу: одного на основі імовірнісної моделі з променевим пошуком, а другого на основі диференційних класифікаторів і детермінованого синтаксичного аналізу. Продемонстровано, що корисність сублексичних одиниць не залежить від методу обробки. Ретельно проаналізовано значення морфологічної і лексичної інформації, і продемонстровано, що за умови грамотного використання така інформація може значно підвищити точність синтаксичного аналізу. Завдяки використанню описаних у статті методів, було перевершено досягнуту попередніми дослідниками точність синтаксичного аналізу банку дерев турецької мови.
Переклад В. Коломієць
Nivre, J. Algorithms for Deterministic Incremental Dependency Parsing [Алгоритми детермінованого поетапного синтаксичного аналізу на основі дерев залежностей] / Joakim Nivre // Computational linguistics. – 2008. – Vol. 34. – No. 4. – Pр. 513–553. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli.07-056-R1-07-027#.WH6C-33sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli.07-056-R1-07-027
Алгоритми синтаксичного аналізу, які обробляють вхідні дані зліва направо і створюють єдине виведення часто уважалися неадекватними для обробки природної мови через численні неоднозначності, звичайно притаманні граматикам природної мови. Проте було доведено, що такі алгоритми, у поєднанні із класифікаторами на основі банків дерев, можуть бути використані для створення високоточних синтаксичних аналізаторів для зняття омонімії, зокрема для синтаксичних розборів на основі дерев залежностей. У статті спершу описано загальні принципи опису й аналізу алгоритмів детермінованого поетапного синтаксичного аналізу на основі дерев залежностей, оформленого як системи переходів. Потім описано і проаналізовано дві сім’ї таких алгоритмів: стекові алгоритми і алгоритми на основі списків. У першій сім’ї, яка обмежується проективними структурами залежностей, описано дугоспрямований і дугостандартний варіанти, а в другій сім’ї – проективний і непроективний варіанти. Для кожного з чотирьох алгоритмів наведено докази точності й складності. Крім того здійснено експериментальну перевірку всіх алгоритмів у комбінації з класифікаторами на основі методу опорних векторів для прогнозування наступної операції синтаксичного аналізу, використовуючи дані тринадцяти мов. Показано, що усі чотири алгоритми мають конкурентноспроможну точність, хоча непроективний алгоритм на основі списку звичайно перевершує проективні алгоритми для мов із значною долею непроективних конструкцій. Проте проективні алгоритми часто дають аналогічні результати у комбінації з методом, відомим як псевдо-проективний синтаксичний аналіз.
Лінійна часова складність стекових алгоритмів робить їх ефективнішими у навчанні і синтаксичному аналізі, але на практиці проективні алгоритми на основі списків виявляються не менш ефективними. Більше того, коли проективні алгоритми використовуються для того, щоб здійснити псевдо-проективний синтаксичний аналіз, вони іноді стають менш ефективними у синтаксичному аналізі (але не у навчанні), ніж непроективні алгоритми на основі списків. Хоча більшість алгоритмів були частково описані у літературі раніше, це перший всебічний аналіз і оцінка алгоритмів у рамках єдиної концепції.
Алгоритми синтаксичного аналізу, які обробляють вхідні дані зліва направо і створюють єдине виведення часто уважалися неадекватними для обробки природної мови через численні неоднозначності, звичайно притаманні граматикам природної мови. Проте було доведено, що такі алгоритми, у поєднанні із класифікаторами на основі банків дерев, можуть бути використані для створення високоточних синтаксичних аналізаторів для зняття омонімії, зокрема для синтаксичних розборів на основі дерев залежностей. У статті спершу описано загальні принципи опису й аналізу алгоритмів детермінованого поетапного синтаксичного аналізу на основі дерев залежностей, оформленого як системи переходів. Потім описано і проаналізовано дві сім’ї таких алгоритмів: стекові алгоритми і алгоритми на основі списків. У першій сім’ї, яка обмежується проективними структурами залежностей, описано дугоспрямований і дугостандартний варіанти, а в другій сім’ї – проективний і непроективний варіанти. Для кожного з чотирьох алгоритмів наведено докази точності й складності. Крім того здійснено експериментальну перевірку всіх алгоритмів у комбінації з класифікаторами на основі методу опорних векторів для прогнозування наступної операції синтаксичного аналізу, використовуючи дані тринадцяти мов. Показано, що усі чотири алгоритми мають конкурентноспроможну точність, хоча непроективний алгоритм на основі списку звичайно перевершує проективні алгоритми для мов із значною долею непроективних конструкцій. Проте проективні алгоритми часто дають аналогічні результати у комбінації з методом, відомим як псевдо-проективний синтаксичний аналіз.
Лінійна часова складність стекових алгоритмів робить їх ефективнішими у навчанні і синтаксичному аналізі, але на практиці проективні алгоритми на основі списків виявляються не менш ефективними. Більше того, коли проективні алгоритми використовуються для того, щоб здійснити псевдо-проективний синтаксичний аналіз, вони іноді стають менш ефективними у синтаксичному аналізі (але не у навчанні), ніж непроективні алгоритми на основі списків. Хоча більшість алгоритмів були частково описані у літературі раніше, це перший всебічний аналіз і оцінка алгоритмів у рамках єдиної концепції.
Переклад В. Коломієць
Schuler, W. Broad-Coverage Parsing Using Human-Like Memory Constraints [Використання властивих людині обмежень обсягу пам’яті у синтаксичному аналізаторі з широким покриттям] / William Schuler, Samir AbdelRahman, Tim Miller, Lane Schwartz // Computational linguistics. – 2010. – Vol. 36. – No. 1. – Pages 1–30. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/coli.2010.36.1.36100#.WH6DYn3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/pdf/10.1162/coli.2010.36.1.36100
За багатьма ознаками синтаксичний аналіз, який виконується людиною, здійснюється у короткотривалій пам’яті загального призначення. Проте відомо, що цей вид пам’яті має дуже малий обсяг, можливо обмежений всього трьома або чотирма окремими елементами. У статті описано модель синтаксичного аналізу, який успішно здійснюється в рамках таких жорстких обмежень шляхом розпізнавання складників у трансформованому представленні у правому куті (різновиді синтаксичного аналізу за лівим кутом) і з’єднання цього представлення з випадковими величинами у ієрархічній прихованій марківській моделі, зваженій послідовній моделі, яка прогнозує зміст обмеженого сховища пам’яті на тривалий час. Оцінка ефективності даної моделі за допомогою великого синтаксично анотованого корпусу англійських речень, а також точність створеної на основі цієї моделі методики синтаксичного аналізу з використанням обмеженої пам’яті дозволяють уважати модель цілком реальною.
За багатьма ознаками синтаксичний аналіз, який виконується людиною, здійснюється у короткотривалій пам’яті загального призначення. Проте відомо, що цей вид пам’яті має дуже малий обсяг, можливо обмежений всього трьома або чотирма окремими елементами. У статті описано модель синтаксичного аналізу, який успішно здійснюється в рамках таких жорстких обмежень шляхом розпізнавання складників у трансформованому представленні у правому куті (різновиді синтаксичного аналізу за лівим кутом) і з’єднання цього представлення з випадковими величинами у ієрархічній прихованій марківській моделі, зваженій послідовній моделі, яка прогнозує зміст обмеженого сховища пам’яті на тривалий час. Оцінка ефективності даної моделі за допомогою великого синтаксично анотованого корпусу англійських речень, а також точність створеної на основі цієї моделі методики синтаксичного аналізу з використанням обмеженої пам’яті дозволяють уважати модель цілком реальною.
Переклад В. Коломієць
Zhang, Y. Syntactic Processing Using the Generalized Perceptron and Beam Search [Синтаксичний аналіз за допомогою універсального перцептрона і променевого пошуку] / Yue Zhang, Stephen Clark // Computational linguistics. – 2011. – Vol. 37. – No. 1. – Pages 105–151. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/coli_a_00037#.WH6EuX3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/pdf/10.1162/coli_a_00037
За допомогою загальної статистичної методики, яка складається з універсальної лінійної моделі, навченої універсальним перцептроном і універсальним декодером з променевим пошуком, досліджено низку завдань синтаксичного аналізу. Цю методику застосовано до сегментування слів, одночасного сегментування і морфологічного розмічування, синтаксичного аналізу на основі граматики залежностей і синтаксичного аналізу структури словосполучення. Обидва компоненти методики є дуже простими у концептуальному і обчислювальному планах. Декодер з променевим пошуком вимагає тільки, щоб завдання синтаксичного аналізу було розділене на послідовність рішень для того, щоб на кожній стадії процесу декодер мав можливість розглянути перші N кандидатів і згенерувати усі можливі варіанти для наступної стадії. Відразу після налаштування декодер застосовується до тренувальних даних, використовуючи несуттєві оновлення відповідно універсального перцептрону для виведення моделі. Ця проста методика є дуже ефективною і за точністю результатів співставна з результатами діючих методик для всіх завдань, які ми розглянули.
Обчислювальна простота декодера і тренувального алгоритму забезпечила значно вищу швидкість тестування і менший час тренування, ніж їх основні альтернативи, зокрема логлінійний алгоритм, навчальний алгоритм із великим ступенем свободи і динамічне програмування для декодування. Крім того, запропонований метод дозволяє визначати довільні характеристики, які можуть неприпустимо уповільнювати альтернативні алгоритми навчання і декодування. Проаналізовано застосування загального методу до кожної з досліджуваних у статті проблем у порівнянні з альтернативними алгоритмами навчання і декодування. Також показано, що важливим фактором процесу є співставність кандидатів, які аналізуються променем. Стверджується, що концептуальна і обчислювальна простота та універсальність методу роблять його вигідним варіантом для виконання низки завдань синтаксичного аналізу і методом, який повинен обиратися для порівняння розробниками альтернативних підходів.
За допомогою загальної статистичної методики, яка складається з універсальної лінійної моделі, навченої універсальним перцептроном і універсальним декодером з променевим пошуком, досліджено низку завдань синтаксичного аналізу. Цю методику застосовано до сегментування слів, одночасного сегментування і морфологічного розмічування, синтаксичного аналізу на основі граматики залежностей і синтаксичного аналізу структури словосполучення. Обидва компоненти методики є дуже простими у концептуальному і обчислювальному планах. Декодер з променевим пошуком вимагає тільки, щоб завдання синтаксичного аналізу було розділене на послідовність рішень для того, щоб на кожній стадії процесу декодер мав можливість розглянути перші N кандидатів і згенерувати усі можливі варіанти для наступної стадії. Відразу після налаштування декодер застосовується до тренувальних даних, використовуючи несуттєві оновлення відповідно універсального перцептрону для виведення моделі. Ця проста методика є дуже ефективною і за точністю результатів співставна з результатами діючих методик для всіх завдань, які ми розглянули.
Обчислювальна простота декодера і тренувального алгоритму забезпечила значно вищу швидкість тестування і менший час тренування, ніж їх основні альтернативи, зокрема логлінійний алгоритм, навчальний алгоритм із великим ступенем свободи і динамічне програмування для декодування. Крім того, запропонований метод дозволяє визначати довільні характеристики, які можуть неприпустимо уповільнювати альтернативні алгоритми навчання і декодування. Проаналізовано застосування загального методу до кожної з досліджуваних у статті проблем у порівнянні з альтернативними алгоритмами навчання і декодування. Також показано, що важливим фактором процесу є співставність кандидатів, які аналізуються променем. Стверджується, що концептуальна і обчислювальна простота та універсальність методу роблять його вигідним варіантом для виконання низки завдань синтаксичного аналізу і методом, який повинен обиратися для порівняння розробниками альтернативних підходів.
Переклад В. Коломієць
McDonald, R. Analyzing and Integrating Dependency Parsers [Аналіз і інтеграція синтаксичних аналізаторів залежностей] / Ryan McDonald, Joakim Nivre // Computational linguistics. – 2011. – Vol. 37. – No. 1. – Pр. 197–230. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/coli_a_00039#.WH6E-H3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/pdf/10.1162/coli_a_00039
За останні п'ять років значно зросла кількість досліджень синтаксичних аналізаторів на основі граматики залежностей, які навчаються на прикладах із банків синтаксичних дерев. Це зростання було спричинене доступністю банків дерев для великої кількості мов – здебільшого завдяки конкурсним завданням конференції з машинного навчання і обробки природних мов (Computational Natural Language Learning, скор. CoNLL) – і зрозумілими методами кодування складних явищ у мовах із вільним порядком слів, які використовуються у синтаксичних теоріях залежностей. Метою нашої статті є об’єктивна оцінка результатів цих досліджень шляхом аналізу двох основних парадигм синтаксичного аналізу на основі граматики залежностей, що керується даними, які часто називають синтаксичним аналізом на основі графів і синтаксичним аналізом на основі машин станів. Ми аналізуємо як теоретичні, так і емпіричні аспекти досліджень, і проливаємо світло на типи помилок, які роблять обидва типи синтаксичних аналізаторів, і їх обумовленість теоретичними припущеннями. Використовуючи ці спостереження, ми описуємо комбіновану систему на основі машинного навчання з використанням стекінгу і доводимо, що така система може навчитися позбавлятися недоліків кожної окремої системи.
За останні п'ять років значно зросла кількість досліджень синтаксичних аналізаторів на основі граматики залежностей, які навчаються на прикладах із банків синтаксичних дерев. Це зростання було спричинене доступністю банків дерев для великої кількості мов – здебільшого завдяки конкурсним завданням конференції з машинного навчання і обробки природних мов (Computational Natural Language Learning, скор. CoNLL) – і зрозумілими методами кодування складних явищ у мовах із вільним порядком слів, які використовуються у синтаксичних теоріях залежностей. Метою нашої статті є об’єктивна оцінка результатів цих досліджень шляхом аналізу двох основних парадигм синтаксичного аналізу на основі граматики залежностей, що керується даними, які часто називають синтаксичним аналізом на основі графів і синтаксичним аналізом на основі машин станів. Ми аналізуємо як теоретичні, так і емпіричні аспекти досліджень, і проливаємо світло на типи помилок, які роблять обидва типи синтаксичних аналізаторів, і їх обумовленість теоретичними припущеннями. Використовуючи ці спостереження, ми описуємо комбіновану систему на основі машинного навчання з використанням стекінгу і доводимо, що така система може навчитися позбавлятися недоліків кожної окремої системи.
Переклад М. Драчової
Gómez-Rodríguez, C. Dependency Parsing Schemata and Mildly Non-Projective Dependency Parsing [Схеми синтаксичного аналізу на основі граматики залежностей і слабо непроективний синтаксичний аналіз на основі граматики залежностей] / Carlos Gómez-Rodríguez, John Carroll, David Weir // Computational linguistics. – 2011. – Vol. 37. – No. 3. – Pages 541–586. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00060#.WH6FoH3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00060
У статті описано схему синтаксичного аналізу на основі граматики залежностей, формальний метод на основі схеми синтаксичного аналізу К. Сіккела для синтаксичних аналізаторів на основі граматики складників, яку можна використати для того, щоб описати, проаналізувати і порівняти алгоритми синтаксичного аналізу на основі граматики залежностей. Даний метод було використано для опису кількох добре відомих проективних і непроективних синтаксичних аналізаторів на основі граматики залежностей, розробки доказів правильності і встановлення формального зв’язку між ними. Потім метод було використано для визначення нових поліноміальних алгоритмів синтаксичного аналізу для різних слабо непроективних граматик залежностей, зокрема глибоко вкладених структур, величина відстані між якими обмежена константою k за час O(n5+2k), і нового класу, який включає всі k структури величини відстані, наявні у кількох банках синтаксичних дерев природніх мов (які ми називаємо недостатньо глибоко вкладеними структурами величини відстані k), за час O(n4+3k). Нарешті, проілюстровано, як можна застосувати метод на основі схеми синтаксичного аналізу до граматики зв’язків, формалізму на основі залежностей.
У статті описано схему синтаксичного аналізу на основі граматики залежностей, формальний метод на основі схеми синтаксичного аналізу К. Сіккела для синтаксичних аналізаторів на основі граматики складників, яку можна використати для того, щоб описати, проаналізувати і порівняти алгоритми синтаксичного аналізу на основі граматики залежностей. Даний метод було використано для опису кількох добре відомих проективних і непроективних синтаксичних аналізаторів на основі граматики залежностей, розробки доказів правильності і встановлення формального зв’язку між ними. Потім метод було використано для визначення нових поліноміальних алгоритмів синтаксичного аналізу для різних слабо непроективних граматик залежностей, зокрема глибоко вкладених структур, величина відстані між якими обмежена константою k за час O(n5+2k), і нового класу, який включає всі k структури величини відстані, наявні у кількох банках синтаксичних дерев природніх мов (які ми називаємо недостатньо глибоко вкладеними структурами величини відстані k), за час O(n4+3k). Нарешті, проілюстровано, як можна застосувати метод на основі схеми синтаксичного аналізу до граматики зв’язків, формалізму на основі залежностей.
Переклад В. Коломієць
Vadas, D. Parsing Noun Phrases in the Penn Treebank [Синтаксичний аналіз іменних груп у банку дерев Penn Treebank] / David Vadas, James R. Curran // Computational linguistics. – 2011. – Vol. 37. – No. 4. – Pр. 753–809. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00076#.WH6F6n3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00076
Іменні групи (ІГ) є важливою частиною природної мови і можуть мати дуже складну структуру. Проте ця структура ІГ здебільшого ігнорується у галузі статистичного синтаксичного аналізу, оскільки вони не марковані у корпусі, який використовується найчастіше. Ця відсутність золотого стандарту обмежувала попередні спроби здійснити синтаксичний аналіз ІГ, унеможливлюючи проведення контрольованих експериментів, які досягли високої ефективності у такій великій кількості завдань з обробки природної мови.
Ми повністю вирішили цю проблему шляхом ручного маркування структури ІГ у всій частині банку дерев Penn Treebank, яка складається із статей газети Wall Street Journal. Отримані нами показники міри узгодженості між маркувальниками спростовують переконання, що це занадто важке завдання, і демонструють, що послідовна розмітка ІГ можлива. Зараз наш золотий стандарт може бути використаний у всіх синтаксичних аналізаторах.
Ми експериментували з цими новими даними, використовуючи модель синтаксичного аналізу М. Коллінза [Collins, 2003], і з’ясували, що ефективність розпізнавання структури ІГ є значно нижчою, аніж загальна продуктивність моделі. F-міра цього аналізатора майже на 5,69 % нижча, аніж базового, який використовує детерміновані правила. Шляхом багатьох експериментів встановлено, що такий результат спричинений, у першу чергу, відсутністю лексичної інформації.
Щоб вирішити цю проблему, була створена широкозахватна, повномасштабна програма, яка бере ІГ у дужки. За допомогою нашої бази даних з банку дерев Penn Treebank, на кілька порядків більшої, ніж ті, що використовувалися раніше, ми створили контрольовану модель, яка демонструє чудових результатів. Наша модель має показник F-міри 93,8% при виконанні простих завдань, які виконувались у більшості попередніх досліджень, і на додаток бере у дужки довші, складніші ІГ, які рідко згадуються у літературі. Для цього складнішого завдання досягнутий показник F-міри 89,14%. Нарешті, упроваджено модель наступної обробки, яка бере у дужки ІГ, визначені аналізатором Д. Бікеля [Bikel, 2004]. Розроблена нами модель бракетування ІГ включає широкий спектр характеристик, які забезпечують лексичну інформацію, яка була відсутня у тестуваннях парсерів, і, в результаті, ми перевищуємо показник F-міри парсера 9,04%.
Вказані експерименти демонструють корисність корпусу і показують, що структура ІГ може зараз використовуватись у великій кількості програм обробки природної мови.
Іменні групи (ІГ) є важливою частиною природної мови і можуть мати дуже складну структуру. Проте ця структура ІГ здебільшого ігнорується у галузі статистичного синтаксичного аналізу, оскільки вони не марковані у корпусі, який використовується найчастіше. Ця відсутність золотого стандарту обмежувала попередні спроби здійснити синтаксичний аналіз ІГ, унеможливлюючи проведення контрольованих експериментів, які досягли високої ефективності у такій великій кількості завдань з обробки природної мови.
Ми повністю вирішили цю проблему шляхом ручного маркування структури ІГ у всій частині банку дерев Penn Treebank, яка складається із статей газети Wall Street Journal. Отримані нами показники міри узгодженості між маркувальниками спростовують переконання, що це занадто важке завдання, і демонструють, що послідовна розмітка ІГ можлива. Зараз наш золотий стандарт може бути використаний у всіх синтаксичних аналізаторах.
Ми експериментували з цими новими даними, використовуючи модель синтаксичного аналізу М. Коллінза [Collins, 2003], і з’ясували, що ефективність розпізнавання структури ІГ є значно нижчою, аніж загальна продуктивність моделі. F-міра цього аналізатора майже на 5,69 % нижча, аніж базового, який використовує детерміновані правила. Шляхом багатьох експериментів встановлено, що такий результат спричинений, у першу чергу, відсутністю лексичної інформації.
Щоб вирішити цю проблему, була створена широкозахватна, повномасштабна програма, яка бере ІГ у дужки. За допомогою нашої бази даних з банку дерев Penn Treebank, на кілька порядків більшої, ніж ті, що використовувалися раніше, ми створили контрольовану модель, яка демонструє чудових результатів. Наша модель має показник F-міри 93,8% при виконанні простих завдань, які виконувались у більшості попередніх досліджень, і на додаток бере у дужки довші, складніші ІГ, які рідко згадуються у літературі. Для цього складнішого завдання досягнутий показник F-міри 89,14%. Нарешті, упроваджено модель наступної обробки, яка бере у дужки ІГ, визначені аналізатором Д. Бікеля [Bikel, 2004]. Розроблена нами модель бракетування ІГ включає широкий спектр характеристик, які забезпечують лексичну інформацію, яка була відсутня у тестуваннях парсерів, і, в результаті, ми перевищуємо показник F-міри парсера 9,04%.
Вказані експерименти демонструють корисність корпусу і показують, що структура ІГ може зараз використовуватись у великій кількості програм обробки природної мови.
Переклад В. Коломієць
Nederhof, M. Splittability of Bilexical Context-Free Grammars is Undecidable [Розщеплюваність білексичних контекстно-незалежних граматик є нерозв’язною] / Mark-Jan Nederhof, Giorgio Satta // Computational linguistics. – 2011. – Vol. 37. – No. 4. – Pages 867–879. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00079#.WH6GNX3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00079
Білексичні контекстно-незалежні граматики виявилися точними моделями для статистичного синтаксичного аналізу природної мови. Час обробки за допомогою існуючих алгоритмів динамічного програмування, які використовуються для синтаксичного розбору речень на основі цих моделей, складає О(w4), де w є строкою вводу.
Білексична контекстно-незалежна граматика є розщеплюваною, якщо ліві аргументи вершини завжди незалежні від правих аргументів і навпаки. Коли білексична контекстно-незалежна граматика є розщеплюваною, швидкість синтаксичного розбору можна асимптотично поліпшити до О(w3). Отже, дослідження цієї характеристики має надзвичайно важливе значення для ефективності синтаксичного аналізу. Але у статті показано негативний результат: розщеплюваність білексичних контекстно-незалежних граматик є нерозв’язною.
Білексичні контекстно-незалежні граматики виявилися точними моделями для статистичного синтаксичного аналізу природної мови. Час обробки за допомогою існуючих алгоритмів динамічного програмування, які використовуються для синтаксичного розбору речень на основі цих моделей, складає О(w4), де w є строкою вводу.
Білексична контекстно-незалежна граматика є розщеплюваною, якщо ліві аргументи вершини завжди незалежні від правих аргументів і навпаки. Коли білексична контекстно-незалежна граматика є розщеплюваною, швидкість синтаксичного розбору можна асимптотично поліпшити до О(w3). Отже, дослідження цієї характеристики має надзвичайно важливе значення для ефективності синтаксичного аналізу. Але у статті показано негативний результат: розщеплюваність білексичних контекстно-незалежних граматик є нерозв’язною.
Переклад В. Коломієць
Roark, B. Finite-State Chart Constraints for Reduced Complexity Context-Free Parsing Pipelines [Скінченні табличні обмеження для спрощення конвейерного контекстно-незалежного синтаксичного аналізу] / Brian Roark, Kristy Hollingshead, Nathan Bodenstab // Computational linguistics. – 2012. – Vol. 38. – No. 4. – Pр. 719–753. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00109#.WH6HQX3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00109
Ми описуємо методи зменшення найбільших і типових труднощів конвейерного контекстно-незалежного синтаксичного аналізу завдяки жорстким обмеженням, визначеним під час кінцевої попередньої обробки. Ми робили O(n) прогнозів, щоб визначити, починає чи закінчує кожне слово вхідного речення у комірках таблиць багатослівний складник з двох або більше слів або чи допускає воно у комірках таблиць однослівні складники, представлені самим словом. Такі обмеження попередньої обробки прискорюють пошук будь-якого алгоритму синтаксичного аналізу на основі таблиць і істотно скорочують час декодування. У багатьох випадках, які ми назвали «закриттям» комірки таблиці, наповнення комірок зменшилося до нуля. Ми описуємо методи закриття достатньої кількості комірок таблиць для забезпечення переконливої квадратичної або навіть лінійної найбільшої проблеми контекстно-незалежного висновку. Крім того, ми використовуємо високоточні обмеження для досягнення значних стандартних прискорень і об'єднуємо обмеження високої точності та обмеження для найскладніших проблем, щоб досягти найкращих результатів при обробці як коротких, так і довгих послідовностей. Такі обмеження обробки досягаються без зменшення точності обробки, а в деяких випадках точність підвищується. Ми показуємо, що наш метод підходить для численних граматик і є додатковим для інших методів скорочення, описуючи емпіричні результати як для точного, так і для приблизного висновку завдяки вичерпному алгоритму Кока — Янгера — Касамі, синтаксичному аналізатору Чарняка і берклійському синтаксичному аналізатору. Ми також повідомляємо результати аналізу китайської мови, де ми досягли найкращих зафіксованих результатів для окремої моделі на часто згадуваному наборі даних.
Ми описуємо методи зменшення найбільших і типових труднощів конвейерного контекстно-незалежного синтаксичного аналізу завдяки жорстким обмеженням, визначеним під час кінцевої попередньої обробки. Ми робили O(n) прогнозів, щоб визначити, починає чи закінчує кожне слово вхідного речення у комірках таблиць багатослівний складник з двох або більше слів або чи допускає воно у комірках таблиць однослівні складники, представлені самим словом. Такі обмеження попередньої обробки прискорюють пошук будь-якого алгоритму синтаксичного аналізу на основі таблиць і істотно скорочують час декодування. У багатьох випадках, які ми назвали «закриттям» комірки таблиці, наповнення комірок зменшилося до нуля. Ми описуємо методи закриття достатньої кількості комірок таблиць для забезпечення переконливої квадратичної або навіть лінійної найбільшої проблеми контекстно-незалежного висновку. Крім того, ми використовуємо високоточні обмеження для досягнення значних стандартних прискорень і об'єднуємо обмеження високої точності та обмеження для найскладніших проблем, щоб досягти найкращих результатів при обробці як коротких, так і довгих послідовностей. Такі обмеження обробки досягаються без зменшення точності обробки, а в деяких випадках точність підвищується. Ми показуємо, що наш метод підходить для численних граматик і є додатковим для інших методів скорочення, описуючи емпіричні результати як для точного, так і для приблизного висновку завдяки вичерпному алгоритму Кока — Янгера — Касамі, синтаксичному аналізатору Чарняка і берклійському синтаксичному аналізатору. Ми також повідомляємо результати аналізу китайської мови, де ми досягли найкращих зафіксованих результатів для окремої моделі на часто згадуваному наборі даних.
Переклад М. Драчової
Ballesteros, M. Going to the Roots of Dependency Parsing [Звернення до коренів синтаксичного аналізу на основі граматики залежностей] / Miguel Ballesteros, Joakim Nivre // Computational linguistics. – 2013. – Vol. 39. – No. 1. – Pр. 5–13. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00132#.WH6H4X3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00132
Дерева залежностей, які використовуються у синтаксичному аналізі, часто включають корінь, представлений у вигляді пустого слова, приєднаного до початку або кінця речення, засобу, який зазвичай вважається звичайним технічим прийомом і не впливає на емпіричні результати. Ми показали, що це припущення є хибним і що точність керованих даними синтаксичних аналізаторів на основі дерев залежностей насправді може залежати від наявності й розташування пустого кореня. Зокрема, ми продемонстрували, що жадібний дугоспрямований синтаксичний аналізатор на основі машин станів, який здійснює обробку зліва направо, завжди працює гірше, коли пустий корінь розташований на початку речення (як прийнято зараз у керованому даними синтаксичному аналізі на основі дерев залежноестей), ніж коли він розташований у кінці або відсутній. Контрольні експерименти із дуговим синтаксичним аналізатором на основі машин станів і аналізатором на основі графу не виявили постійних преференцій, але, тим не менш, показали, що розташування кореня суттєво впливає на результати. Ми зробили висновок, що розташування пустих кореневих вузлів у керованому даними синтаксичному аналізі на основі дерев залежностей є недооціненим джерелом розбіжностей у експериментах і також може бути параметром, який потрібно налаштовувати для деяких синтаксичних аналізаторів.
Дерева залежностей, які використовуються у синтаксичному аналізі, часто включають корінь, представлений у вигляді пустого слова, приєднаного до початку або кінця речення, засобу, який зазвичай вважається звичайним технічим прийомом і не впливає на емпіричні результати. Ми показали, що це припущення є хибним і що точність керованих даними синтаксичних аналізаторів на основі дерев залежностей насправді може залежати від наявності й розташування пустого кореня. Зокрема, ми продемонстрували, що жадібний дугоспрямований синтаксичний аналізатор на основі машин станів, який здійснює обробку зліва направо, завжди працює гірше, коли пустий корінь розташований на початку речення (як прийнято зараз у керованому даними синтаксичному аналізі на основі дерев залежноестей), ніж коли він розташований у кінці або відсутній. Контрольні експерименти із дуговим синтаксичним аналізатором на основі машин станів і аналізатором на основі графу не виявили постійних преференцій, але, тим не менш, показали, що розташування кореня суттєво впливає на результати. Ми зробили висновок, що розташування пустих кореневих вузлів у керованому даними синтаксичному аналізі на основі дерев залежностей є недооціненим джерелом розбіжностей у експериментах і також може бути параметром, який потрібно налаштовувати для деяких синтаксичних аналізаторів.
Переклад І. Снєгурова
Tsarfaty, R. Parsing Morphologically Rich Languages: Introduction to the Special Issue [Автоматичний синтаксичний аналіз мов із розвиненою морфологією: передмова до спеціального випуску] / Reut Tsarfaty, Djamé Seddah, Sandra Kübler, Joakim Nivre // Computational linguistics. – 2013. – Vol. 39. – No. 1. – Pages 15–22. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00133#.WH6IF33sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00133
Автоматичний синтаксичний аналіз є головним завданням обробки природної мови. Він включає визначення для кожного речення природною мовою абстрактного представлення граматичних об’єктів у реченні і взаємовідносин між цими об’єктами. Це представлення забезпечує зв’язок з композиційною семантикою і з поняттями «хто кому що зробив». Протягом останніх двох десятиліть було досягнуто значних успіхів у автоматичному синтаксичному аналізі англійської мови, які призвели до значного покращення якості програм, основною частиною яких є синтаксичні аналізатори, таких як системи видобування інформації, аналізу тональності, реферування і машинного перекладу. Спроби відтворити успіх автоматичного синтаксичного аналізу англійської мови для других мов часто давали незадовільні результати. Зокрема, з’ясувалось, що автоматичний синтаксичний аналіз мов із складною будовою слова і вільним порядком слів потребує значної адаптації. У цьому спеціальному випуску повідомляється про методи успішного вирішення проблем, пов’язаних із синтаксичним аналізом різних мов із розвиненою морфологією. У передмові дається характеристика мов із розвиненою морфологією, описуються проблеми автоматичного синтаксичного аналізу мов із розвиненою морфологією і окреслюється основний зміст статей у спеціальному випуску. У статтях описано останні дослідження, присвячені автоматичному синтаксичному аналізу у різних міжмовних середовищах. Вони свідчать, що автоматичний синтаксичний аналіз мов із розвиненою морфологією стикається з проблемами, які виходять за рамки вибору конкретної репрезентації і алгоритму.
Автоматичний синтаксичний аналіз є головним завданням обробки природної мови. Він включає визначення для кожного речення природною мовою абстрактного представлення граматичних об’єктів у реченні і взаємовідносин між цими об’єктами. Це представлення забезпечує зв’язок з композиційною семантикою і з поняттями «хто кому що зробив». Протягом останніх двох десятиліть було досягнуто значних успіхів у автоматичному синтаксичному аналізі англійської мови, які призвели до значного покращення якості програм, основною частиною яких є синтаксичні аналізатори, таких як системи видобування інформації, аналізу тональності, реферування і машинного перекладу. Спроби відтворити успіх автоматичного синтаксичного аналізу англійської мови для других мов часто давали незадовільні результати. Зокрема, з’ясувалось, що автоматичний синтаксичний аналіз мов із складною будовою слова і вільним порядком слів потребує значної адаптації. У цьому спеціальному випуску повідомляється про методи успішного вирішення проблем, пов’язаних із синтаксичним аналізом різних мов із розвиненою морфологією. У передмові дається характеристика мов із розвиненою морфологією, описуються проблеми автоматичного синтаксичного аналізу мов із розвиненою морфологією і окреслюється основний зміст статей у спеціальному випуску. У статтях описано останні дослідження, присвячені автоматичному синтаксичному аналізу у різних міжмовних середовищах. Вони свідчать, що автоматичний синтаксичний аналіз мов із розвиненою морфологією стикається з проблемами, які виходять за рамки вибору конкретної репрезентації і алгоритму.
Переклад В. Коломієць
Seeker, W. Morphological and Syntactic Case in Statistical Dependency Parsing [Морфологічні і синтаксичні відмінки у статистичному синтаксичному аналізі на основі дерев залежностей] / Wolfgang Seeker, Jonas Kuhn // Computational linguistics. – 2013. – Vol. 39. – No. 1. – Pр. 23–55. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00134#.WH6JL33sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00134
Більшість морфологічно багатих мов із вільним порядком слів використовують системи відмінків для позначення граматичної функції іменних елементів, особливо основних аргументів дієслова. Стандартний поетапний підхід до синтаксичного аналізу на основі дерев залежностей передбачає повне зняття морфологічної (відмінкової) омонімії до здійснення автоматичного синтаксичного аналізу. Експериментальний синтаксичний аналіз чеської, німецької та угорської мов показав, що цей підхід може привести до помилок у морфологічній розмітці під час синтаксичного аналізу мов, для яких характерний синкретизм у морфологічних відмінкових парадигмах. Ми розробили іншу модель, у якій відмінок використовується як можливо недостатньо визначений фільтруючий механізм, що обмежує варіанти синтаксичного аналізу. Ретельно розроблені морфо-синтаксичні обмеження можуть обмежити пошуковий простір статистичного синтаксичного аналізатора на основі дерев залежностей і виключати рішення, які порушили б обмеження, явно зазначені у частиномовній приналежності слів у даному реченні. Ми експериментально доводимо, що обмежена система перевершує найсучаснішу поетапну модель на основі даних, а, також, що вивід синтаксичного аналізатора є гарантовано вільним від локальних і глобальних морфо-синтаксичних помилок, що може бути корисним для наступних прикладних програм.
Більшість морфологічно багатих мов із вільним порядком слів використовують системи відмінків для позначення граматичної функції іменних елементів, особливо основних аргументів дієслова. Стандартний поетапний підхід до синтаксичного аналізу на основі дерев залежностей передбачає повне зняття морфологічної (відмінкової) омонімії до здійснення автоматичного синтаксичного аналізу. Експериментальний синтаксичний аналіз чеської, німецької та угорської мов показав, що цей підхід може привести до помилок у морфологічній розмітці під час синтаксичного аналізу мов, для яких характерний синкретизм у морфологічних відмінкових парадигмах. Ми розробили іншу модель, у якій відмінок використовується як можливо недостатньо визначений фільтруючий механізм, що обмежує варіанти синтаксичного аналізу. Ретельно розроблені морфо-синтаксичні обмеження можуть обмежити пошуковий простір статистичного синтаксичного аналізатора на основі дерев залежностей і виключати рішення, які порушили б обмеження, явно зазначені у частиномовній приналежності слів у даному реченні. Ми експериментально доводимо, що обмежена система перевершує найсучаснішу поетапну модель на основі даних, а, також, що вивід синтаксичного аналізатора є гарантовано вільним від локальних і глобальних морфо-синтаксичних помилок, що може бути корисним для наступних прикладних програм.
Переклад В. Туз
Fraser, A. Knowledge Sources for Constituent Parsing of German, a Morphologically Rich and Less-Configurational Language [Набори правил і процедур для заснованого на складниках синтаксичного аналізу німецької мови, морфологічно багатої мови з менш усталеним порядком слів] / Alexander Fraser, Helmut Schmid, Richárd Farkas, Renjing Wang, Hinrich Schütze // Computational linguistics. – 2013. – Vol. 39. – No. 1. – Pр. 57–85. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00135#.WH6Ji33sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00135
Досліджувався синтаксичний аналіз на основі складників німецької мови, яка є морфологічно багатою мовою з менш усталеним порядком слів. Використовувалась імовірнісна контекстно-вільна граматика на основі банку дерев, адаптована до числених морфологічних особливостей німецької мови шляхом марковізації і додавання спеціальних характеристик до її продукцій. Здійснена оцінка результативності додавання лексичної інформації. Також проаналізовано як монолінгвальний, так і білінгвальний підходи до переранжування розбору. Запропонована система переранжування є новою найсучаснішою системою у заснованому на складниках синтаксичному аналізі банку дерев Tiger. Здійснено аналіз, який завершується висновками, що стосуються синтаксичного аналізу інших морфологічно багатих мов з менш усталеним порядком слів.
Досліджувався синтаксичний аналіз на основі складників німецької мови, яка є морфологічно багатою мовою з менш усталеним порядком слів. Використовувалась імовірнісна контекстно-вільна граматика на основі банку дерев, адаптована до числених морфологічних особливостей німецької мови шляхом марковізації і додавання спеціальних характеристик до її продукцій. Здійснена оцінка результативності додавання лексичної інформації. Також проаналізовано як монолінгвальний, так і білінгвальний підходи до переранжування розбору. Запропонована система переранжування є новою найсучаснішою системою у заснованому на складниках синтаксичному аналізі банку дерев Tiger. Здійснено аналіз, який завершується висновками, що стосуються синтаксичного аналізу інших морфологічно багатих мов з менш усталеним порядком слів.
Переклад В. Коломієць
Kallmeyer, L. Data-Driven Parsing using Probabilistic Linear Context-Free Rewriting Systems [Керований даними синтаксичний аналіз за допомогою імовірнісних лінійних контекстно-незалежних систем переписування] / Laura Kallmeyer, Wolfgang Maier // Computational linguistics. – 2013. – Vol. 39. – No. 1. – Pр. 87–119. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00136#.WH6Jwn3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00136
У статті представлена перша ефективна реалізація виваженого дедуктивного синтаксичного аналізатора на основі алгоритму Кока — Янгера — Касамі для імовірнісних лінійних контекстно-незалежних систем переписування (Probabilistic Linear Context-Free Rewriting System — PLCFRS). Лінійна контекстно-незалежна система переписування (LCFRS), розширення контекстно-незалежної граматики (Context-Free Grammar — CFG), може ефективно описувати порушення однорідності і тому ідеально підходить для використання у синтаксичному аналізі, який керується даними. Для прискорення процесу синтаксичного аналізу ми використовували різні розрахунки об’єктів аналізу на основі контексту, деякі з яких допускали синтаксичний аналіз А*. Аналізатор тестувався за допомогою граматик, отриманих із німецького банку дерев NeGra. Наші експерименти свідчать, що керований даними синтаксичний аналіз для лінійної контекстно-незалежної системи переписування є здійснимим і дає результати конкурентоспроможної якості.
У статті представлена перша ефективна реалізація виваженого дедуктивного синтаксичного аналізатора на основі алгоритму Кока — Янгера — Касамі для імовірнісних лінійних контекстно-незалежних систем переписування (Probabilistic Linear Context-Free Rewriting System — PLCFRS). Лінійна контекстно-незалежна система переписування (LCFRS), розширення контекстно-незалежної граматики (Context-Free Grammar — CFG), може ефективно описувати порушення однорідності і тому ідеально підходить для використання у синтаксичному аналізі, який керується даними. Для прискорення процесу синтаксичного аналізу ми використовували різні розрахунки об’єктів аналізу на основі контексту, деякі з яких допускали синтаксичний аналіз А*. Аналізатор тестувався за допомогою граматик, отриманих із німецького банку дерев NeGra. Наші експерименти свідчать, що керований даними синтаксичний аналіз для лінійної контекстно-незалежної системи переписування є здійснимим і дає результати конкурентоспроможної якості.
Переклад М. Драчової
Goldberg, Y. Word Segmentation, Unknown-word Resolution, and Morphological Agreement in a Hebrew Parsing System [Сегментування слів, розпізнавання незнайомих слів і морфологічне узгодження у синтаксичному аналізаторі івриту] / Yoav Goldberg, Michael Elhadad // Computational linguistics. – 2013. – Vol. 39. – No. 1. – Pр. 121–160. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00137#.WH6KBX3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00137
У статті описано систему синтаксичного аналізу на основі граматики складників для сучасного івриту. Система заснована на запропонованому С. Петровим та ін. (Petrov et al., 2006) методі синтаксичного аналізу на основі імовірнісної контекстно-незалежної граматики з прихованими анотаціями (Probabilistic Context-Free Grammar With Latent Annotations, скор. PCFG-LA), який зазнав різноманітних уточнень з метою врахування особливостей івриту як морфологічно багатої мови з невеликим банком дерев. Ми показуємо, що результати синтаксичного аналізу можна поліпшити завдяки використанню лінгвістичного ресурсу, відмінного від банку дерев, а саме морфологічного аналізатора на основі лексикону. Ми описуємо комбіновану обчислювальну модель зовнішнього лексикону і синтаксичного аналізатора на основі банку дерев, також у типовому випадку, коли у лексиконі і банку дерев використовуються різні схеми анотування. Ми показуємо, що можна одночасно здійснювати сегментування слів івриту і синтаксичний аналіз на основі граматики складників, використовуючи ґратчастий синтаксичний аналіз на основі алгоритму Кока — Янгера — Касамі. Одночасне виконання завдань ефективне і істотно перевершує показники конвейерної моделі. Ми пропонуємо моделювати граматичне узгодження у синтаксичному аналізаторі на основі граматики складників як ортогональний граматиці механізм фільтра і представляємо конкретну реалізацію цього методу. Хоча синтаксичний аналізатор на основі граматики складників не робить великої кількості помилок в узгодженні, механізм фільтра ефективно виправляє ті помилки узгодження, які аналізатор таки допускає.
Отримані результати виходять за рамки обробки івриту і можуть бути широко застосовані у обробці природної мови. Іврит є конкретним прикладом морфологічно багатої мови і ідеї, висунуті у цій роботі, також корисні для обробки інших мов, зокрема англійської. Методика ґратчастого синтаксичного аналізу корисна у будь-яких випадках, коли інформація на вході неоднозначна. Розширення лексичного покриття синтаксичного аналізатора на основі банку дерев завдяки використанню зовнішнього лексикону потрібне для будь-якої мови із невеликим банком дерев.
У статті описано систему синтаксичного аналізу на основі граматики складників для сучасного івриту. Система заснована на запропонованому С. Петровим та ін. (Petrov et al., 2006) методі синтаксичного аналізу на основі імовірнісної контекстно-незалежної граматики з прихованими анотаціями (Probabilistic Context-Free Grammar With Latent Annotations, скор. PCFG-LA), який зазнав різноманітних уточнень з метою врахування особливостей івриту як морфологічно багатої мови з невеликим банком дерев. Ми показуємо, що результати синтаксичного аналізу можна поліпшити завдяки використанню лінгвістичного ресурсу, відмінного від банку дерев, а саме морфологічного аналізатора на основі лексикону. Ми описуємо комбіновану обчислювальну модель зовнішнього лексикону і синтаксичного аналізатора на основі банку дерев, також у типовому випадку, коли у лексиконі і банку дерев використовуються різні схеми анотування. Ми показуємо, що можна одночасно здійснювати сегментування слів івриту і синтаксичний аналіз на основі граматики складників, використовуючи ґратчастий синтаксичний аналіз на основі алгоритму Кока — Янгера — Касамі. Одночасне виконання завдань ефективне і істотно перевершує показники конвейерної моделі. Ми пропонуємо моделювати граматичне узгодження у синтаксичному аналізаторі на основі граматики складників як ортогональний граматиці механізм фільтра і представляємо конкретну реалізацію цього методу. Хоча синтаксичний аналізатор на основі граматики складників не робить великої кількості помилок в узгодженні, механізм фільтра ефективно виправляє ті помилки узгодження, які аналізатор таки допускає.
Отримані результати виходять за рамки обробки івриту і можуть бути широко застосовані у обробці природної мови. Іврит є конкретним прикладом морфологічно багатої мови і ідеї, висунуті у цій роботі, також корисні для обробки інших мов, зокрема англійської. Методика ґратчастого синтаксичного аналізу корисна у будь-яких випадках, коли інформація на вході неоднозначна. Розширення лексичного покриття синтаксичного аналізатора на основі банку дерев завдяки використанню зовнішнього лексикону потрібне для будь-якої мови із невеликим банком дерев.
Переклад М. Драчової
Marton, Y. Dependency Parsing of Modern Standard Arabic with Lexical and Inflectional Features [Синтаксичний аналіз сучасної літературної арабської мови на основі граматики залежностей за допомогою лексичних і флексійних характеристик] / Yuval Marton, Nizar Habash, Owen Rambow // Computational linguistics. – 2013. – Vol. 39. – No. 1. – Pр. 161–194. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00138#.WH6Hj33sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00138
Ми досліджували вплив особливостей лексичної і флективної морфології на синтаксичний аналіз на основі граматики залежностей арабської мови, морфологічно багатої мови зі складними моделями узгодження. Використовуючи контрольовані експерименти, ми співставили використання різних наборів частиномовних тегів і морфологічних характеристик у двох вхідних станах: машинно-передбаченому стані (у якому частиномовні теги і значення морфологічних характеристик присвоюються автоматично) і золотому стані (в якому їх справжні значення відомі). Ми з’ясували, що більш інформативні (точні) набори тегів корисні у золотому стані, але можуть бути згубними у машинно-передбаченому стані, у якому більш ефективними є прості, але точніше передбачені теги. Ми визначили набір характеристик (означеність, особа, число, рід і неогласована лема), який покращує якість синтаксичного аналізу у машинно-передбаченому стані, в той час як інші характеристики корисніші у золотому стані. Ми вперше продемонстрували, що у синтаксичному аналізі корисніші функціональні характеристики роду і числа (наприклад, «ламана множина») і, можливо, близька характеристика розумності («людськості»), аніж форми роду і числа. Нарешті, ми довели, що якість синтаксичного аналізу в передбаченому стані можна значно покращити навчанням у комбінованому золотому+передбаченому стані. Ми експериментували з двома синтаксичними аналізаторами, які працюють на основі машин станів, MaltParser і Easy-First Parser. Наші висновки стабільні і не залежать від аналізаторів, моделей і вхідних станів. Це наводить на думку, що вплив лінгвістичної теорії у формі наборів тегів і виділених нами характеристик не обмежений рамками конкретних експериментальних досліджень і може бути корисним для інших синтаксичних аналізаторів і морфологічно багатих мов.
Ми досліджували вплив особливостей лексичної і флективної морфології на синтаксичний аналіз на основі граматики залежностей арабської мови, морфологічно багатої мови зі складними моделями узгодження. Використовуючи контрольовані експерименти, ми співставили використання різних наборів частиномовних тегів і морфологічних характеристик у двох вхідних станах: машинно-передбаченому стані (у якому частиномовні теги і значення морфологічних характеристик присвоюються автоматично) і золотому стані (в якому їх справжні значення відомі). Ми з’ясували, що більш інформативні (точні) набори тегів корисні у золотому стані, але можуть бути згубними у машинно-передбаченому стані, у якому більш ефективними є прості, але точніше передбачені теги. Ми визначили набір характеристик (означеність, особа, число, рід і неогласована лема), який покращує якість синтаксичного аналізу у машинно-передбаченому стані, в той час як інші характеристики корисніші у золотому стані. Ми вперше продемонстрували, що у синтаксичному аналізі корисніші функціональні характеристики роду і числа (наприклад, «ламана множина») і, можливо, близька характеристика розумності («людськості»), аніж форми роду і числа. Нарешті, ми довели, що якість синтаксичного аналізу в передбаченому стані можна значно покращити навчанням у комбінованому золотому+передбаченому стані. Ми експериментували з двома синтаксичними аналізаторами, які працюють на основі машин станів, MaltParser і Easy-First Parser. Наші висновки стабільні і не залежать від аналізаторів, моделей і вхідних станів. Це наводить на думку, що вплив лінгвістичної теорії у формі наборів тегів і виділених нами характеристик не обмежений рамками конкретних експериментальних досліджень і може бути корисним для інших синтаксичних аналізаторів і морфологічно багатих мов.
Переклад М. Драчової
Green, S. Parsing Models for Identifying Multiword Expressions [Моделі синтаксичного аналізу для розпізнавання багатослівних виразів] / Spence Green, Marie-Catherine de Marneffe, Christopher D. Manning // Computational linguistics. – 2013. – Vol. 39. – No. 1. – Pр. 195–227. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00139#.WH6KW33sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00139
Багатослівні вирази знаходяться на межі синтаксису і семантики і є причиною появи альтернативних теорій синтаксису, наприклад конструкційної граматики. Проте у обробці природної мови синтаксичний аналіз і розпізнавання багатослівних виразів досі моделювались окремо. Ми розробили дві структуровані прогностичні моделі для одночасного синтаксичного аналізу і розпізнавання багатослівних виразів. Перша заснована на контекстно-вільних граматиках, а друга використовує граматики заміщення дерев, формалізм, що дозволяє зберігати синтаксичні фрагменти більшого обсягу. Наші експерименти показують, що обидві моделі можуть розпізнавати багатослівні вирази набагато точніше, ніж найсучасніша система, заснована на статистичних даних про спільну появу слів.
Ми експериментували з арабською та французькою мовами, для кожної з яких характерні багатослівні вирази. На відміну від англійської мови, вони також мають багатшу морфологію, яка є причиною лексичної розрідженості у обмежених корпусах. Щоб подолати цю розрідженість, ми розробили просте факторне лексичне представлення контекстно-вільної моделі синтаксичного аналізу. Результати морфологічного аналізу автоматично перетворюються на теги з великою кількістю характеристик, прикріплені до лексичних одиниць. Цей метод, який ми називаємо факторною лексикою, покращує як точність стандартного синтаксичного аналізу, так і точність розпізнавання багатослівних виразів.
Багатослівні вирази знаходяться на межі синтаксису і семантики і є причиною появи альтернативних теорій синтаксису, наприклад конструкційної граматики. Проте у обробці природної мови синтаксичний аналіз і розпізнавання багатослівних виразів досі моделювались окремо. Ми розробили дві структуровані прогностичні моделі для одночасного синтаксичного аналізу і розпізнавання багатослівних виразів. Перша заснована на контекстно-вільних граматиках, а друга використовує граматики заміщення дерев, формалізм, що дозволяє зберігати синтаксичні фрагменти більшого обсягу. Наші експерименти показують, що обидві моделі можуть розпізнавати багатослівні вирази набагато точніше, ніж найсучасніша система, заснована на статистичних даних про спільну появу слів.
Ми експериментували з арабською та французькою мовами, для кожної з яких характерні багатослівні вирази. На відміну від англійської мови, вони також мають багатшу морфологію, яка є причиною лексичної розрідженості у обмежених корпусах. Щоб подолати цю розрідженість, ми розробили просте факторне лексичне представлення контекстно-вільної моделі синтаксичного аналізу. Результати морфологічного аналізу автоматично перетворюються на теги з великою кількістю характеристик, прикріплені до лексичних одиниць. Цей метод, який ми називаємо факторною лексикою, покращує як точність стандартного синтаксичного аналізу, так і точність розпізнавання багатослівних виразів.
Переклад М. Драчової
Gómez-Rodríguez, C. Divisible Transition Systems and Multiplanar Dependency Parsing [Ділимі системи переходів і мультипланарний синтаксичний аналіз на основі дерев залежностей] / Carlos Gómez-Rodríguez, Joakim Nivre // Computational linguistics. – 2013. – Vol. 39. – No. 4. – Pр. 799–845. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00150#.WH6LCH3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00150
Синтаксичний аналіз на основі машин станів є популярним підходом у синтаксичному аналізі на основі дерев залежностей, який забезпечує високу ефективність вузькоспеціалізованих аналізаторів. Існує багато різних аналізаторів на основі машин станів, часто формалізованих в рамках дещо різних теорій. У статті показано, що велику кількість відомих систем проективного синтаксичного аналізу на основі дерев залежностей можна розглядати як варіанти однієї стекової системи з невеликим набором елементарних переходів, які можуть бути об'єднані у складні переходи і обмежені різними способами. Ми називаємо такі системи стековими системами переходів і підтверджуємо велику кількість теоретичних висновків стосовно їх точності та складності. Зокрема, ми описуємо важливий підклас, відомий як ефективні ділимі системи переходів, які аналізують планарні графи залежностей у лінійному часі. Далі ми показуємо, по-перше, як можна обмежити цю систему, щоб вона аналізувала саме набір планарних дерев залежностей, і по-друге, як можна узагальнити цю систему до k-планарних дерев, використовуючи численні стеки. Використовуючи перший відомий ефективний тест k-планарності, ми досліджуємо, як система знаходить k-планарні дерева у доступних банках дерев і виявили, що вона дуже добре працює з 2-планарними деревами. В кінці ми здійснюємо експериментальну перевірку і показуємо, що наш 2-планарний синтаксичний аналізатор дозволяє досягти істотного поліпшення якості синтаксичного аналізу у порівнянні з відповідними 1-планарним і проективним синтаксичними аналізаторами для масивів даних із непроективними деревами залежностей і працює нарівні з широко використовуваним дугоспрямованим псевдопроективним синтаксичним аналізатором.
Синтаксичний аналіз на основі машин станів є популярним підходом у синтаксичному аналізі на основі дерев залежностей, який забезпечує високу ефективність вузькоспеціалізованих аналізаторів. Існує багато різних аналізаторів на основі машин станів, часто формалізованих в рамках дещо різних теорій. У статті показано, що велику кількість відомих систем проективного синтаксичного аналізу на основі дерев залежностей можна розглядати як варіанти однієї стекової системи з невеликим набором елементарних переходів, які можуть бути об'єднані у складні переходи і обмежені різними способами. Ми називаємо такі системи стековими системами переходів і підтверджуємо велику кількість теоретичних висновків стосовно їх точності та складності. Зокрема, ми описуємо важливий підклас, відомий як ефективні ділимі системи переходів, які аналізують планарні графи залежностей у лінійному часі. Далі ми показуємо, по-перше, як можна обмежити цю систему, щоб вона аналізувала саме набір планарних дерев залежностей, і по-друге, як можна узагальнити цю систему до k-планарних дерев, використовуючи численні стеки. Використовуючи перший відомий ефективний тест k-планарності, ми досліджуємо, як система знаходить k-планарні дерева у доступних банках дерев і виявили, що вона дуже добре працює з 2-планарними деревами. В кінці ми здійснюємо експериментальну перевірку і показуємо, що наш 2-планарний синтаксичний аналізатор дозволяє досягти істотного поліпшення якості синтаксичного аналізу у порівнянні з відповідними 1-планарним і проективним синтаксичними аналізаторами для масивів даних із непроективними деревами залежностей і працює нарівні з широко використовуваним дугоспрямованим псевдопроективним синтаксичним аналізатором.
Переклад М. Драчової
Henderson, J. Multilingual Joint Parsing of Syntactic and Semantic Dependencies with a Latent Variable Model [Багатомовний об’єднаний синтаксичний аналіз синтаксичних і семантичних залежностей за допомогою моделі з прихованою змінною] / James Henderson, Paola Merlo, Ivan Titov, Gabriele Musillo // Computational linguistics. – 2013. – Vol. 39. – No. 4. – Pр. 949–998. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00158#.WH6LSH3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00158
Сучасні дослідження моделей синтаксичного аналізу, керованих даними, перейшли від виключно синтаксичного аналізу до інтенсивніших семантичних представлень, показуючи, що успішне розуміння смислу тексту вимагає структурованого аналізу як його граматики, так і його семантики. У статті повідомляється про об’єднану породжувальну модель на основі передісторії для прогнозування найвірогіднішого дерева виведення синтаксичного аналізатора на основі дерев залежностей як для синтаксичних, так і для семантичних залежностей у різних мовах. Оскільки ці дві структури залежностей не ізоморфні, ми пропонуємо слабку синхронизацію на рівні значущих підпослідовностей двох дерев виведення. Ці синхронізовані підпослідовності містять інформацію про ліве оточення кожного окремого слова. Ми також пропонуємо інноваційні виведення семантичних структур залежностей, які відповідають відносно вільній природі цих графів. Для навчання об’єднаної моделі цих синхронизованих виведень ми використовуємо модель синтаксичного аналізу із прихованою змінною – модель Incremental Sigmoid Belief Network (ISBN). Ця модель продукує представлення прихованих властивостей у деревах виведень, які використовуються для виявлення взаємозв’язків як усередині двох дерев виведення, так і між ними, вперше використовуючи ISBN для розв’язання проблеми багатозадачного навчання. Ця об’єднана модель демонструє конкурентноздатний рівень як синтаксичного, так і семантичного аналізу різних мов. Завдяки загальному характеру нашого методу, вказане застосування моделі ISBN для аналізу слабо синхронізованих синтактико-семантичних дерев виведення також свідчить про можливість її застосування для вирішення інших проблем, коли йдеться про опанування двома незалежними, але спорідненими представленнями.
Сучасні дослідження моделей синтаксичного аналізу, керованих даними, перейшли від виключно синтаксичного аналізу до інтенсивніших семантичних представлень, показуючи, що успішне розуміння смислу тексту вимагає структурованого аналізу як його граматики, так і його семантики. У статті повідомляється про об’єднану породжувальну модель на основі передісторії для прогнозування найвірогіднішого дерева виведення синтаксичного аналізатора на основі дерев залежностей як для синтаксичних, так і для семантичних залежностей у різних мовах. Оскільки ці дві структури залежностей не ізоморфні, ми пропонуємо слабку синхронизацію на рівні значущих підпослідовностей двох дерев виведення. Ці синхронізовані підпослідовності містять інформацію про ліве оточення кожного окремого слова. Ми також пропонуємо інноваційні виведення семантичних структур залежностей, які відповідають відносно вільній природі цих графів. Для навчання об’єднаної моделі цих синхронизованих виведень ми використовуємо модель синтаксичного аналізу із прихованою змінною – модель Incremental Sigmoid Belief Network (ISBN). Ця модель продукує представлення прихованих властивостей у деревах виведень, які використовуються для виявлення взаємозв’язків як усередині двох дерев виведення, так і між ними, вперше використовуючи ISBN для розв’язання проблеми багатозадачного навчання. Ця об’єднана модель демонструє конкурентноздатний рівень як синтаксичного, так і семантичного аналізу різних мов. Завдяки загальному характеру нашого методу, вказане застосування моделі ISBN для аналізу слабо синхронізованих синтактико-семантичних дерев виведення також свідчить про можливість її застосування для вирішення інших проблем, коли йдеться про опанування двома незалежними, але спорідненими представленнями.
Переклад І. Снегурова, М. Погребної
Demberg, V. Incremental, Predictive Parsing with Psycholinguistically Motivated Tree-Adjoining Grammar [Поетапний, прогностичний синтаксичний аналіз на основі психолінгвістично обумовленої граматики з'єднання дерев] / Vera Demberg, Frank Keller, Alexander Koller // Computational linguistics. – 2013. – Vol. 39. – No. 4. – Pр. 1025–1066. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00160#.WH6Li33sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00160
Психолінгвістичні дослідження свідчать, що головними характеристиками обробки речення людиною є поетапність, зв’язність (спрощені дерева не мають неприєднаних вузлів) і прогнозування (наступна синтаксична структура є очікуваною). Проте універсальної моделі синтаксичного аналізу із вказаними характеристиками поки немає. У статті описано перший універсальний імовірнісний синтаксичний аналізатор на основі психолінгвістично мотивованої граматики з’єднання дерев (PsychoLinguistically motivated Tree-Adjoining Grammar, скор. PLTAG), модифікованої граматики з’єднання дерев (Tree-Adjoining Grammar, скор. TAG), яка задовольняє всім трьом умовам. Тренування аналізатора здійснювалось на модифікованій за правилами граматики з’єднання дерев версії синтаксично анотованого корпусу Penn Treebank. Продемонстровано, що він працює так само, як існуючі аналізатори на основі TAG, які є поетапними, але не мають прогностичної сили. Запропонована модель PLTAG також використовувалась для прогнозування швидкості обробки тексту людиною і показала кращі результати на відеоокулографічному корпусі Данді, ніж стандартна модель несподіваності.
Психолінгвістичні дослідження свідчать, що головними характеристиками обробки речення людиною є поетапність, зв’язність (спрощені дерева не мають неприєднаних вузлів) і прогнозування (наступна синтаксична структура є очікуваною). Проте універсальної моделі синтаксичного аналізу із вказаними характеристиками поки немає. У статті описано перший універсальний імовірнісний синтаксичний аналізатор на основі психолінгвістично мотивованої граматики з’єднання дерев (PsychoLinguistically motivated Tree-Adjoining Grammar, скор. PLTAG), модифікованої граматики з’єднання дерев (Tree-Adjoining Grammar, скор. TAG), яка задовольняє всім трьом умовам. Тренування аналізатора здійснювалось на модифікованій за правилами граматики з’єднання дерев версії синтаксично анотованого корпусу Penn Treebank. Продемонстровано, що він працює так само, як існуючі аналізатори на основі TAG, які є поетапними, але не мають прогностичної сили. Запропонована модель PLTAG також використовувалась для прогнозування швидкості обробки тексту людиною і показала кращі результати на відеоокулографічному корпусі Данді, ніж стандартна модель несподіваності.
Переклад В. О. Коломієць
Nivre, J. Constrained Arc-Eager Dependency Parsing [Обмежений дугоспрямований синтаксичний аналіз на основі граматики залежностей] / Joakim Nivre, Yoav Goldberg, Ryan McDonald // Computational linguistics. – 2014. – Vol. 40. – No. 2. – Pр. 249–257. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00184#.WH6MUn3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00184
Дугоспрямовані синтаксичні аналізатори на основі граматики залежностей обробляють речення за один перегляд вхідних даних зліва направо і характеризуються лінійною часовою складністю із жадібним декодуванням або променевим пошуком. Ми показуємо, як можна обмежити такі аналізатори, щоб ураховувати два різні типи умов до обмежень кістяка вихідного графа залежностей, що вимагають, щоб певні кістякові дерева відповідали піддеревам графа, і до обмежень дуг, що вимагають наявності у графі певних дуг. Обмеження вбудовано у дугоспрямований аналізатор на основі машин станів як набір вихідних умов для кожного переходу, вони зберігають лінійну часову складність синтаксичного аналізатора.
Дугоспрямовані синтаксичні аналізатори на основі граматики залежностей обробляють речення за один перегляд вхідних даних зліва направо і характеризуються лінійною часовою складністю із жадібним декодуванням або променевим пошуком. Ми показуємо, як можна обмежити такі аналізатори, щоб ураховувати два різні типи умов до обмежень кістяка вихідного графа залежностей, що вимагають, щоб певні кістякові дерева відповідали піддеревам графа, і до обмежень дуг, що вимагають наявності у графі певних дуг. Обмеження вбудовано у дугоспрямований аналізатор на основі машин станів як набір вихідних умов для кожного переходу, вони зберігають лінійну часову складність синтаксичного аналізатора.
Переклад М. Драчової
Nivre, J. Arc-Eager Parsing with the Tree Constraint [Дугоспрямований синтаксичний аналіз із обмеженням дерев] / Joakim Nivre, Daniel Fernández-González // Computational linguistics. – 2014. – Vol. 40. – No. 2. – Pages 259–267. – Режим доступу до анотації : http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00185#.WH6Mhn3sSGA – Режим доступу до повнотекстової статті : http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00185
Дугоспрямована система синтаксичного аналізу на основі машин станів широко використовується в обробці природних мов незважаючи на те, що вона не гарантує отримання правильно побудованого дерева залежностей на виході. Ми пропонуємо нескладну модифікацію оригінальної системи, яка забезпечує обмеження дерев без внесення жодних змін до процедури навчання синтаксичного аналізатора. Експерименти з обробки різних мов свідчать, що цей метод зменшує кількість помилок у середньому на 72 % і незмінно перевершує результати стандартного евристичного алгоритму, який використовується нині.
Дугоспрямована система синтаксичного аналізу на основі машин станів широко використовується в обробці природних мов незважаючи на те, що вона не гарантує отримання правильно побудованого дерева залежностей на виході. Ми пропонуємо нескладну модифікацію оригінальної системи, яка забезпечує обмеження дерев без внесення жодних змін до процедури навчання синтаксичного аналізатора. Експерименти з обробки різних мов свідчать, що цей метод зменшує кількість помилок у середньому на 72 % і незмінно перевершує результати стандартного евристичного алгоритму, який використовується нині.
Переклад М. Драчової
Gardent, C. Multiple Adjunction in Feature-Based Tree-Adjoining Grammar [Множинна ад’юнкція у категоріальній граматиці з’єднання дерев] / Claire Gardent, Shashi Narayan // Computational Linguistics. – 2015. – Vol. 41. – No. 1. – Pages 41–70. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00217 – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00217
Шейбс та Шібер (1994) продемонстрували, що в автоматичному синтаксичному аналізі за допомогою граматики з’єднання дерев (ГЗД) коректна підтримка синтаксичного аналізу, семантичної інтерпретації та статистичного моделювання мови неможлива без незалежних дериватів. Втім, запропонований ними алгоритм синтаксичного аналізу не можна прямо застосувати до категоріальних ГЗД (КГЗД). У статті запропоновано алгоритм розпізнавання для КГЗД, який працює як із залежними, так і з незалежними дериватами. Отриманий алгоритм поєднує переваги незалежних дериватів з перевагами категоріальних граматик. Зокрема, показано, що він пояснює, з одного боку, цілий ряд взаємодій між залежними і незалежними дериватами, а з другого боку, синтаксичні обмеження, лінійне упорядкування і локальні та глобальні семантичні залежності.
Шейбс та Шібер (1994) продемонстрували, що в автоматичному синтаксичному аналізі за допомогою граматики з’єднання дерев (ГЗД) коректна підтримка синтаксичного аналізу, семантичної інтерпретації та статистичного моделювання мови неможлива без незалежних дериватів. Втім, запропонований ними алгоритм синтаксичного аналізу не можна прямо застосувати до категоріальних ГЗД (КГЗД). У статті запропоновано алгоритм розпізнавання для КГЗД, який працює як із залежними, так і з незалежними дериватами. Отриманий алгоритм поєднує переваги незалежних дериватів з перевагами категоріальних граматик. Зокрема, показано, що він пояснює, з одного боку, цілий ряд взаємодій між залежними і незалежними дериватами, а з другого боку, синтаксичні обмеження, лінійне упорядкування і локальні та глобальні семантичні залежності.
Переклад М. Дубка
Mirroshandel S. A. Integrating Selectional Constraints and Subcategorization Frames in a Dependency Parser [Використання обмежень у сполучуваності та субкатегорійних фреймів у синтаксичних аналізаторах на основі граматики залежностей] / Seyed Abolghasem Mirroshandel, Alexis Nasr // Computational linguistics. – 2016. – Vol. 42. – No. 1. – Pages 55–90. – Режим доступу до анотації: https://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00242 – Режим доступу до повнотекстової статті: https://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00242
Статистичні синтаксичні аналізатори навчаються на банках синтаксичних дерев, які складаються з декількох тисяч речень. Для запобігання розрідженості даних та складності обчислень такі аналізатори висувають вагомі гіпотези про незалежність рішень, прийнятих для побудови синтаксичного дерева. Ці гіпотези про незалежність призводять до членування синтаксичних структур на невеликі фрагменти, що в свою чергу не дозволяє синтаксичному аналізатору адекватно змоделювати багато лексико-синтаксичних явищ, наприклад обмеження в сполучуваності та субкатегорійні фрейми. Крім того, банки синтаксичних дерев надто малі для дослідження багатьох лексико-синтаксичних закономірностей, таких як обмеження в сполучуваності та субкатегорійні фрейми. У статті запропоновано рішення для обох проблем: як вирахувати шаблони, що перевищують розмір фрагментів, які моделюються в синтаксичному аналізаторі; і як отримати субкатегорійні фрейми та обмеження в сполучуваності з нерозмічених корпусів і вбудувати їх у процес автоматичного синтаксичного аналізу. Запропонований метод було апробовано на французькій та англійській мовах. Експерименти з французькою мовою показали зменшення порушень обмежень у сполучуваності на 41,6% і зменшення помилок у виділенні субкатегорійних фреймів на 22%. Ці показники нижчі для англійської мови: 16,21% у першому випадку та 8,83% у другому.
Статистичні синтаксичні аналізатори навчаються на банках синтаксичних дерев, які складаються з декількох тисяч речень. Для запобігання розрідженості даних та складності обчислень такі аналізатори висувають вагомі гіпотези про незалежність рішень, прийнятих для побудови синтаксичного дерева. Ці гіпотези про незалежність призводять до членування синтаксичних структур на невеликі фрагменти, що в свою чергу не дозволяє синтаксичному аналізатору адекватно змоделювати багато лексико-синтаксичних явищ, наприклад обмеження в сполучуваності та субкатегорійні фрейми. Крім того, банки синтаксичних дерев надто малі для дослідження багатьох лексико-синтаксичних закономірностей, таких як обмеження в сполучуваності та субкатегорійні фрейми. У статті запропоновано рішення для обох проблем: як вирахувати шаблони, що перевищують розмір фрагментів, які моделюються в синтаксичному аналізаторі; і як отримати субкатегорійні фрейми та обмеження в сполучуваності з нерозмічених корпусів і вбудувати їх у процес автоматичного синтаксичного аналізу. Запропонований метод було апробовано на французькій та англійській мовах. Експерименти з французькою мовою показали зменшення порушень обмежень у сполучуваності на 41,6% і зменшення помилок у виділенні субкатегорійних фреймів на 22%. Ці показники нижчі для англійської мови: 16,21% у першому випадку та 8,83% у другому.
Переклад А. Шульги
Gildea, D. Synchronous Context-Free Grammars and Optimal Parsing Strategies [Синхронні контекстно-вільні граматики та стратегії оптимального автоматичного синтаксичного аналізу] / Daniel Gildea, Giorgio Satta // Computational linguistics. – 2016. – Vol. 42. – No. 2. – Pages 207–243. – Режим доступу до анотації: https://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00246 – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00246
Складність автоматичного синтаксичного аналізу з синхронними контекстно-вільними граматиками є багаточленом по довжині речення для закріпленої граматики, але ступінь багаточлена залежить від граматики. Зокрема, ступінь залежить від довжини правил, представлених правилами перестановок, і стратегії автоматичного синтаксичного аналізу, прийнятої для розкладання розпізнавання правила на дрібніші кроки. Проблему пошуку найкращої стратегії автоматичного синтаксичного аналізу для правила розглянуто з точки зору складності простору та часу. Продемонстровано, що знаходження двійкової стратегії з найнижчою просторовою складністю є NP-складною задачею. Продемонстровано також, що будь-який алгоритм пошуку стратегії з найнижчою часовою складністю передбачає вдосконалення алгоритмів апроксимації для визначення деревної ширини загальних графів.
Складність автоматичного синтаксичного аналізу з синхронними контекстно-вільними граматиками є багаточленом по довжині речення для закріпленої граматики, але ступінь багаточлена залежить від граматики. Зокрема, ступінь залежить від довжини правил, представлених правилами перестановок, і стратегії автоматичного синтаксичного аналізу, прийнятої для розкладання розпізнавання правила на дрібніші кроки. Проблему пошуку найкращої стратегії автоматичного синтаксичного аналізу для правила розглянуто з точки зору складності простору та часу. Продемонстровано, що знаходження двійкової стратегії з найнижчою просторовою складністю є NP-складною задачею. Продемонстровано також, що будь-який алгоритм пошуку стратегії з найнижчою часовою складністю передбачає вдосконалення алгоритмів апроксимації для визначення деревної ширини загальних графів.
Переклад М. Дубка
Zhang X. Transition-Based Parsing for Deep Dependency Structures [Автоматичний синтаксичний аналіз глибинних структур залежностей на основі переходів] / Xun Zhang , Yantao Du , Weiwei Sun and Xiaojun Wan // Computational linguistics. – 2016. – Vol. 42. – No. 3. – Pages 353–389. – Режим доступу до анотації: https://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00252 – Режим доступу до повнотекстової статті: https://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00252
Деривації в різних граматичних формалізмах дозволяють видобувати різноманітні структури залежностей. Зокрема, завдяки лінгвістичному аналізу на основі комбінаторної категоріальної граматики (ККГ), лексико-функціональної граматики (ЛФГ) та верховинної граматики складників (ВГС) можна на додаток до представлення поверхневої структури дерева видобути білексичні глибинні структури залежностей. Традиційно ці структури залежностей отримують як вторинний продукт граматично-орієнтованих синтаксичних аналізаторів. А в цій статті досліджується альтернативний керований даними підхід до побудови загальних графів залежностей на основі переходів, який успішно використовується в автоматичному синтаксичному аналізі. Представлено дві нові системи на основі переходів, які об’єднують існуючі методи опрацювання синтаксичних дерев і які можуть поетапно генерувати довільні орієнтовані графи. На основі цих систем переходів можна побудувати статистичні синтаксичні аналізатори, які є конкурентоспроможними як за точністю, так і за ефективністю. Крім того, різнорідна будова систем переходів забезпечує різноманітність сумісних моделей синтаксичного аналізу, що значно підвищує ефективність синтаксичного аналізатора. Для зняття лексичної багатозначності запропоновано два нові методи поліпшення якості аналізу, а саме: комбінацію переходів і спрощення дерев. Завдяки комбінації переходів кожна дія, яка виконується синтаксичним аналізатором, суттєво змінює конфігурації. Отже, для зняття статистичної неоднозначності можна виділити чіткіші категорії. Для визначення цих інформативних категорій метод спрощення дерев виводить основи дерев із графів залежностей і повторно використовує методи синтаксичного аналізу дерев для отримання категорій на основі дерев. Здійснено функторно-аргументний аналіз на основі ККГ, аналіз граматичних зв’язків на основі ЛФГ та аналіз семантичної залежності на основі ВГС англійської та китайської мов. Проведені експерименти свідчать, що керовані даними моделі з відповідними системами переходів можуть забезпечити високоякісний аналіз глибинних структур залежностей, нарівні з більш складними граматичними моделями. Експерименти також свідчать про ефективність гетерогенної будови систем синтаксичного аналізу на основі переходів, комбінації переходів і спрощення дерев для зняття статистичної неоднозначності.
Деривації в різних граматичних формалізмах дозволяють видобувати різноманітні структури залежностей. Зокрема, завдяки лінгвістичному аналізу на основі комбінаторної категоріальної граматики (ККГ), лексико-функціональної граматики (ЛФГ) та верховинної граматики складників (ВГС) можна на додаток до представлення поверхневої структури дерева видобути білексичні глибинні структури залежностей. Традиційно ці структури залежностей отримують як вторинний продукт граматично-орієнтованих синтаксичних аналізаторів. А в цій статті досліджується альтернативний керований даними підхід до побудови загальних графів залежностей на основі переходів, який успішно використовується в автоматичному синтаксичному аналізі. Представлено дві нові системи на основі переходів, які об’єднують існуючі методи опрацювання синтаксичних дерев і які можуть поетапно генерувати довільні орієнтовані графи. На основі цих систем переходів можна побудувати статистичні синтаксичні аналізатори, які є конкурентоспроможними як за точністю, так і за ефективністю. Крім того, різнорідна будова систем переходів забезпечує різноманітність сумісних моделей синтаксичного аналізу, що значно підвищує ефективність синтаксичного аналізатора. Для зняття лексичної багатозначності запропоновано два нові методи поліпшення якості аналізу, а саме: комбінацію переходів і спрощення дерев. Завдяки комбінації переходів кожна дія, яка виконується синтаксичним аналізатором, суттєво змінює конфігурації. Отже, для зняття статистичної неоднозначності можна виділити чіткіші категорії. Для визначення цих інформативних категорій метод спрощення дерев виводить основи дерев із графів залежностей і повторно використовує методи синтаксичного аналізу дерев для отримання категорій на основі дерев. Здійснено функторно-аргументний аналіз на основі ККГ, аналіз граматичних зв’язків на основі ЛФГ та аналіз семантичної залежності на основі ВГС англійської та китайської мов. Проведені експерименти свідчать, що керовані даними моделі з відповідними системами переходів можуть забезпечити високоякісний аналіз глибинних структур залежностей, нарівні з більш складними граматичними моделями. Експерименти також свідчать про ефективність гетерогенної будови систем синтаксичного аналізу на основі переходів, комбінації переходів і спрощення дерев для зняття статистичної неоднозначності.
Переклад А. Шульги
Gómez-Rodríguez, C. Restricted Non-Projectivity: Coverage vs. Efficiency [Обмежена непроективність: охоплення чи ефективність] / Carlos Gómez-Rodríguez // Computational linguistics. – 2016. – Vol. 42. – No. 4. – Pages 809–817. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00267 – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00267
Щоб забезпечити оптимальне співвідношення ефективності автоматичного синтаксичного аналізу та охоплення притаманних природним мовам синтаксичних структур, протягом останнього десятиліття було запропоновано різні обмежені класи непроективних дерев залежностей. Метою цього масштабного дослідження було оцінювання охоплення широкого кола таких класів у корпусах 30 мов за допомогою двох різних мірил синтаксичної розмітки. Результати свідчать, що серед відомих нині послаблень проективності найкраще співвідношення охоплення та обчислювальної складності точного автоматичного синтаксичного аналізу досягається або за допомогою дерев, які перетинаються в одній кінцевій точці, або за допомогою багатовузлових дерев, залежно від бажаного рівня охоплення. Також описано деякі особливості зв’язку багатовузлових дерев з іншими відповідними класами дерев.
Щоб забезпечити оптимальне співвідношення ефективності автоматичного синтаксичного аналізу та охоплення притаманних природним мовам синтаксичних структур, протягом останнього десятиліття було запропоновано різні обмежені класи непроективних дерев залежностей. Метою цього масштабного дослідження було оцінювання охоплення широкого кола таких класів у корпусах 30 мов за допомогою двох різних мірил синтаксичної розмітки. Результати свідчать, що серед відомих нині послаблень проективності найкраще співвідношення охоплення та обчислювальної складності точного автоматичного синтаксичного аналізу досягається або за допомогою дерев, які перетинаються в одній кінцевій точці, або за допомогою багатовузлових дерев, залежно від бажаного рівня охоплення. Також описано деякі особливості зв’язку багатовузлових дерев з іншими відповідними класами дерев.
Переклад М. Дубка
Ballesteros, M. Greedy Transition-Based Dependency Parsing with Stack LSTMs [Жадібний автоматичний синтаксичний аналіз залежностей на основі переходів за допомогою ТКПС] / Miguel Ballesteros, Chris Dyer, Yoav Goldberg, Noah A. Smith // Computational linguistics. – 2017. – Vol. 43. – No. 2. – Pages 311–347. – Режим доступу до анотації: https://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00285 – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00285
У статті представлено жадібний автоматичний синтаксичний аналізатор на основі переходів, який автоматично навчається репрезентувати стани автоматичного синтаксичного аналізатора за допомогою рекурентних нейронних мереж. Основним нововведенням, яке дозволяє робити це ефективно, є нова структура управління для послідовних нейронних мереж – стековий модуль тривалої короткочасної пам'яті (ТКЧП). Як і в звичайних стекових структурах даних, які використовуються в автоматичних синтаксичних аналізаторах на основі переходів, елементи можуть додаватися до або видалятися з вершини стека за сталий проміжок часу, але, крім цього, ТКЧП підтримує безперервне просторове розміщення вмісту стека. Запропонована модель фіксує три аспекти стану автоматичного синтаксичного аналізатора: (i) необмежений перегляд буфера вхідних слів; (іі) повну історію виконаних автоматичним синтаксичним аналізатором переходів; (ііі) повний вміст стека фрагментів частково побудованого дерева, зокрема їхні внутрішні структури. Крім того, здійснено порівняння двох різних представлень слова: (i) стандартних векторів слів на основі довідкових таблиць і (ii) символьних моделей слів. Хоча стандартні моделі додавання слів добре працюють на всіх мовах, символьні моделі покращують опрацювання слів, відсутніх у словнику, особливо в морфологічно багатих мовах. Нарешті, обговорено використання динамічних оракулів у навчанні автоматичного синтаксичного аналізатора. Під час навчання динамічні оракули по черзі отримують зразки станів автоматичного синтаксичного аналізатора з навчальних даних та з автоматично створюваної моделі, що робить цю модель більш стійкою до тих видів помилок, які матимуть місце під час тестування. Результатом автоматичного навчання запропонованої моделі за допомогою динамічних оракулів є дійсно конкурентоспроможний лінійний жадібний аналізатор.
У статті представлено жадібний автоматичний синтаксичний аналізатор на основі переходів, який автоматично навчається репрезентувати стани автоматичного синтаксичного аналізатора за допомогою рекурентних нейронних мереж. Основним нововведенням, яке дозволяє робити це ефективно, є нова структура управління для послідовних нейронних мереж – стековий модуль тривалої короткочасної пам'яті (ТКЧП). Як і в звичайних стекових структурах даних, які використовуються в автоматичних синтаксичних аналізаторах на основі переходів, елементи можуть додаватися до або видалятися з вершини стека за сталий проміжок часу, але, крім цього, ТКЧП підтримує безперервне просторове розміщення вмісту стека. Запропонована модель фіксує три аспекти стану автоматичного синтаксичного аналізатора: (i) необмежений перегляд буфера вхідних слів; (іі) повну історію виконаних автоматичним синтаксичним аналізатором переходів; (ііі) повний вміст стека фрагментів частково побудованого дерева, зокрема їхні внутрішні структури. Крім того, здійснено порівняння двох різних представлень слова: (i) стандартних векторів слів на основі довідкових таблиць і (ii) символьних моделей слів. Хоча стандартні моделі додавання слів добре працюють на всіх мовах, символьні моделі покращують опрацювання слів, відсутніх у словнику, особливо в морфологічно багатих мовах. Нарешті, обговорено використання динамічних оракулів у навчанні автоматичного синтаксичного аналізатора. Під час навчання динамічні оракули по черзі отримують зразки станів автоматичного синтаксичного аналізатора з навчальних даних та з автоматично створюваної моделі, що робить цю модель більш стійкою до тих видів помилок, які матимуть місце під час тестування. Результатом автоматичного навчання запропонованої моделі за допомогою динамічних оракулів є дійсно конкурентоспроможний лінійний жадібний аналізатор.
Переклад М. Дубка
Gebhardt K. Hybrid Grammars for Parsing of Discontinuous Phrase Structures and Non-Projective Dependency Structures [Гібридні граматики для синтаксичного аналізу перерваних фразових структур і непроективних структур залежностей] / Kilian Gebhardt, Mark-Jan Nederhof, Heiko Vogler // Computational linguistics. – 2017. – Vol. 43. – No. 3. – Pages 465–520. – Режим доступу до анотації: https://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00291 – Режим доступу до повнотекстової статті: https://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00291
У статті досліджується поняття гібридних граматик, які формалізують і узагальнюють низку існуючих методів для опрацювання перерваних синтаксичних структур. Розглянуто як перервані фразові структури, так і непроективні структури залежностей. Формально гібридні граматики пов’язані з синхронними граматиками, в яких один компонент генерує лінійні структури, а інший – ієрархічні. Результатом об’єднання лексичних елементів обох компонентів є перервані структури. Описано декілька типів гібридних граматик. Також, розглянуто виведення граматик з банків синтаксичних дерев. Основною перевагою гібридних граматик над існуючими методами є можливість розмежувати переривність необхідних структур і часову складність автоматичного синтаксичного аналізу. Це дозволяє проаналізувати застосування для аналізу перерваних структур різноманітних алгоритмів автоматичного синтаксичного аналізу з різними властивостями. Це підтверджується представленими експериментальними результатами, які демонструють широкий діапазон тривалості роботи, точності та частоти збоїв автоматичного синтаксичного аналізу.
У статті досліджується поняття гібридних граматик, які формалізують і узагальнюють низку існуючих методів для опрацювання перерваних синтаксичних структур. Розглянуто як перервані фразові структури, так і непроективні структури залежностей. Формально гібридні граматики пов’язані з синхронними граматиками, в яких один компонент генерує лінійні структури, а інший – ієрархічні. Результатом об’єднання лексичних елементів обох компонентів є перервані структури. Описано декілька типів гібридних граматик. Також, розглянуто виведення граматик з банків синтаксичних дерев. Основною перевагою гібридних граматик над існуючими методами є можливість розмежувати переривність необхідних структур і часову складність автоматичного синтаксичного аналізу. Це дозволяє проаналізувати застосування для аналізу перерваних структур різноманітних алгоритмів автоматичного синтаксичного аналізу з різними властивостями. Це підтверджується представленими експериментальними результатами, які демонструють широкий діапазон тривалості роботи, точності та частоти збоїв автоматичного синтаксичного аналізу.
Переклад А. Шульги