Karttunen, L. Introduction to the Special Issue on Finite-State Methods in NLP [Вступ до спеціального випуску, присвяченого методам скінченних станів у обробці природної мови] / Lauri Karttunen, Kemal Oflazer // Computational linguistics. – 2000. – Vol. 26. – No. 1. – Pages 1–2. – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120100561593
На перших етапах становлення сучасної лінгвістики граматики скінченних станів ігнорувалися як абсолютно непридатні, але протягом останнього десятиліття спостерігається значне зростання їх використання у різних додатках для обробки природної мови. У п’яти статтях, які увійшли до спеціального випуску, розглядаються різні аспекти теорії скінченних станів і її практичне застосування.
На перших етапах становлення сучасної лінгвістики граматики скінченних станів ігнорувалися як абсолютно непридатні, але протягом останнього десятиліття спостерігається значне зростання їх використання у різних додатках для обробки природної мови. У п’яти статтях, які увійшли до спеціального випуску, розглядаються різні аспекти теорії скінченних станів і її практичне застосування.
В. Коломієць
Nederhof, M. J. Practical Experiments with Regular Approximation of Context-Free Languages [Практичні експерименти з формального ототожнення безконтекстних мов] / Mark-Jan Nederhof // Computational linguistics. – 2000. – Vol. 26. – No. 1. – Pages 17–44. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120100561610#.WIUkaH3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120100561610
Розглянуто декілька методів побудови кінцевих автоматів із використанням контекстно-вільної граматики, у тому числі обидва методи, які дозволяють отримати підмножини, і ті, які дають розширені множини вихідної контекстно-вільної мови. Деякі з цих методів регулярного наближення є новими, а деякі інші являють собою удосконалення того, що описано в літературі. Проведено практичні експерименти з різними методами регулярного наближення для усних вхідних даних: гіпотези розпізнавача усного мовлення фільтруються кінцевим автоматом.
Розглянуто декілька методів побудови кінцевих автоматів із використанням контекстно-вільної граматики, у тому числі обидва методи, які дозволяють отримати підмножини, і ті, які дають розширені множини вихідної контекстно-вільної мови. Деякі з цих методів регулярного наближення є новими, а деякі інші являють собою удосконалення того, що описано в літературі. Проведено практичні експерименти з різними методами регулярного наближення для усних вхідних даних: гіпотези розпізнавача усного мовлення фільтруються кінцевим автоматом.
Переклад Д. Попової
Alshawi, H. Learning Dependency Translation Models as Collections of Finite-State Head Transducers [Алгоритми навчання перекладу на основі залежностей у вигляді наборів скінченних перетворювачів] / Hiyan Alshawi, Srinivas Bangalore, Shona Douglas // Computational linguistics. – 2000. – Vol. 26. – No. 1. – Pages 45–60. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120100561629#.WIUk133sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120100561629
У статті дається визначення перетворювачів з ваговою обробкою, скінченних автоматів, які виконують перетворення, починаючи з середини рядка. Ці пертворювачі явно більш ефективні, ніж конкретний стандартний скінченний перетворювач, який обробляє рядки зліва направо. Далі дається визначення алоритмів перетворення на основі залежностей як колекцій перетворювачів з ваговою обробкою, які застосовуються в ієрархічному порядку. Описано алгоритм пошуку на основі динамічного програмування для знаходження оптимального перетворення вхідного рядка відповідно алгоритму перетворення на основі залежностей. Описано метод автоматичного тренування алгоритму перетворення на основі залежностей з використанням набору прикладів вхідних та вихідних рядків. Спочатку, керучись статистикою кореляцій, алгоритм шукає ієрархічні пари тренувальних прикладів, а потім створює переходи перетворювачів відповідно цим парам. Описано результати експериментального застосування цього методу навчання при перекладі з англійської на іспанську та японську мови.
У статті дається визначення перетворювачів з ваговою обробкою, скінченних автоматів, які виконують перетворення, починаючи з середини рядка. Ці пертворювачі явно більш ефективні, ніж конкретний стандартний скінченний перетворювач, який обробляє рядки зліва направо. Далі дається визначення алоритмів перетворення на основі залежностей як колекцій перетворювачів з ваговою обробкою, які застосовуються в ієрархічному порядку. Описано алгоритм пошуку на основі динамічного програмування для знаходження оптимального перетворення вхідного рядка відповідно алгоритму перетворення на основі залежностей. Описано метод автоматичного тренування алгоритму перетворення на основі залежностей з використанням набору прикладів вхідних та вихідних рядків. Спочатку, керучись статистикою кореляцій, алгоритм шукає ієрархічні пари тренувальних прикладів, а потім створює переходи перетворювачів відповідно цим парам. Описано результати експериментального застосування цього методу навчання при перекладі з англійської на іспанську та японську мови.
Переклад Д. Попової, М. Погребної
van Noord, G. Treatment of Epsilon Moves in Subset Construction [Використання епсилон-переходів у створенні підмножин] / Gertjan van Noord // Computational linguistics. – 2000. – Vol. 26. – No. 1. – Pages 61–76. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120100561638#.WIUlVn3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120100561638
Стаття присвячена проблемі детермінування кінцевих автоматів з великою кількістю епсілон-переходів. Експерименти з кінцевими наближеннями граматик природніх мов часто призводить до появи дуже великих автоматів із дуже великою кількістю епсілон-переходів. У цій статті визначаються і порівнюються кілька алгоритмів створення підмножин, які застосовують епсілон-переходи. Проведено експерименти, які свідчать, що алгоритми значно відрізняються на практиці, як за розміром отриманого детермінованого автомата, так і за ефективностю. Крім того, експерименти наводять на думку, що середня кількість епсілон-переходів у стані може допомогти передбачити, який алгоритм, скоріше за все, буде найшвидшим для конкретного вхідного автомата.
Стаття присвячена проблемі детермінування кінцевих автоматів з великою кількістю епсілон-переходів. Експерименти з кінцевими наближеннями граматик природніх мов часто призводить до появи дуже великих автоматів із дуже великою кількістю епсілон-переходів. У цій статті визначаються і порівнюються кілька алгоритмів створення підмножин, які застосовують епсілон-переходи. Проведено експерименти, які свідчать, що алгоритми значно відрізняються на практиці, як за розміром отриманого детермінованого автомата, так і за ефективностю. Крім того, експерименти наводять на думку, що середня кількість епсілон-переходів у стані може допомогти передбачити, який алгоритм, скоріше за все, буде найшвидшим для конкретного вхідного автомата.
Переклад Д. Попової
Kiraz, G.A. Multitiered Nonlinear Morphology Using Multitape Finite Automata: A Case Study on Syriac and Arabic [Багаторівнева нелінійна морфологія з використанням багатострічкових скінченних автоматів: тематичне дослідження на основі сирійської та арабської мов] / George Anton Kiraz // Computational linguistics. – 2000. – Vol. 26. – No. 1. – Pages 77–105. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120100561647#.WIUlq33sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120100561647
У статті представлено обчислювальну модель нелінійної морфології з прикладами з сирійської та арабської мов. Модель є багаторівневою, оскільки допускає численні лексичні репрезентації, що відповідають численним рівням автосегментної фонології. Модель складається з трьох основних компонентів: 1) лексикону, який є сукупністю підлексиконів, де кожний підлексикон представляє матеріал певного рівня, 2) компонента правил виводу, який відображає декілька лексичних репрезентацій у одній поверхневій формі і навпаки, та (ііі) морфотактичного компонента, який використовує автоматні граматики. Система є скінченною, позаяк лексикони і правила можуть бути представленими багатострічковими скінченними автоматами.
У статті представлено обчислювальну модель нелінійної морфології з прикладами з сирійської та арабської мов. Модель є багаторівневою, оскільки допускає численні лексичні репрезентації, що відповідають численним рівням автосегментної фонології. Модель складається з трьох основних компонентів: 1) лексикону, який є сукупністю підлексиконів, де кожний підлексикон представляє матеріал певного рівня, 2) компонента правил виводу, який відображає декілька лексичних репрезентацій у одній поверхневій формі і навпаки, та (ііі) морфотактичного компонента, який використовує автоматні граматики. Система є скінченною, позаяк лексикони і правила можуть бути представленими багатострічковими скінченними автоматами.
Переклад Д. Попової
Morrill, G. Incremental Processing and Acceptability [Поетапна обробка та відповідність вимогам] / Glyn Morrill // Computational linguistics. – 2000. – Vol. 26. – No. 3. – Pages 319–338. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120100561728#.WIUmDH3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120100561728
У статті описано процедуру поетапної, зліва направо, обробки категоріальної граматики Ламбека шляхом створення захисної сітки. Простий показник складності, характеристика в момент великої кількості невирішених валентностей, точно прогнозує різноманітні проблеми обробки, зокрема неоднозначність (garden pathing), неприпустимість вбудовування всередину, очікування пізнього закриття, вибір сфери дії квантифікаторів зліва-направо і зсув іменної групи.
У статті описано процедуру поетапної, зліва направо, обробки категоріальної граматики Ламбека шляхом створення захисної сітки. Простий показник складності, характеристика в момент великої кількості невирішених валентностей, точно прогнозує різноманітні проблеми обробки, зокрема неоднозначність (garden pathing), неприпустимість вбудовування всередину, очікування пізнього закриття, вибір сфери дії квантифікаторів зліва-направо і зсув іменної групи.
Переклад О. Мартинюк
Rambow, O. D-Tree Substitution Grammars [Граматики заміщення d-дерев] / Owen Rambow, K. Vijay-Shanker, David Weir // Computational linguistics. – 2001. – Vol. 27. – No. 1. – Pages 87–121. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120101300346813#.WIUmdn3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120101300346813
Багато комп'ютерних лінгвістів цікавляться лексикалізованими граматичними моделями. Одним із добре відомих прикладів є лексикалізована граматика складання дерев (lexicalized tree adjoining grammar, скор. LTAG). У статті пропонується розглядати виводи у LTAG не як маніпуляції над деревами, а як маніпуляції над описами дерев. Новий погляд на лексикалізовану модель піднімає питання про доцільність деяких її аспектів. Описано нову модель — граматику заміщення d-дерев (DSG). Виводи в DSG включають структуру d-дерев, спеціальні види опису дерев. Дерева зчитуються з похідних d-дерев. Показано, як можна використати граматику DSG, яка успадкувала багато характеристик LTAG, для здійснення різних лінгвістичних досліджень, які неможливі з LTAG.
Багато комп'ютерних лінгвістів цікавляться лексикалізованими граматичними моделями. Одним із добре відомих прикладів є лексикалізована граматика складання дерев (lexicalized tree adjoining grammar, скор. LTAG). У статті пропонується розглядати виводи у LTAG не як маніпуляції над деревами, а як маніпуляції над описами дерев. Новий погляд на лексикалізовану модель піднімає питання про доцільність деяких її аспектів. Описано нову модель — граматику заміщення d-дерев (DSG). Виводи в DSG включають структуру d-дерев, спеціальні види опису дерев. Дерева зчитуються з похідних d-дерев. Показано, як можна використати граматику DSG, яка успадкувала багато характеристик LTAG, для здійснення різних лінгвістичних досліджень, які неможливі з LTAG.
Переклад М. Драчової
Wintner, S. A Note on Typing Feature Structures [Нотатки про типізацію ознакових структур] / Shuly Wintner, Anoop Sarkar // Computational linguistics. – 2002. – Vol. 28. – No. 3. – Pages 389–397. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/089120102760276027#.WIXJrX3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/089120102760276027
Ознакові структури використовуються для передачі лінгвістичної інформації у різноманітних лінгвістичних формалізмах. Існують різні визначення ознакових структур; однією з площин варіації є типізація: на відміну від структур нетипізованих ознак, структури типізованих ознак асоціюють кожну структуру з типом і обмежують появу ознак і значення, яке вони набирають, вимогами відповідності. У статті продемонстровано переваги, які типізація дає навіть тим лінгвістичним формалізмам, які використовують структури нетипізованих ознак. Описано метод валідації узгодженості вимог до структури нетипізованих ознак шляхом дотримання порядку обслуговування типів. Цей метод спрощує велику кількість перевірок на стадії компілювання: багато можливих помилок можна виявити до застосування формалізму для здійснення синтаксичного розбору. Розроблено сигнатуру типу для існуючої граматики англійської мови з широким діапазоном можливих застосувань і запроваджено алгоритм виведення типів на основі специфікації ознакової структури у граматиці, який повідомляє про несумісності з сигнатурою. Виявлено велику кількість помилок у граматиці, деякі з яких описано у статті.
Ознакові структури використовуються для передачі лінгвістичної інформації у різноманітних лінгвістичних формалізмах. Існують різні визначення ознакових структур; однією з площин варіації є типізація: на відміну від структур нетипізованих ознак, структури типізованих ознак асоціюють кожну структуру з типом і обмежують появу ознак і значення, яке вони набирають, вимогами відповідності. У статті продемонстровано переваги, які типізація дає навіть тим лінгвістичним формалізмам, які використовують структури нетипізованих ознак. Описано метод валідації узгодженості вимог до структури нетипізованих ознак шляхом дотримання порядку обслуговування типів. Цей метод спрощує велику кількість перевірок на стадії компілювання: багато можливих помилок можна виявити до застосування формалізму для здійснення синтаксичного розбору. Розроблено сигнатуру типу для існуючої граматики англійської мови з широким діапазоном можливих застосувань і запроваджено алгоритм виведення типів на основі специфікації ознакової структури у граматиці, який повідомляє про несумісності з сигнатурою. Виявлено велику кількість помилок у граматиці, деякі з яких описано у статті.
Переклад В. Коломієць
Poesio, M. Centering: A Parametric Theory and Its Instantiations [Центрування: параметрична теорія і її трактування] / Massimo Poesio , Rosemary Stevenson , Barbara Di Eugenio , Janet Hitzeman // Computational linguistics. – 2004. – Vol. 30. – No. 3. – Pages 309–363. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/0891201041850911#.WIXNp33sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/0891201041850911
Теорія центрування є найвідомішою платформою для узагальнень про локальні зв’язність і виділеність, проте її положення сформульовані мовою понять, які конкретизуються лише частково, таких як «висловлення», «реалізація» або «ранжування». Детальнішої специфікації цих параметрів теорії намагалася досягти велика кількість дослідників, внаслідок чого положення центрування можуть трактуватися багатьма різними способами. У дослідженні систематично проаналізовано вплив цих різних способів налаштування вказаних параметрів на положення теорії. Для цього потрібно було, в першу чергу, уточнити, які положення містить теорія (одним із висновків є те, що так зване «Обмеження №1» є власне основним положенням теорії). По-друге, потрібно було чітко визначити ці параметричні аспекти. Наприклад, ми стверджуємо, що поняття «займенник», яке використовується у Правилі 1, повинне уважатися параметром. По-третє, потрібно було знайти відповідні методи для оцінки цих положень. З’ясовано, що хоча основне положення теорії про виділеність і прономіналізацію, Правило 1 – перевага прономіналізації ретроспективного центру (ЦР), мало залежить від налаштувань, Обмеження 1 – положення про зв’язність (об’єкту) і унікальність ЦР – значно більше залежить від налаштувань. Воно не підтверджується, якщо параметри налаштовані відповідно загальноприйнятим поглядам («стандартне налаштування»), воно підтверджується, лише якщо дозволена непряма реалізація, і навіть при найсприятливіших налаштуваннях його порушують від 20% до 25% висловлювань у нашому корпусі. Також встановлене оптимальне співвідношення між Правилом 1 з одного боку і Обмеженням 1 і Правилом 2 з другого боку. Налаштування параметрів для зведення порушень локальної зв’язності до мінімуму призводить до зростання порушень виділеності і навпаки. Отримані результати свідчать, що зв’язність «об’єкта» – постійне посилання на ті ж самі об’єкти – повинна бути доповнена принаймні повідомленням про споріднену зв’язність.
Теорія центрування є найвідомішою платформою для узагальнень про локальні зв’язність і виділеність, проте її положення сформульовані мовою понять, які конкретизуються лише частково, таких як «висловлення», «реалізація» або «ранжування». Детальнішої специфікації цих параметрів теорії намагалася досягти велика кількість дослідників, внаслідок чого положення центрування можуть трактуватися багатьма різними способами. У дослідженні систематично проаналізовано вплив цих різних способів налаштування вказаних параметрів на положення теорії. Для цього потрібно було, в першу чергу, уточнити, які положення містить теорія (одним із висновків є те, що так зване «Обмеження №1» є власне основним положенням теорії). По-друге, потрібно було чітко визначити ці параметричні аспекти. Наприклад, ми стверджуємо, що поняття «займенник», яке використовується у Правилі 1, повинне уважатися параметром. По-третє, потрібно було знайти відповідні методи для оцінки цих положень. З’ясовано, що хоча основне положення теорії про виділеність і прономіналізацію, Правило 1 – перевага прономіналізації ретроспективного центру (ЦР), мало залежить від налаштувань, Обмеження 1 – положення про зв’язність (об’єкту) і унікальність ЦР – значно більше залежить від налаштувань. Воно не підтверджується, якщо параметри налаштовані відповідно загальноприйнятим поглядам («стандартне налаштування»), воно підтверджується, лише якщо дозволена непряма реалізація, і навіть при найсприятливіших налаштуваннях його порушують від 20% до 25% висловлювань у нашому корпусі. Також встановлене оптимальне співвідношення між Правилом 1 з одного боку і Обмеженням 1 і Правилом 2 з другого боку. Налаштування параметрів для зведення порушень локальної зв’язності до мінімуму призводить до зростання порушень виділеності і навпаки. Отримані результати свідчать, що зв’язність «об’єкта» – постійне посилання на ті ж самі об’єкти – повинна бути доповнена принаймні повідомленням про споріднену зв’язність.
Переклад В. Коломієць
Nederhof, M. A General Technique to Train Language Models on Language Models [Загальний метод навчання мовних моделей на мовних моделях] / Mark-Jan Nederhof // Computational linguistics. – 2005. – Vol. 31. – No. 2. – Pages 173–185. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/0891201054223986#.WIXRIX3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/0891201054223986
Показано, що за певних умов мовну модель можна тренувати на основі іншої мовної моделі. Головним прикладом цього методу є навчання кінцевого автомату на основі імовірнісної контекстно-вільної граматики, завдяки чому відстань Кульбака-Лейблера між граматикою і навченим автоматом є очевидно мінімальною. Навчання n-грамної моделі на основі імовірнісної контекстно-вільної граматики є суттєвим узагальненням існуючого алгоритму.
Показано, що за певних умов мовну модель можна тренувати на основі іншої мовної моделі. Головним прикладом цього методу є навчання кінцевого автомату на основі імовірнісної контекстно-вільної граматики, завдяки чому відстань Кульбака-Лейблера між граматикою і навченим автоматом є очевидно мінімальною. Навчання n-грамної моделі на основі імовірнісної контекстно-вільної граматики є суттєвим узагальненням існуючого алгоритму.
Переклад В. Коломієць
Malouf, R. Maximal Consistent Subsets [Максимальні упорядковані підмножини] / Robert Malouf // Computational linguistics. – 2007. – Vol. 33. – No. 2. – Pages 153–160. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli.2007.33.2.153#.WIXRZX3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli.2007.33.2.153
Стандартні операції уніфікації комбінують вивірену інформацію з інформацією від однієї або більше заперечних ознакових структур. Багато таких операцій включають знаходження максимальних підмножин набору елементарних обмежень, узгоджених між собою і з строгою ознаковою структурою, у якій підмножина максимально упорядкована з точки зору структури класифікації, оскільки до неї не можна додати жодного обмеження, не порушивши упорядкованості. Хоча вказана проблема є НП-повною, існує багато евристичних методів оптимізації, за допомогою яких можна значно зменшити обсяг пошукового простору. У статті пропонується новий метод оптимізації, обрізка листових верхівок, який у деяких випадках на декілька порядків прискорює час виконання завдання у порівнянні з описаними раніше алгоритмами. Завдяки цьому стандартні операції уніфікації є достатньо ефективними для застосування до широкого кола проблем і додатків.
Стандартні операції уніфікації комбінують вивірену інформацію з інформацією від однієї або більше заперечних ознакових структур. Багато таких операцій включають знаходження максимальних підмножин набору елементарних обмежень, узгоджених між собою і з строгою ознаковою структурою, у якій підмножина максимально упорядкована з точки зору структури класифікації, оскільки до неї не можна додати жодного обмеження, не порушивши упорядкованості. Хоча вказана проблема є НП-повною, існує багато евристичних методів оптимізації, за допомогою яких можна значно зменшити обсяг пошукового простору. У статті пропонується новий метод оптимізації, обрізка листових верхівок, який у деяких випадках на декілька порядків прискорює час виконання завдання у порівнянні з описаними раніше алгоритмами. Завдяки цьому стандартні операції уніфікації є достатньо ефективними для застосування до широкого кола проблем і додатків.
Переклад В. Коломієць
Smith, N. Weighted and Probabilistic Context-Free Grammars Are Equally Expressive [Зважені та імовірнісні контекстно-вільні граматики є однаково точними] / Noah A. Smith, Mark Johnson // Computational linguistics. – 2007. – Vol. 33. – No. 4. – Pр. 477–491. – Режим доступу до анотації http://www.mitpressjournals.org/doi/abs/10.1162/coli.2007.33.4.477#.WH6BNX3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli.2007.33.4.477
У статті аналізується співвідношення між зваженими контекстно-вільними граматиками, у яких кожному правилу виводу відповідає позитивне дійсне число, та імовірнісними контекстно-вільними граматиками, у яких ваги правил виводу, яким відповідає нетермінал, повинні в сумі дорівнювати одиниці. Оскільки клас зважених контекстно-вільних граматик по суті включає в себе імовірнісні контекстно-вільні граматики, можна припустити, що зважені контекстно-вільні граматики здатні описати розподіли, які не можна описати за допомогою імовірнісних контекстно-вільних граматик. Однак З. Чі (Комп’ютерна лінгвістика. – 1999. – V. 25. – Issue 1. – P. 131-160) і С. П. Ебні, Д. А. МакАлестер i П. Перейра (Матеріали 37-ї щорічної конференції Асоціації комп’ютерної лінгвістики – Коледж Парк, Меріленд, 1999. – С. 542-549) довели, що будь-який розподіл, описаний зваженою контекстно-вільною граматикою, є еквівалентним певному розподілу, описаному імовірнісною контекстно-вільною граматикою. Ми застосували їхні висновки до умовних розподілів і показали, що будь-який визначений зваженою контекстно-вільною граматикою умовний розподіл синтаксичних дерев за наявності ланцюжків є також умовним розподілом, визначеним певною імовірнісною контекстно-вільною граматикою, навіть коли функції розподілу граматик не співпадають. Це свідчить про те, що будь-яке поліпшення точності синтаксичного аналізу або анотування від умовного визначення зваженими контекстно-вільними граматиками або умовними довільними полями до комбінованого визначення імовірнісними контекстно-вільними граматиками або прихованими моделями Маркова пояснюється процедурою визначення, а не зміною типу моделі, оскільки імовірнісні контекстно-вільні граматики і приховані моделі Маркова настільки ж точні, як і, відповідно, зважені контекстно-вільні граматики і ланцюгові умовні довільні поля.
У статті аналізується співвідношення між зваженими контекстно-вільними граматиками, у яких кожному правилу виводу відповідає позитивне дійсне число, та імовірнісними контекстно-вільними граматиками, у яких ваги правил виводу, яким відповідає нетермінал, повинні в сумі дорівнювати одиниці. Оскільки клас зважених контекстно-вільних граматик по суті включає в себе імовірнісні контекстно-вільні граматики, можна припустити, що зважені контекстно-вільні граматики здатні описати розподіли, які не можна описати за допомогою імовірнісних контекстно-вільних граматик. Однак З. Чі (Комп’ютерна лінгвістика. – 1999. – V. 25. – Issue 1. – P. 131-160) і С. П. Ебні, Д. А. МакАлестер i П. Перейра (Матеріали 37-ї щорічної конференції Асоціації комп’ютерної лінгвістики – Коледж Парк, Меріленд, 1999. – С. 542-549) довели, що будь-який розподіл, описаний зваженою контекстно-вільною граматикою, є еквівалентним певному розподілу, описаному імовірнісною контекстно-вільною граматикою. Ми застосували їхні висновки до умовних розподілів і показали, що будь-який визначений зваженою контекстно-вільною граматикою умовний розподіл синтаксичних дерев за наявності ланцюжків є також умовним розподілом, визначеним певною імовірнісною контекстно-вільною граматикою, навіть коли функції розподілу граматик не співпадають. Це свідчить про те, що будь-яке поліпшення точності синтаксичного аналізу або анотування від умовного визначення зваженими контекстно-вільними граматиками або умовними довільними полями до комбінованого визначення імовірнісними контекстно-вільними граматиками або прихованими моделями Маркова пояснюється процедурою визначення, а не зміною типу моделі, оскільки імовірнісні контекстно-вільні граматики і приховані моделі Маркова настільки ж точні, як і, відповідно, зважені контекстно-вільні граматики і ланцюгові умовні довільні поля.
Переклад А. Бобкової
Miyao, Y. Feature Forest Models for Probabilistic HPSG Parsing [Моделі лісу ознак для вірогіднісного синтаксичного аналізу на основі HPSG] / Yusuke Miyao, Jun'ichi Tsujii // Computational linguistics. – 2008. – Vol. 34. – No. 1. – Pages 35–80. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli.2008.34.1.35#.WIXSaX3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli.2008.34.1.35
Вірогіднісне моделювання лексикалізованих граматик є складним завданням, оскільки ці граматики використовують складні структури даних, такі як структури типізованих ознак. Це дозволяє уникнути застосування звичайних методів вірогіднісного моделювання, у яких уся структура ділиться на підструктури, виходячи з припущення про статистичну незалежність підструктур. Наприклад, частиномовна розмітка речення розкладається на розмітку кожного слова, а автоматичний синтаксичний аналіз на основі контекстно-вільної граматики (КВГ) розкладається на застосування правил КВГ. Ці методи спираються на структуру поставленого завдання, тобто решітки і дерева, і не можуть застосовуватися до структур графів, які включають структури типізованих ознак.
У статті пропонується вирішити проблему вірогіднісного моделювання складних структур даних, зокрема структур типізованих ознак, за допомогою моделі лісу ознак. Модель лісу ознак допускає спосіб вірогіднісного моделювання без припущення про незалежність, якщо вірогіднісні події представлені лісами ознак. Ліси ознак є універсальними структурами даних, які представляють омонімічні дерева у спакованій структурі лісу. Моделі лісу ознак є моделями максимальної ентропії, визначеними на основі лісів ознак. Для оцінки по методу максимальної ентропії без розпакування лісів ознак запропоновано алгоритм динамічного програмування. Отже, вірогіднісне моделювання будь-яких структур даних є можливим, якщо вони представлені лісами ознак.
У статті також описано методи представлення за допомогою лісів ознак синтаксичних структур граматики HPSG і предикатно-аргументних структур. Отже, у статті подано повний опис сратегії розробки вірогіднісних моделей для синтаксичного аналізу на основі граматики HPSG. Ефективність запропонованих методів емпірично оцінена за допомогою експериментів із синтаксичним аналізом на основі корпусу Penn Treebank, проаналізовано можливість їх застосування для синтаксичного аналізу реальних речень.
Вірогіднісне моделювання лексикалізованих граматик є складним завданням, оскільки ці граматики використовують складні структури даних, такі як структури типізованих ознак. Це дозволяє уникнути застосування звичайних методів вірогіднісного моделювання, у яких уся структура ділиться на підструктури, виходячи з припущення про статистичну незалежність підструктур. Наприклад, частиномовна розмітка речення розкладається на розмітку кожного слова, а автоматичний синтаксичний аналіз на основі контекстно-вільної граматики (КВГ) розкладається на застосування правил КВГ. Ці методи спираються на структуру поставленого завдання, тобто решітки і дерева, і не можуть застосовуватися до структур графів, які включають структури типізованих ознак.
У статті пропонується вирішити проблему вірогіднісного моделювання складних структур даних, зокрема структур типізованих ознак, за допомогою моделі лісу ознак. Модель лісу ознак допускає спосіб вірогіднісного моделювання без припущення про незалежність, якщо вірогіднісні події представлені лісами ознак. Ліси ознак є універсальними структурами даних, які представляють омонімічні дерева у спакованій структурі лісу. Моделі лісу ознак є моделями максимальної ентропії, визначеними на основі лісів ознак. Для оцінки по методу максимальної ентропії без розпакування лісів ознак запропоновано алгоритм динамічного програмування. Отже, вірогіднісне моделювання будь-яких структур даних є можливим, якщо вони представлені лісами ознак.
У статті також описано методи представлення за допомогою лісів ознак синтаксичних структур граматики HPSG і предикатно-аргументних структур. Отже, у статті подано повний опис сратегії розробки вірогіднісних моделей для синтаксичного аналізу на основі граматики HPSG. Ефективність запропонованих методів емпірично оцінена за допомогою експериментів із синтаксичним аналізом на основі корпусу Penn Treebank, проаналізовано можливість їх застосування для синтаксичного аналізу реальних речень.
Переклад В. Коломієць
Riggle, J. The Complexity of Ranking Hypotheses in Optimality Theory [Складність ранжування гіпотез у теорії оптимальності] / Jason Riggle // Computational linguistics. – 2009. – Vol. 35. – No. 1. – Pages 47–59. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli.07-031-R2-06-98#.WIXTcH3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli.07-031-R2-06-98
Якщо маємо задану обмеженнями множину з k обмеженнями в рамках теорії оптимальності (англ. Optimality Theory, скор. OT), яка її здатність стати класифікаційною схемою для лінгвістичних даних? Одна корисна міра цієї здатності – обсяг найбільшого набору даних, у якому кожна підвибірка узгоджується з унікальною граматичною гіпотезою. Ця міра відома як розмірність Вапника-Червоненкіса (англ. Vapnik-Chervonenkis dimension, скор. VCD) і є стандартною мірою складності для класів понять у теорії складності обчислень. У статті використовується тризначна логіка базових умов ранжування для того, щоб показати, що VCD теорії оптимальності з k обмеженнями становить k-1. Аналіз OT з точки зору VCD свідчить, що складність OT є регулярною функцією k і що «складність» обчислень в OT має лінійний вигляд у k для великої кількості теорій, які використовують вірогіднісні визначення складності.
Якщо маємо задану обмеженнями множину з k обмеженнями в рамках теорії оптимальності (англ. Optimality Theory, скор. OT), яка її здатність стати класифікаційною схемою для лінгвістичних даних? Одна корисна міра цієї здатності – обсяг найбільшого набору даних, у якому кожна підвибірка узгоджується з унікальною граматичною гіпотезою. Ця міра відома як розмірність Вапника-Червоненкіса (англ. Vapnik-Chervonenkis dimension, скор. VCD) і є стандартною мірою складності для класів понять у теорії складності обчислень. У статті використовується тризначна логіка базових умов ранжування для того, щоб показати, що VCD теорії оптимальності з k обмеженнями становить k-1. Аналіз OT з точки зору VCD свідчить, що складність OT є регулярною функцією k і що «складність» обчислень в OT має лінійний вигляд у k для великої кількості теорій, які використовують вірогіднісні визначення складності.
Переклад В. Коломієць
Huang, L. Binarization of Synchronous Context-Free Grammars [Бінаризація синхронних контекстно-вільних граматик] / Liang Huang, Hao Zhang, Daniel Gildea, Kevin Knight // Computational linguistics. – 2009. – Vol. 35. – No. 4. – Pages 559–595. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli.2009.35.4.35406#.WIXUzH3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli.2009.35.4.35406
Системи на основі синхронних граматик і перетворювачів дерев обіцяють поліпшити якість статистичного машинного перекладу, але вони часто потребують величезних обчислювальних потужностей. Через довільне переупорядкування між двома мовами складність в обсязі окремих граматичних правил стрімко зростає. Нами розроблена теорія бінаризації для синхронних контекстно-вільних граматик і описано лінійний за часом алгоритм для бінаризаціїї синхронних правил, якщо це можливо. Проведені нами широкомасштабні експерименти виявили, що майже всі правила бінаризуються і отриманий набір бінаризованих правил значно покращує швидкість і точність сучасної системи машинного перекладу на основі синтаксису. Також проаналізована загальніша, і складніша в обчислювальному плані, проблема знаходження ефективних стратегій синтаксичного аналізу для правил, які неможливо бінаризувати, і описано приблизний алгоритм поліноміального часу для цієї проблеми.
Системи на основі синхронних граматик і перетворювачів дерев обіцяють поліпшити якість статистичного машинного перекладу, але вони часто потребують величезних обчислювальних потужностей. Через довільне переупорядкування між двома мовами складність в обсязі окремих граматичних правил стрімко зростає. Нами розроблена теорія бінаризації для синхронних контекстно-вільних граматик і описано лінійний за часом алгоритм для бінаризаціїї синхронних правил, якщо це можливо. Проведені нами широкомасштабні експерименти виявили, що майже всі правила бінаризуються і отриманий набір бінаризованих правил значно покращує швидкість і точність сучасної системи машинного перекладу на основі синтаксису. Також проаналізована загальніша, і складніша в обчислювальному плані, проблема знаходження ефективних стратегій синтаксичного аналізу для правил, які неможливо бінаризувати, і описано приблизний алгоритм поліноміального часу для цієї проблеми.
Переклад В. Коломієць
Nesson, R. Complexity, Parsing, and Factorization of Tree-Local Multi-Component Tree-Adjoining Grammar [Складність, синтаксичний аналіз і факторизація багатокомпонентної граматики з’єднання дерев у часткові дерева] / Rebecca Nesson, Giorgio Satta, Stuart M. Shieber // Computational linguistics. – 2010. – Vol. 36. – No. 3. – Pр. 443–480. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli_a_00005#.WH6Ecn3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli_a_00005
Багатокомпонентна граматика з’єднання дерев у часткові дерева (Tree-Local Multi-Component Tree-Adjoining Grammar, скор. TL-MCTAG) є привабливим формалізмом для репрезентації природної мови, бо уважається, що вона уможливлює інкапсуляцію правильної області розташування всередині своїх базових структур. Її багатокомпонентна структура дозволяє моделювати лексичні одиниці, елементи яких можуть знаходитися у реченні на великій відстані один від одного, такі як квантифікатори і питальні слова. Коли вона використовується як базовий формалізм для синхронної граматики, її гнучкість дозволяє їй виражати як тісні зв’язки, так і неоднорідну структуру, потрібні для визначення зв’язків між синтаксисом і семантикою однієї мови або синтаксисом двох різних мов. Її помірна виразність обмежує відхилення і, на нашу думку, можливо надала їй додаткової популярності, яка грунтується на неправильному уявленні про складність її синтаксичного аналізу.
Хоча під час першого преставлення TL-MCTAG було показано, що за експресивністю вона еквівалентна граматиці з’єднання дерев, складність TL-MCTAG все ще недостатньо вивчена. У статті детально описано дослідження проблеми розпізнавання TL-MCTAG, яке свідчить, що навіть найбільш обмежені форми TL-MCTAG є НП-повними для розпізнавання. Проте незважаючи на довідну складність проблеми розпізнавання, ми запропонували кілька алгоритмів, які можуть суттєво поліпшити ефективність обробки. По-перше, ми описали алгоритм синтаксичного аналізу, який удосконалює базовий метод синтаксичного аналізу і здійснює обробку за поліноміальний час, коли у вхідній граматиці обмежені як максимальна кількість дерев у наборі дерев, так і максимальна кількість дерев, які можна з’єднати у задане дерево. По-друге, ми запропонували оптимальний, ефективний алгоритм факторизації граматики для отримання високоеквівалентної TL-MCTAG із мінімальною кількістю дерев у дереві.
Багатокомпонентна граматика з’єднання дерев у часткові дерева (Tree-Local Multi-Component Tree-Adjoining Grammar, скор. TL-MCTAG) є привабливим формалізмом для репрезентації природної мови, бо уважається, що вона уможливлює інкапсуляцію правильної області розташування всередині своїх базових структур. Її багатокомпонентна структура дозволяє моделювати лексичні одиниці, елементи яких можуть знаходитися у реченні на великій відстані один від одного, такі як квантифікатори і питальні слова. Коли вона використовується як базовий формалізм для синхронної граматики, її гнучкість дозволяє їй виражати як тісні зв’язки, так і неоднорідну структуру, потрібні для визначення зв’язків між синтаксисом і семантикою однієї мови або синтаксисом двох різних мов. Її помірна виразність обмежує відхилення і, на нашу думку, можливо надала їй додаткової популярності, яка грунтується на неправильному уявленні про складність її синтаксичного аналізу.
Хоча під час першого преставлення TL-MCTAG було показано, що за експресивністю вона еквівалентна граматиці з’єднання дерев, складність TL-MCTAG все ще недостатньо вивчена. У статті детально описано дослідження проблеми розпізнавання TL-MCTAG, яке свідчить, що навіть найбільш обмежені форми TL-MCTAG є НП-повними для розпізнавання. Проте незважаючи на довідну складність проблеми розпізнавання, ми запропонували кілька алгоритмів, які можуть суттєво поліпшити ефективність обробки. По-перше, ми описали алгоритм синтаксичного аналізу, який удосконалює базовий метод синтаксичного аналізу і здійснює обробку за поліноміальний час, коли у вхідній граматиці обмежені як максимальна кількість дерев у наборі дерев, так і максимальна кількість дерев, які можна з’єднати у задане дерево. По-друге, ми запропонували оптимальний, ефективний алгоритм факторизації граматики для отримання високоеквівалентної TL-MCTAG із мінімальною кількістю дерев у дереві.
Переклад В. Коломієць
Erk, K. A Flexible, Corpus-Driven Model of Regular and Inverse Selectional Preferences [Гнучка корпусно-керована модель регулярної і зворотної вірогідної сполучуваності] / Katrin Erk, Sebastian Padó, Ulrike Padó // Computational linguistics. – 2010. – Vol. 36. – No. 4. – Pages 723–763. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli_a_00017#.WIXWVX3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli_a_00017
У статті представлена модель вірогідної сполучуваності на основі векторного простору, яка вираховує показник імовірності для стрижневих слів аргументів. Модель не потребує жодних лексичних ресурсів (таких як WordNet). Її можна навчати як на одному синтаксично анотованому корпусі, так і поєднуючи невеликий за обсягом вихідний корпус із семантичною розміткою та великий узагальнюючий корпус із синтаксичною розміткою. Наша модель здатна передбачити зворотну вірогідну сполучуваність, тобто показники імовірності для предикатів з урахуванням стрижневих слів аргументів.
Для оцінки розробленої моделі було використано одне завдання з обробки природної мови (псевдо-зняття неоднозначностей) та одне когнітивне завдання (прогнозування експертних оцінок достовірності), визначено вплив різних параметрів і здійснено порівняння розробленої моделі з іншими класами моделей. Використання вирішення лексичної неоднозначності та інформації про сематичні ролі, яка міститься у семантично анотованому вихідному корпусі, забезпечило постійні переваги. Відносно параметрів, визначено налаштування, які забезпечують високу продуктивність у різних експериментальних умовах. Проте, основним чинником, який впливає на якість прогнозування, залишається частота. Також визначено більш детальні налаштування параметрів, потрібних для завдань із великою кількістю низькочастотних одиниць .
У статті представлена модель вірогідної сполучуваності на основі векторного простору, яка вираховує показник імовірності для стрижневих слів аргументів. Модель не потребує жодних лексичних ресурсів (таких як WordNet). Її можна навчати як на одному синтаксично анотованому корпусі, так і поєднуючи невеликий за обсягом вихідний корпус із семантичною розміткою та великий узагальнюючий корпус із синтаксичною розміткою. Наша модель здатна передбачити зворотну вірогідну сполучуваність, тобто показники імовірності для предикатів з урахуванням стрижневих слів аргументів.
Для оцінки розробленої моделі було використано одне завдання з обробки природної мови (псевдо-зняття неоднозначностей) та одне когнітивне завдання (прогнозування експертних оцінок достовірності), визначено вплив різних параметрів і здійснено порівняння розробленої моделі з іншими класами моделей. Використання вирішення лексичної неоднозначності та інформації про сематичні ролі, яка міститься у семантично анотованому вихідному корпусі, забезпечило постійні переваги. Відносно параметрів, визначено налаштування, які забезпечують високу продуктивність у різних експериментальних умовах. Проте, основним чинником, який впливає на якість прогнозування, залишається частота. Також визначено більш детальні налаштування параметрів, потрібних для завдань із великою кількістю низькочастотних одиниць .
Переклад М. Погребної
Sygal, Y. Towards Modular Development of Typed Unification Grammars [На шляху до модульної розбудови типізованих уніфікаційних граматик] / Yael Sygal, Shuly Wintner // Computational linguistics. – 2011. – Vol. 37. – No. 1. – Pages 29–74. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/coli_a_00035#.WIXW-n3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/coli_a_00035
Створення великомасштабних граматик природних мов є складним завданням. Граматики створюються колективно командами лінгвістів, комп’ютерних лінгвістів і програмістів так само, як створюється великомасштабне програмне забезпечення. Граматики пишуться за допомогою граматичних формалізмів, які нагадують мови програмування дуже високого рівня, і тому є дуже схожими на комп’ютерні програми. Проте розробка граматик все ще знаходиться на початковій стадії розвитку. Дуже мало середовищ розробки граматики підтримують створення складних модульних граматик шляхом розподілу завдань по створенню граматики, комбінування підграматик, нарізної компіляції і автоматичної компоновки, інкапсуляції даних тощо.
Ця праця заклала базовий фундамент для модульної розбудови типізованих уніфікаційних граматик природніх мов. Переважна частина даних у таких формалізмах шифрується за допомогою сигнатури типу, отже в даному дослідженні проблема розв’язується шляхом розподілу сигнатур між різними модулями. Наведено визначення сигнатурного модуля і запропоновано оператори комбінування модулів. Модулі можуть визначати лише частину інформації про компоненти сигнатури і можуть спілкуватися через параметри, так само як виклики функцій у мовах програмування. В основу запропонованих визначень покладено методи і прийоми теорії мов програмування і розробки програмного забезпечення, а також реальні потреби розробників граматик, визначені шляхом ретельного аналізу існуючих граматик. Показано, що наведені визначення відповідають цим потребам, оскільки задовольняють детальний набір побажань. Користь запропонованих визначень продемонстрована шляхом наведення модульної конструкції HPSG-граматики К. Полларда та І. Сага.
Створення великомасштабних граматик природних мов є складним завданням. Граматики створюються колективно командами лінгвістів, комп’ютерних лінгвістів і програмістів так само, як створюється великомасштабне програмне забезпечення. Граматики пишуться за допомогою граматичних формалізмів, які нагадують мови програмування дуже високого рівня, і тому є дуже схожими на комп’ютерні програми. Проте розробка граматик все ще знаходиться на початковій стадії розвитку. Дуже мало середовищ розробки граматики підтримують створення складних модульних граматик шляхом розподілу завдань по створенню граматики, комбінування підграматик, нарізної компіляції і автоматичної компоновки, інкапсуляції даних тощо.
Ця праця заклала базовий фундамент для модульної розбудови типізованих уніфікаційних граматик природніх мов. Переважна частина даних у таких формалізмах шифрується за допомогою сигнатури типу, отже в даному дослідженні проблема розв’язується шляхом розподілу сигнатур між різними модулями. Наведено визначення сигнатурного модуля і запропоновано оператори комбінування модулів. Модулі можуть визначати лише частину інформації про компоненти сигнатури і можуть спілкуватися через параметри, так само як виклики функцій у мовах програмування. В основу запропонованих визначень покладено методи і прийоми теорії мов програмування і розробки програмного забезпечення, а також реальні потреби розробників граматик, визначені шляхом ретельного аналізу існуючих граматик. Показано, що наведені визначення відповідають цим потребам, оскільки задовольняють детальний набір побажань. Користь запропонованих визначень продемонстрована шляхом наведення модульної конструкції HPSG-граматики К. Полларда та І. Сага.
Переклад В. Коломієць
Greenhill, J. S. Levenshtein Distances Fail to Identify Language Relationships Accurately [Відстані Левенштейна нездатні точно визначати ступені спорідненості мов] / Simon J. Greenhill // Computational linguistics. – 2011. – Vol. 37. – No. 4. – Pages 689–698. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00073#.WIUU8n3sSGA – Режим доступу до повнотекстової статті:
http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00073
Відстань Левенштейна – це проста міра відстані, що дорівнює кількості операцій редагування, необхідних для перетворення одного рядка в інший. Останнім часом цією мірою цікавляться як засобом автоматичної класифікації мов на генеалогічні підгрупи. У статті ефективність використання відстані Левенштейна для класифікації мов протестована шляхом субдискретизації трьох мовніх підгруп з великої бази даних австронезійських мов. Порівняння класифікації, отриманої за допомогою відстані Левенштейна, з класифікацією, отриманою за допомогою порівняльного методу, свідчить про те, що точність класифікації на основі відстані Левенштейна становить 40%. Стандартизація орфографії поліпшує результати продуктивності, але не більше ніж до 65% точності всередині мовних підгруп. Точність класифікації на основі відстані Левенштейна різко зменшується з філогенетичною відстанню, унеможливлюючи розрізнення гомологічності і випадкової схожості віддалено споріднених мов. Така низька продуктивність свідчить про необхідність лінгвістично чутливіших методів для автоматичної класифікації мов.
http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00073
Відстань Левенштейна – це проста міра відстані, що дорівнює кількості операцій редагування, необхідних для перетворення одного рядка в інший. Останнім часом цією мірою цікавляться як засобом автоматичної класифікації мов на генеалогічні підгрупи. У статті ефективність використання відстані Левенштейна для класифікації мов протестована шляхом субдискретизації трьох мовніх підгруп з великої бази даних австронезійських мов. Порівняння класифікації, отриманої за допомогою відстані Левенштейна, з класифікацією, отриманою за допомогою порівняльного методу, свідчить про те, що точність класифікації на основі відстані Левенштейна становить 40%. Стандартизація орфографії поліпшує результати продуктивності, але не більше ніж до 65% точності всередині мовних підгруп. Точність класифікації на основі відстані Левенштейна різко зменшується з філогенетичною відстанню, унеможливлюючи розрізнення гомологічності і випадкової схожості віддалено споріднених мов. Така низька продуктивність свідчить про необхідність лінгвістично чутливіших методів для автоматичної класифікації мов.
Переклад В. Коломієць
Schütze, H. Half-Context Language Models [Напівконтекстні моделі мови] / Hinrich Schütze, Michael Walsh // Computational linguistics. – 2011. – Vol. 37. – No. 4. – Pages 843–865. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00078#.WIXXe33sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00078
У статті досліджується вплив різних ступенів деталізації контексту на продуктивність моделі мови. Описано нову модель мови, яка поєднує в собі кластеризацию і часткову контекстуалізацію, новий спосіб представлення контекстів. Основою часткової контекстуалізації є гіпотеза про частковий контекст, згідно з якою найкращого представлення дистрибутивних характеристик слова або біграма можна досягти, аналізуючи окремо його дистрибуцію у правому і лівому контекстах і беручи до уваги лише найголовнішу інформацію про дистрибуцію. Кластеризація виконується за допомогою нового алгоритму кластеризації для мовних моделей на основі класів, який вигідно відрізняється від алгоритму обміну. Показано, що у поєданні з моделлю Кнезера-Нея напівконтекстні моделі досягають вищого показника невизначеності, ніж широко використовувані інтерпольовані моделі на основі n-грамів та традиційні підходи на основі класів. Новий, детальний, контекстнозалежний аналіз виділяє ті контексти, у яких модель досягає високої ефективності, і ті, які краще аналізувати за допомогою існуючих моделей, які не базуються на класах.
У статті досліджується вплив різних ступенів деталізації контексту на продуктивність моделі мови. Описано нову модель мови, яка поєднує в собі кластеризацию і часткову контекстуалізацію, новий спосіб представлення контекстів. Основою часткової контекстуалізації є гіпотеза про частковий контекст, згідно з якою найкращого представлення дистрибутивних характеристик слова або біграма можна досягти, аналізуючи окремо його дистрибуцію у правому і лівому контекстах і беручи до уваги лише найголовнішу інформацію про дистрибуцію. Кластеризація виконується за допомогою нового алгоритму кластеризації для мовних моделей на основі класів, який вигідно відрізняється від алгоритму обміну. Показано, що у поєданні з моделлю Кнезера-Нея напівконтекстні моделі досягають вищого показника невизначеності, ніж широко використовувані інтерпольовані моделі на основі n-грамів та традиційні підходи на основі класів. Новий, детальний, контекстнозалежний аналіз виділяє ті контексти, у яких модель досягає високої ефективності, і ті, які краще аналізувати за допомогою існуючих моделей, які не базуються на класах.
Переклад М. Погребної
Cohen, B. S. Empirical Risk Minimization for Probabilistic Grammars: Sample Complexity and Hardness of Learning [Емпірична мінімізація ризику для імовірнісних граматик: кількість прикладів і складність навчання] / Shay B. Cohen, Noah A. Smith // Computational linguistics. – 2012. – Vol. 38. – No. 3. – Pages 479–526. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00092#.WIXaWn3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00092
Імовірнісні граматики – це генеративні статистичні моделі, корисні для композиційних і послідовних структур. Вони широко застосовуються у комп’ютерній лінгвістиці. У статті описано схожу на структурну мінімізацію ризику концепцію емпіричної мінімізації ризику імовірнісних граматик за допомогою логарифмічного декремента. У цій концепції визначено кількість прикладів, яка потрібна як для навчання з учителем, так і для навчання без учителя. Висуваючи відповідні описам природних мов припущення про вихідний розподіл, можна на основі розподілу визначити потрібну кількість прикладів для імовірнісних граматик. Також наведено прості алгоритми для здійснення емпіричної мінімізації ризику, використовуючи цю концепцію як із залученням учителя, так і без учителя. Показано, що у навчанні без учителя проблема мінімізації емпіричного ризику є НП-складною. Тому для мінімізації емпіричного ризику запропоновано приблизний алгоритм, схожий на максимізацію очікувань.
Імовірнісні граматики – це генеративні статистичні моделі, корисні для композиційних і послідовних структур. Вони широко застосовуються у комп’ютерній лінгвістиці. У статті описано схожу на структурну мінімізацію ризику концепцію емпіричної мінімізації ризику імовірнісних граматик за допомогою логарифмічного декремента. У цій концепції визначено кількість прикладів, яка потрібна як для навчання з учителем, так і для навчання без учителя. Висуваючи відповідні описам природних мов припущення про вихідний розподіл, можна на основі розподілу визначити потрібну кількість прикладів для імовірнісних граматик. Також наведено прості алгоритми для здійснення емпіричної мінімізації ризику, використовуючи цю концепцію як із залученням учителя, так і без учителя. Показано, що у навчанні без учителя проблема мінімізації емпіричного ризику є НП-складною. Тому для мінімізації емпіричного ризику запропоновано приблизний алгоритм, схожий на максимізацію очікувань.
Переклад В. Коломієць
Kuhlmann, M. Tree-Adjoining Grammars Are Not Closed Under Strong Lexicalization [Граматики з’єднання дерев не закриваються під впливом сильної лексикалізації] / Marco Kuhlmann, Giorgio Satta // Computational linguistics. – 2012. – Vol. 38. – No. 3. – Pр. 617–629. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00090#.WH6G-33sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00090
Лексикалізована граматика з’єднання дерев – це граматика з’єднання дерев, у якій кожне атомарне дерево містить якусь очевидну лексичну одиницю. Такі граматики використовуються для надання лексичних пояснень синтаксичних явищ, у яких початкове дерево визначає домен розташування синтаксичних і семантичних залежностей його лексичних одиниць. У літературі стверджувалося, що для кожної граматики з’єднання дерев можна сконструювати абсолютно еквівалентну лексикалізовану версію. Ми показали, що подібної процедури не існує. Граматики з’єднання дерев не закриваються під впливом сильної лексикалізації.
Лексикалізована граматика з’єднання дерев – це граматика з’єднання дерев, у якій кожне атомарне дерево містить якусь очевидну лексичну одиницю. Такі граматики використовуються для надання лексичних пояснень синтаксичних явищ, у яких початкове дерево визначає домен розташування синтаксичних і семантичних залежностей його лексичних одиниць. У літературі стверджувалося, що для кожної граматики з’єднання дерев можна сконструювати абсолютно еквівалентну лексикалізовану версію. Ми показали, що подібної процедури не існує. Граматики з’єднання дерев не закриваються під впливом сильної лексикалізації.
Переклад В. Коломієць
Tan, M. A Scalable Distributed Syntactic, Semantic, and Lexical Language Model [Широкомасштабна розподілена синтаксична, семантична і лексична модель мови] / Ming Tan, Wenli Zhou, Lei Zheng, Shaojun Wang // Computational linguistics. – 2012. – Vol. 38. – No. 3. – Pages 631–671. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00107#.WIXa5H3sSGA – Режим доступу до повнотекстової статті:
http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00107
У статті зроблено спробу побудувати широкомасштабну розподілену складену мовну модель, створену органічним об'єднанням N-грамної моделі, структурної моделі мови та імовірнісного латентно-семантичного аналізу під спрямованою парадигмою випадкових полів Маркова для одночасного пояснення лексичного значення локального слова, синтаксичної структури середньомасштабного речення і семантичного змісту довгого документу. Складену мовну модель навчали шляхом виконання наближеного EM-алгоритму з конвергентним списком N-кращих гіпотез і додаткового EM-алгоритму з метою покращення ефективності передбачення слів на основі корпусів обсягом до мільярда слів. Модель зберігали у суперкомп'ютері. Широкомасштабна розподілена складена мовна модель дає різке зменшення перплексивності N-грамів і досягає значно кращої якості перекладу за метрикою Bleu і "читабельності" перекладів при повторному ранжуванні списку N-кращих гіпотез із сучасної системи машинного перекладу на основі синтаксичного аналізу.
http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00107
У статті зроблено спробу побудувати широкомасштабну розподілену складену мовну модель, створену органічним об'єднанням N-грамної моделі, структурної моделі мови та імовірнісного латентно-семантичного аналізу під спрямованою парадигмою випадкових полів Маркова для одночасного пояснення лексичного значення локального слова, синтаксичної структури середньомасштабного речення і семантичного змісту довгого документу. Складену мовну модель навчали шляхом виконання наближеного EM-алгоритму з конвергентним списком N-кращих гіпотез і додаткового EM-алгоритму з метою покращення ефективності передбачення слів на основі корпусів обсягом до мільярда слів. Модель зберігали у суперкомп'ютері. Широкомасштабна розподілена складена мовна модель дає різке зменшення перплексивності N-грамів і досягає значно кращої якості перекладу за метрикою Bleu і "читабельності" перекладів при повторному ранжуванні списку N-кращих гіпотез із сучасної системи машинного перекладу на основі синтаксичного аналізу.
Переклад Т. Павлущенко і М. Погребної
Lembersky, G. Language Models for Machine Translation: Original vs. Translated Texts [Мовні моделі для машинного перекладу: порівняння оригінальних і перекладених текстів] / Gennadi Lembersky, Noam Ordan, Shuly Wintner // Computational linguistics. – 2012. – Vol. 38. – No. 4. – Pages 799–825. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00111#.WIdNqH3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00111
У статті досліджуються відмінності між мовними моделями, створеними на основі оригінальних текстів мовою перекладу, і моделями, створеними на основі текстів, вручну перекладених на мову перекладу. На підтвердження загальновідомих спостережень перекладознавців продемонстровано, що останні є значно кращими індикаторами перекладених речень, ніж перші, а тому краще підходять для набору зразків. Більше того, перекладені тексти дозволяють отримати кращі мовні моделі для статистичного машинного перекладу, ніж оригінальні тексти.
У статті досліджуються відмінності між мовними моделями, створеними на основі оригінальних текстів мовою перекладу, і моделями, створеними на основі текстів, вручну перекладених на мову перекладу. На підтвердження загальновідомих спостережень перекладознавців продемонстровано, що останні є значно кращими індикаторами перекладених речень, ніж перші, а тому краще підходять для набору зразків. Більше того, перекладені тексти дозволяють отримати кращі мовні моделі для статистичного машинного перекладу, ніж оригінальні тексти.
Переклад В. Коломієць
Wedekind, J. LFG Generation by Grammar Specialization [Генерування ЛФГ шляхом спеціалізації граматики] / Jürgen Wedekind, Ronald M. Kaplan // Computational linguistics. – 2012. – Vol. 38. – No. 4. – Pages 867–915. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00113#.WIXbln3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00113
У статті описано підхід до генерування лексико-функціональної граматики (ЛФГ), яка базується на тому факті, що набір ланцюгів, які ЛФГ пов’язує з певною ациклічною f-структурою, є контекстно-вільною мовою. У статті описано алгоритм створення для довільної ЛФГ і довільної вихідної ациклічної f-структури контекстно-вільної граматики, яка описує саме той набір ланцюгів, які вказана ЛФГ асоціює з цією f-структурою. Конкретні речення потім подаються через стандартний контекстно-вільний генератор, який працює на основі цієї граматики. Контекстно-вільна граматика будується шляхом адаптації контекстно-вільної основи ЛФГ для конкретної f-структури і є компактним представленням усіх результатів генерації, які ЛФГ ставить у відповідність із уведенням. Вказаний підхід розповсюджується на інші граматичні формалізми із очевидними контекстно-вільними основами, такі як PATR, а також на формалізми, які дозволяють видобути контекстно-вільну основу із складніших специфікацій. Він забезпечує загальну математичну концептуальну схему для розуміння і удосконалення функціонування серії алгоритмів генерування на основі блок-схем.
У статті описано підхід до генерування лексико-функціональної граматики (ЛФГ), яка базується на тому факті, що набір ланцюгів, які ЛФГ пов’язує з певною ациклічною f-структурою, є контекстно-вільною мовою. У статті описано алгоритм створення для довільної ЛФГ і довільної вихідної ациклічної f-структури контекстно-вільної граматики, яка описує саме той набір ланцюгів, які вказана ЛФГ асоціює з цією f-структурою. Конкретні речення потім подаються через стандартний контекстно-вільний генератор, який працює на основі цієї граматики. Контекстно-вільна граматика будується шляхом адаптації контекстно-вільної основи ЛФГ для конкретної f-структури і є компактним представленням усіх результатів генерації, які ЛФГ ставить у відповідність із уведенням. Вказаний підхід розповсюджується на інші граматичні формалізми із очевидними контекстно-вільними основами, такі як PATR, а також на формалізми, які дозволяють видобути контекстно-вільну основу із складніших специфікацій. Він забезпечує загальну математичну концептуальну схему для розуміння і удосконалення функціонування серії алгоритмів генерування на основі блок-схем.
Переклад В. Коломієць
Kuhlmann, M. Mildly Non-Projective Dependency Grammar [Помірно непроективна граматика залежностей] / Marco Kuhlmann // Computational linguistics. – 2013. – Vol. 39. – No. 2. – Pр. 355–387. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00125#.WH6Km33sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00125
Синтаксичні представлення на основі залежностей між словами мають давню традицію у дескриптивній лінгвістиці і активно використовуються у численних прикладних програмах. Проте з формальної точки зору граматика залежностей залишається до деякої міри автономією. Більше того, більшість наявних формалізмів граматики залежностей використовуються лише у проективному аналізі і через це не можуть забезпечити зрозумілого відображення таких явищ як переміщення питального слова або перехресні залежності.
У статті представлено формалізм непроективної граматики залежностей у контексті лінійних контекстно-вільних систем переписування. Характерною особливістю нашого формалізму є тісна відповідність між непроективними деревами залежностей, які допускає граматика, з одного боку і граматичною складністю синтаксичного розбору з другого боку. Ми показуємо, що синтаксичний аналіз на основі необмеженої граматики є важкоконтрольованим. Через це ми аналізуємо два обмеження непроективності: рівень блокування і високий рівень вкладеності. Разом ці два обмеження визначають клас помірно непроективних граматик залежностей, які можна аналізувати за поліноміальний час. Тестування з використанням п’яти банків дерев залежностей показало, що ці граматики ефективно обробляють емпіричні дані.
Синтаксичні представлення на основі залежностей між словами мають давню традицію у дескриптивній лінгвістиці і активно використовуються у численних прикладних програмах. Проте з формальної точки зору граматика залежностей залишається до деякої міри автономією. Більше того, більшість наявних формалізмів граматики залежностей використовуються лише у проективному аналізі і через це не можуть забезпечити зрозумілого відображення таких явищ як переміщення питального слова або перехресні залежності.
У статті представлено формалізм непроективної граматики залежностей у контексті лінійних контекстно-вільних систем переписування. Характерною особливістю нашого формалізму є тісна відповідність між непроективними деревами залежностей, які допускає граматика, з одного боку і граматичною складністю синтаксичного розбору з другого боку. Ми показуємо, що синтаксичний аналіз на основі необмеженої граматики є важкоконтрольованим. Через це ми аналізуємо два обмеження непроективності: рівень блокування і високий рівень вкладеності. Разом ці два обмеження визначають клас помірно непроективних граматик залежностей, які можна аналізувати за поліноміальний час. Тестування з використанням п’яти банків дерев залежностей показало, що ці граматики ефективно обробляють емпіричні дані.
Переклад Д. Попової
Crabbé, B. XMG: eXtensible MetaGrammar [XMG: розширювана метаграматика] / Benoît Crabbé, Denys Duchier, Claire Gardent, Joseph Le Roux, Yannick Parmentier // Computational linguistics. – 2013. – Vol. 39. – No. 3 – Pages 591–629. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00144#.WIXcGn3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00144
Стаття знайомить із eXtensible MetaGrammar (XMG), концепцією для опису граматик на основі дерев, таких як Feature-Based Lexicalized Tree-Adjoining Grammars (FB-LTAG) та Interaction Grammars (IG). Стверджується, що XMG притаманні три характеристики, які полегшують як написання граматик, так і швидке моделювання граматик на основі дерев. По-перше, XMG є повністю декларативною. Наприклад, вона допускає декларативне використання діатези, яка суттєво відійшла від процедурних лексичних правил, які часто використовуються для детального опису граматик на основі дерев. По-друге, мова XMG має високі виражальні можливості, оскільки вона підтримує численні лінгвістичні виміри, успадкування і ретельну обробку індентифікаторів. По-третє, XMG може бути розширена, оскільки її обчислювальна структура дозволяє розширення у інші лінгвістичні формалізми. У статті пояснюється, як ця структура природно підтримує розробку трьох лінгвістичних формалізмів, а саме FB-LTAG, IG і багатокомпонентної граматики складання дерев (англ. Multi-Component Tree-Adjoining Grammar, скор. MC-TAG). Також показано, як вона уможливлює пряму інтеграцію додаткових механізмів, таких як лінгвістичні і формальні принципи. Щоб докладніше проілюструвати декларативність, виражальні можливості і розширюваність XMG, у статті описано методику, яка використовувалась для докладного опису FB-LTAG для французької мови, розширеної композиційною семантикою на основі уніфікації. Це ілюстрація того, як XMG спрощує і моделювання ієрархій фрагментів дерев, необхідне для опису граматик на основі дерев, і синтаксичний/семантичний інтерфейс між семантичними репрезентаціями і синтаксичними деревами. Нарешті, у статті коротко повідомляється про декілька граматик для французької, англійської та німецької мов, які були застосовані на практиці за допомогою XMG і здійснюється порівняння XMG з іншими існуючими концептуальними схемами опису граматик для граматик на основі дерев.
Стаття знайомить із eXtensible MetaGrammar (XMG), концепцією для опису граматик на основі дерев, таких як Feature-Based Lexicalized Tree-Adjoining Grammars (FB-LTAG) та Interaction Grammars (IG). Стверджується, що XMG притаманні три характеристики, які полегшують як написання граматик, так і швидке моделювання граматик на основі дерев. По-перше, XMG є повністю декларативною. Наприклад, вона допускає декларативне використання діатези, яка суттєво відійшла від процедурних лексичних правил, які часто використовуються для детального опису граматик на основі дерев. По-друге, мова XMG має високі виражальні можливості, оскільки вона підтримує численні лінгвістичні виміри, успадкування і ретельну обробку індентифікаторів. По-третє, XMG може бути розширена, оскільки її обчислювальна структура дозволяє розширення у інші лінгвістичні формалізми. У статті пояснюється, як ця структура природно підтримує розробку трьох лінгвістичних формалізмів, а саме FB-LTAG, IG і багатокомпонентної граматики складання дерев (англ. Multi-Component Tree-Adjoining Grammar, скор. MC-TAG). Також показано, як вона уможливлює пряму інтеграцію додаткових механізмів, таких як лінгвістичні і формальні принципи. Щоб докладніше проілюструвати декларативність, виражальні можливості і розширюваність XMG, у статті описано методику, яка використовувалась для докладного опису FB-LTAG для французької мови, розширеної композиційною семантикою на основі уніфікації. Це ілюстрація того, як XMG спрощує і моделювання ієрархій фрагментів дерев, необхідне для опису граматик на основі дерев, і синтаксичний/семантичний інтерфейс між семантичними репрезентаціями і синтаксичними деревами. Нарешті, у статті коротко повідомляється про декілька граматик для французької, англійської та німецької мов, які були застосовані на практиці за допомогою XMG і здійснюється порівняння XMG з іншими існуючими концептуальними схемами опису граматик для граматик на основі дерев.
Переклад В. Коломієць
Kuhn, T. A Survey and Classification of Controlled Natural Languages [Аналіз і класифікація контрольованих природних мов] / Tobias Kuhn // Computational linguistics. – 2014. – Vol. 40. – No. 1. – Pages 121–170. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00168#.WIXcsH3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00168
Те, що у статті називається контрольованою природною мовою (англ. controlled natural language, скор. CNL), відоме під різними назвами. Велика кількість таких мов створена переважно протягом останніх чотирьох десятиліть. Вони використовуються для удосконалення спілкування між людьми, для удосконалення перекладу або для природних і інтуїтивно зрозумілих представлень формальних позначень. Незважаючи на очевидні відмінності, варто об’єднати всі ці мови в одну групу. Для того щоб упорядкувати різні мови, у статті запропонована загальна схема класифікації. Представлено комплексне дослідження існуючих CNL на основі англійської мови, у якому описано 100 мов, створених після 1930 року. Класифікація цих мов свідчить, що вони утворюють єдину розірвану хмару, яка заповнює концептуальний простір між природними мовами, такими як англійська, з одного боку і формальними мовами, такими як пропозиціональна логіка, з іншого боку. Мета статті – розробити спільну термінологію і спільну модель для CNL, сприяти розумінню їх загальної природи, створити вихідний пункт для дослідників у цій галузі і допомогти розробникам у прийнятті проектних рішень.
Те, що у статті називається контрольованою природною мовою (англ. controlled natural language, скор. CNL), відоме під різними назвами. Велика кількість таких мов створена переважно протягом останніх чотирьох десятиліть. Вони використовуються для удосконалення спілкування між людьми, для удосконалення перекладу або для природних і інтуїтивно зрозумілих представлень формальних позначень. Незважаючи на очевидні відмінності, варто об’єднати всі ці мови в одну групу. Для того щоб упорядкувати різні мови, у статті запропонована загальна схема класифікації. Представлено комплексне дослідження існуючих CNL на основі англійської мови, у якому описано 100 мов, створених після 1930 року. Класифікація цих мов свідчить, що вони утворюють єдину розірвану хмару, яка заповнює концептуальний простір між природними мовами, такими як англійська, з одного боку і формальними мовами, такими як пропозиціональна логіка, з іншого боку. Мета статті – розробити спільну термінологію і спільну модель для CNL, сприяти розумінню їх загальної природи, створити вихідний пункт для дослідників у цій галузі і допомогти розробникам у прийнятті проектних рішень.
Переклад В. Коломієць
Chung, T. Sampling Tree Fragments from Forests [Відбір фрагментів дерев із лісів] / Tagyoung Chung, Licheng Fang, Daniel Gildea, Daniel Štefankovič // Computational linguistics. – 2014. – Vol. 40. – No. 1. – Pages 203–229. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00170#.WH6MG33sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00170
У статті досліджується проблема відбору дерев із лісів за умови, що вірогідності для кожного дерева можуть бути функцією довільно великих фрагментів дерева. За цієї умови сучасні проекти по формуванню вибірки для навчання граматик заміщення дерев повинні включати випадки, коли структура дерева (дерево утворене на основі граматики заміщення дерев) не є фіксованою. Розроблено алгоритм Монте Карло з ланцюгами Маркова, який виправляє спотворення, спричинені незбалансованими лісами, і описано експерименти з використанням цього алгоритму для навчання правилам синхронної контекстно-незалежної граматики для машинного перекладу. У цьому додатку відібрані ліси представляють набір правил граматики Hiero, які узгоджуються із фіксованими вихідними вирювнюваннями на рівні слів. Якість машиного перекладу не відрізняється від стандартних методик, але досягається за допомогою значно менших граматик.
У статті досліджується проблема відбору дерев із лісів за умови, що вірогідності для кожного дерева можуть бути функцією довільно великих фрагментів дерева. За цієї умови сучасні проекти по формуванню вибірки для навчання граматик заміщення дерев повинні включати випадки, коли структура дерева (дерево утворене на основі граматики заміщення дерев) не є фіксованою. Розроблено алгоритм Монте Карло з ланцюгами Маркова, який виправляє спотворення, спричинені незбалансованими лісами, і описано експерименти з використанням цього алгоритму для навчання правилам синхронної контекстно-незалежної граматики для машинного перекладу. У цьому додатку відібрані ліси представляють набір правил граматики Hiero, які узгоджуються із фіксованими вихідними вирювнюваннями на рівні слів. Якість машиного перекладу не відрізняється від стандартних методик, але досягається за допомогою значно менших граматик.
Переклад В. Коломієць
Wedekind, J. On the Universal Generation Problem for Unification Grammars [Про універсальну проблему генерації для уніфікаційних граматик] / Jürgen Wedekind // Computational linguistics. – 2014. – Vol. 40. – No. 3. – Pages 533–538. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00191#.WIXdJ33sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00191
Універсальною проблемою генерації для уніфікаційних граматик є проблема визначення, чи породжує певна граматика якийсь термінальний ланцюг із певною ознаковою структурою. Відомо, що для формалізмів LFG і PATR цю проблему можна вирішити, якщо до уваги беруться лише нециклічні ознакові структури. У статті показано, що для циклічних структур вказана проблема є нерозв’язною. Це стосується навіть граматик, які аналізуються автономно.
Універсальною проблемою генерації для уніфікаційних граматик є проблема визначення, чи породжує певна граматика якийсь термінальний ланцюг із певною ознаковою структурою. Відомо, що для формалізмів LFG і PATR цю проблему можна вирішити, якщо до уваги беруться лише нециклічні ознакові структури. У статті показано, що для циклічних структур вказана проблема є нерозв’язною. Це стосується навіть граматик, які аналізуються автономно.
Переклад В. Коломієць
Sproat, R. Applications of Lexicographic Semirings to Problems in Speech and Language Processing [Застосування лексикографічних напівкілець до розв’язання проблем обробки природної мови] / Richard Sproat, Mahsa Yarmohammadi, Izhak Shafran, Brian Roark // Computational linguistics. – 2014. – Vol. 40. – No. 4. – Pages 733–761. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00198#.WIXdbX3sSGA – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00198
У статті досліджуються лексикографічні півкільця та їх застосування у вирішенні проблем обробки природної мови. Зокрема, описано два приклади бінарних лексикографічних півкілець, одне з яких включало пару тропічних вагів, а друге – тропічну вагу разом із півкільцем у новому рядку, названим нами категоріальним півкільцем. Перше з них використовується для отримання точного коду відтермінованих моделей з іпсилон-переходами. Таке лексикографічне півкільце мовної моделі дозволяє оптимізувати в автономному режимі точні моделі, представлені як великі зважені кінцеві перетворювачі на відміну від розмитих (онлайн) моделей зі збоями при переходах. Представлені емпіричні результати свідчать, що навіть у простих переходах, де можуть використовуватися невдалі переходи, використання потужнішого лексикографічного півкільця є доцільним з точки зору часу перетину. Друге з цих лексикографічних півкілець застосовується для вирішення проблеми вилучення з решітки послідовностей слів з частиномовною розміткою лише найкращої частиномовної розмітки для кожної послідовності слів. Здійснюється це шляхом додавання міток в якості категоріальної ваги у другому компоненті 〈Тропічного, Категоріального〉 лексикографічного півкільця, детермінізації користувача отриманою решіткою слів у тому півкільці, а потім використання тегів в якості вихідних міток перетворювача словесних решіток. Цей метод порівнюється з конкуруючим методом Поуві та інших [Povey et al., 2012].
У статті досліджуються лексикографічні півкільця та їх застосування у вирішенні проблем обробки природної мови. Зокрема, описано два приклади бінарних лексикографічних півкілець, одне з яких включало пару тропічних вагів, а друге – тропічну вагу разом із півкільцем у новому рядку, названим нами категоріальним півкільцем. Перше з них використовується для отримання точного коду відтермінованих моделей з іпсилон-переходами. Таке лексикографічне півкільце мовної моделі дозволяє оптимізувати в автономному режимі точні моделі, представлені як великі зважені кінцеві перетворювачі на відміну від розмитих (онлайн) моделей зі збоями при переходах. Представлені емпіричні результати свідчать, що навіть у простих переходах, де можуть використовуватися невдалі переходи, використання потужнішого лексикографічного півкільця є доцільним з точки зору часу перетину. Друге з цих лексикографічних півкілець застосовується для вирішення проблеми вилучення з решітки послідовностей слів з частиномовною розміткою лише найкращої частиномовної розмітки для кожної послідовності слів. Здійснюється це шляхом додавання міток в якості категоріальної ваги у другому компоненті 〈Тропічного, Категоріального〉 лексикографічного півкільця, детермінізації користувача отриманою решіткою слів у тому півкільці, а потім використання тегів в якості вихідних міток перетворювача словесних решіток. Цей метод порівнюється з конкуруючим методом Поуві та інших [Povey et al., 2012].
Переклад А. Синящик
Kuhlmann M. Lexicalization and Generative Power in CCG [Лексикалізація та генеративна ефективність в ККГ] / Marco Kuhlmann, Alexander Koller, Giorgio Satta // Computational linguistics. – 2015. – Vol. 41. – No. 2. – Pages 215–247. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00219 – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00219
Слабка еквівалентність між комбінаторною категоріальною граматикою (ККГ) і граматикою з’єднання дерев (ГЗД) є основним результатом у літературі про граматичні формалізми з помірною залежністю від контексту. Проте, категорійний формалізм, для якого була встановлена ця еквівалентність, суттєво відрізняється від сучасних версій ККГ. Зокрема, він дозволяє обмежувати комбінаторні правила на основі граматики, у той час як сучасні ККГ передбачають універсальний набір правил, що виключає будь-які міжмовні варіації у лексиконі. У статті досліджується формальна значимість цієї розбіжності. Основний висновок полягає в тому, що лексикалізовані версії класичного формалізму ККГ явно менш ефективні, ніж ГЗД.
Слабка еквівалентність між комбінаторною категоріальною граматикою (ККГ) і граматикою з’єднання дерев (ГЗД) є основним результатом у літературі про граматичні формалізми з помірною залежністю від контексту. Проте, категорійний формалізм, для якого була встановлена ця еквівалентність, суттєво відрізняється від сучасних версій ККГ. Зокрема, він дозволяє обмежувати комбінаторні правила на основі граматики, у той час як сучасні ККГ передбачають універсальний набір правил, що виключає будь-які міжмовні варіації у лексиконі. У статті досліджується формальна значимість цієї розбіжності. Основний висновок полягає в тому, що лексикалізовані версії класичного формалізму ККГ явно менш ефективні, ніж ГЗД.
Переклад А. Шульги
Tanaka-Ishii, K. Computational Constancy Measures of Texts—Yule's K and Rényi's Entropy [Міри обчислювальної стійкості текстів – показник Юла (К) та ентропія Реньї] / Kumiko Tanaka-Ishii, Shunsuke Aihara // Computational linguistics. – 2015. – Vol. 41. – No. 3. – Pages 481–502. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00228 – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00228
У статті описно математичну й емпіричну перевірку мір обчислюваної стійкості текстів природною мовою. Міра стійкості характеризує певний текст, приписуючи інваріантну величину будь-якому обсягу, що перевищує певну кількість. Вивчення таких мір проводиться вже 70 років, починаючи з показника Юла (К), який спочатку призначався для встановлення авторства. У статті розглянуто різні міри, запропоновані після Юла, і перевірено зроблені дотепер висновки, тобто зроблено огляд досліджень мір стійкості. Також, у статті пояснено, чому K є по суті еквівалентом апроксимації ентропії Реньї другого порядку, тобто визначено значимість цього показника в лінгвістиці. Крім того, емпірично досліджено кандидатів у міри стійкості в цьому новому, ширшому контексті. Наближена ентропія вищого порядку демонструє стабільне зближення між різними мовами та видами текстів. Втім, також з’ясовано, що, всупереч очікуванням Юла, вона не може встановлювати авторство. Насамкінець, К застосовано до двох невідомих рукописів – манускрипту Войніча та ронго-ронго і продемонстровано, що результати підтверджують попередні гіпотези щодо цих рукописів.
У статті описно математичну й емпіричну перевірку мір обчислюваної стійкості текстів природною мовою. Міра стійкості характеризує певний текст, приписуючи інваріантну величину будь-якому обсягу, що перевищує певну кількість. Вивчення таких мір проводиться вже 70 років, починаючи з показника Юла (К), який спочатку призначався для встановлення авторства. У статті розглянуто різні міри, запропоновані після Юла, і перевірено зроблені дотепер висновки, тобто зроблено огляд досліджень мір стійкості. Також, у статті пояснено, чому K є по суті еквівалентом апроксимації ентропії Реньї другого порядку, тобто визначено значимість цього показника в лінгвістиці. Крім того, емпірично досліджено кандидатів у міри стійкості в цьому новому, ширшому контексті. Наближена ентропія вищого порядку демонструє стабільне зближення між різними мовами та видами текстів. Втім, також з’ясовано, що, всупереч очікуванням Юла, вона не може встановлювати авторство. Насамкінець, К застосовано до двох невідомих рукописів – манускрипту Войніча та ронго-ронго і продемонстровано, що результати підтверджують попередні гіпотези щодо цих рукописів.
Переклад М. Дубка
Karimi, S. Evaluation Methods for Statistically Dependent Text [Методи оцінювання статистично залежних текстів] / Sarvnaz Karimi, Jie Yin, Jiri Baum // Computational linguistics. – 2015. – Vol. 41. – No. 3. – Pages 539–548. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00230 – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00230
Протягом останніх років опубліковано багато досліджень даних, зібраних у соціальних мережах, зокрема в мікроблогах на кшталт Twitter. Проте, лише в кількох з них розглядалися методи оцінювання, які враховують статистично залежний характер таких даних, що порушує теоретичні умови використання перехресної перевірки. Незважаючи на питання, які піднімались у минулому щодо застовання перехресної перевірки до даних зі схожими характеристиками, наприклад, динамічних рядів, деякі з цих досліджень оцінюють свої результати за допомогою стандартної k-кратної перехресної перевірки. Завдяки експериментам на основі даних Twitter, зібраних протягом двохрічного періоду, який включає катастрофічні події, було показано, що через ігнорування статистичної залежності опублікованих у соціальних мережах текстових повідомлень стандартна перехресна перевірка може призвести до помилкових висновків у завданні з машинного навчання. Проаналізовано альтернативні методи оцінювання, які напряму використовують статистичну залежність у тексті. Отримані результати також викликаюь питання до будь-яких інших даних, до яких можна застосувати подібні умови.
Протягом останніх років опубліковано багато досліджень даних, зібраних у соціальних мережах, зокрема в мікроблогах на кшталт Twitter. Проте, лише в кількох з них розглядалися методи оцінювання, які враховують статистично залежний характер таких даних, що порушує теоретичні умови використання перехресної перевірки. Незважаючи на питання, які піднімались у минулому щодо застовання перехресної перевірки до даних зі схожими характеристиками, наприклад, динамічних рядів, деякі з цих досліджень оцінюють свої результати за допомогою стандартної k-кратної перехресної перевірки. Завдяки експериментам на основі даних Twitter, зібраних протягом двохрічного періоду, який включає катастрофічні події, було показано, що через ігнорування статистичної залежності опублікованих у соціальних мережах текстових повідомлень стандартна перехресна перевірка може призвести до помилкових висновків у завданні з машинного навчання. Проаналізовано альтернативні методи оцінювання, які напряму використовують статистичну залежність у тексті. Отримані результати також викликаюь питання до будь-яких інших даних, до яких можна застосувати подібні умови.
Переклад М. Дубка
Paperno, D. When the Whole Is Less Than the Sum of Its Parts: How Composition Affects PMI Values in Distributional Semantic Vectors [Коли ціле є меншим, ніж сума його частин: як структура впливає на значення ПВІ в семантичних контекстних векторах] / Denis Paperno, Marco Baroni // Computational linguistics. – 2016. – Vol. 42. – No. 2. – Pages 345–350. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00250 – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00250
Дистрибутивні семантичні моделі, які виводять представлення слів на основі векторів із прикладів вживання слів у корпусах, мають багато корисних застосувань (Turney and Pantel, 2010). Останнім часом зажили популярності композиційні дистрибутивні моделі, які виводять вектори для фраз з представлень слів, з яких вони складаються (Mitchell and Lapata, 2010). Значення контекстних векторів часто є оцінкою в балах поточкової взаємної інформації (ПВІ), отриманою з грубих показників одночасної появи слів. У статті проаналізовано зв'язок між координатами ПВІ вектора фрази і його компонентів, щоб з’ясувати, які операції повинна виконувати належна композиційна модель. Математично доведено, що величина різниці між координатою ПВІ вектора фрази і сумою показників ПВІ на відповідних координатах частин фрази інтерпретується незалежно, а саме шляхом квантифікації впливу контексту, пов'язаного з відповідною координатою на внутрішній когезії фрази, що також вимірюється за допомогою ПВІ. Потім цей показник досліджено емпірично, шляхом аналізу сполучень прикметник-іменник.
Дистрибутивні семантичні моделі, які виводять представлення слів на основі векторів із прикладів вживання слів у корпусах, мають багато корисних застосувань (Turney and Pantel, 2010). Останнім часом зажили популярності композиційні дистрибутивні моделі, які виводять вектори для фраз з представлень слів, з яких вони складаються (Mitchell and Lapata, 2010). Значення контекстних векторів часто є оцінкою в балах поточкової взаємної інформації (ПВІ), отриманою з грубих показників одночасної появи слів. У статті проаналізовано зв'язок між координатами ПВІ вектора фрази і його компонентів, щоб з’ясувати, які операції повинна виконувати належна композиційна модель. Математично доведено, що величина різниці між координатою ПВІ вектора фрази і сумою показників ПВІ на відповідних координатах частин фрази інтерпретується незалежно, а саме шляхом квантифікації впливу контексту, пов'язаного з відповідною координатою на внутрішній когезії фрази, що також вимірюється за допомогою ПВІ. Потім цей показник досліджено емпірично, шляхом аналізу сполучень прикметник-іменник.
Переклад М. Дубка
Bos J. Expressive Power of Abstract Meaning Representations [Експресивна сила представлень абстрактних значень] / Johan Bos // Computational linguistics. – 2016. – Vol. 42. – No. 3. – Pages 527–535. – Режим доступу до анотації: https://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00257 – Режим доступу до повнотекстової статті: https://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00257
Синтаксис представлень абстрактних значень (ПАЗ) можна визначити рекурсивно, і можна визначити систематичний переклад на логіку першого порядку (ЛПП), зокрема правильне опрацювання заперечення. ПАЗ без повторюваних змінних знаходяться у розв’язному фрагменті ЛПП з двома змінними. Поточне визначення ПАЗ має обмежену експресивну силу для універсального кількісного визначення (до одного універсального квантифікатора на речення). Просте розширення синтаксису ПАЗ і переклад на логіку першого порядку уможливлює представлення проективності та області дії.
Синтаксис представлень абстрактних значень (ПАЗ) можна визначити рекурсивно, і можна визначити систематичний переклад на логіку першого порядку (ЛПП), зокрема правильне опрацювання заперечення. ПАЗ без повторюваних змінних знаходяться у розв’язному фрагменті ЛПП з двома змінними. Поточне визначення ПАЗ має обмежену експресивну силу для універсального кількісного визначення (до одного універсального квантифікатора на речення). Просте розширення синтаксису ПАЗ і переклад на логіку першого порядку уможливлює представлення проективності та області дії.
Переклад А. Шульги
Ionescu, R. T. String Kernels for Native Language Identification: Insights from Behind the Curtains [Рядкові ядра для визначення мови автора: із досвіду розробки й використання] / Radu Tudor Ionescu, Marius Popescu, Aoife Cahill // Computational linguistics. – 2016. – Vol. 42. – No. 3. – Pages 491–525. – Режим доступу до анотації: https://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00256 – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00256
Найбільш поширеним підходом до задач класифікації в інтелектуальному аналізі текстових даних є використання таких категорій, як слова, частиномовні мітки, основи або інші лінгвістичні категорії вищого рівня. Нещодавно для завдання визначення рідної мови автора (ВРМ) було запропоновано підхід, який використовує в якості категорій виключно символьні p-грами. Шляхом об'єднання декількох стрічкових ядер за допомогою багатоядерних обчислень цей підхід дозволив отримати результати на рівні останніх досягнень галузі. Незважаючи на продуктивність підходу на основі стрічкових ядер, є кілька питань про цей метод, які чекають відповіді. По-перше, не зрозуміло, чому такий простий підхід може конкурувати з набагато складнішими підходами, які враховують слова, леми, синтаксичну інформацію чи навіть семантику. По-друге, хоча підхід створювався як незалежний від мови, всі експерименти досі проводились на англійській мові. Ця праця є детальним дослідженням, яке повинне дати системне уявлення про підхід на основі стрічкових ядер та відповісти на вищезгадані відкриті питання.
Щоб порівняти підхід на основі стрічкових ядер з іншими сучасними методами, проведено велику кількість експериментів із визначення рідної мови автора. Емпіричні результати, отримані в усіх експериментах, проведених у цьому дослідженні, вказують на те, що запропонований підхід відповідає останнім досягненням у ВРМ, досягаючи точності, що на 1,7% перевершує найкращі результати у змаганні систем ВРМ 2013 року. Крім того, результати, отримані на базі як арабського, так і норвезького корпусів, свідчать, що запропонований підхід є незалежним від мови. При визначенні носіїв арабської мови стрічкові ядра показали точність, що перевершує найкращі відомі на сьогодні показники на 17%. Результати стрічкових ядер при визначенні носіїв норвезької мови також значно перевершують найсучасніший підхід. Крім того, в експерименті з кількома корпусами запропонований підхід перевершив результати найсучаснішої системи на 32,3%, продемонструвавши, що він може також бути незалежним від тематики.
Щоб отримати додаткові уявлення про підхід на основі стрічкових ядер, в цій статті аналізуються категорії, виділені класифікатором як більш розрізнювальні. Аналіз також містить інформацію про наслідки переносу локалізованої мови, оскільки критерії, які використовуються запропонованою моделлю, є p-грамами різної довжини. Виділені моделлю категорії, як правило, включають основи, службові слова, а також префікси та суфікси, які можуть бути узагальнені на відміну від суто словесних ознак. Завдяки аналізу розрізнювальних ознак, стаття дає уявлення про два види ефекту мовного перенесення, а саме вибір слів (лексичне перенесення) та морфологічні розбіжності. Мета цього дослідження полягає в тому, щоб дати повне уявлення про підхід на основі стрічкових ядер, а також пояснити, чому цей підхід працює так добре.
Найбільш поширеним підходом до задач класифікації в інтелектуальному аналізі текстових даних є використання таких категорій, як слова, частиномовні мітки, основи або інші лінгвістичні категорії вищого рівня. Нещодавно для завдання визначення рідної мови автора (ВРМ) було запропоновано підхід, який використовує в якості категорій виключно символьні p-грами. Шляхом об'єднання декількох стрічкових ядер за допомогою багатоядерних обчислень цей підхід дозволив отримати результати на рівні останніх досягнень галузі. Незважаючи на продуктивність підходу на основі стрічкових ядер, є кілька питань про цей метод, які чекають відповіді. По-перше, не зрозуміло, чому такий простий підхід може конкурувати з набагато складнішими підходами, які враховують слова, леми, синтаксичну інформацію чи навіть семантику. По-друге, хоча підхід створювався як незалежний від мови, всі експерименти досі проводились на англійській мові. Ця праця є детальним дослідженням, яке повинне дати системне уявлення про підхід на основі стрічкових ядер та відповісти на вищезгадані відкриті питання.
Щоб порівняти підхід на основі стрічкових ядер з іншими сучасними методами, проведено велику кількість експериментів із визначення рідної мови автора. Емпіричні результати, отримані в усіх експериментах, проведених у цьому дослідженні, вказують на те, що запропонований підхід відповідає останнім досягненням у ВРМ, досягаючи точності, що на 1,7% перевершує найкращі результати у змаганні систем ВРМ 2013 року. Крім того, результати, отримані на базі як арабського, так і норвезького корпусів, свідчать, що запропонований підхід є незалежним від мови. При визначенні носіїв арабської мови стрічкові ядра показали точність, що перевершує найкращі відомі на сьогодні показники на 17%. Результати стрічкових ядер при визначенні носіїв норвезької мови також значно перевершують найсучасніший підхід. Крім того, в експерименті з кількома корпусами запропонований підхід перевершив результати найсучаснішої системи на 32,3%, продемонструвавши, що він може також бути незалежним від тематики.
Щоб отримати додаткові уявлення про підхід на основі стрічкових ядер, в цій статті аналізуються категорії, виділені класифікатором як більш розрізнювальні. Аналіз також містить інформацію про наслідки переносу локалізованої мови, оскільки критерії, які використовуються запропонованою моделлю, є p-грамами різної довжини. Виділені моделлю категорії, як правило, включають основи, службові слова, а також префікси та суфікси, які можуть бути узагальнені на відміну від суто словесних ознак. Завдяки аналізу розрізнювальних ознак, стаття дає уявлення про два види ефекту мовного перенесення, а саме вибір слів (лексичне перенесення) та морфологічні розбіжності. Мета цього дослідження полягає в тому, щоб дати повне уявлення про підхід на основі стрічкових ядер, а також пояснити, чому цей підхід працює так добре.
Переклад М. Дубка
Cohen S. Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication [Синтаксичний аналіз лінійних контекстно-незалежних систем переписування за допомогою швидкого множення матриць] / Shay B. Cohen, Daniel Gildea // Computational linguistics. – 2016. – Vol. 42. – No. 3. – Pages 421–455. – Режим доступу до анотації: https://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00254 – Режим доступу до повнотекстової статті: https://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00254
У статті описано алгоритм розпізнавання підмножини бінарних лінійних контекстно-незалежних систем переписування (ЛКНСП) з часом виконання О (nωd), де M (m) = O (mω) - це тривалість перемноження матриць m × m, а d –“контактний ранг” ЛКНСП, тобто максимальна кількість комбінаторних та некомбінаторних точок, які з’являються у правилах граматики. Показано також, що цей алгоритм можна також використовувати як підпрограму для отримання алгоритму розпізнавання загальної бінарної ЛКНСП з тривалістю виконання O (nωd + 1). Нині найбільш відомий ω є меншим, ніж 2,38. Отриманий результат є ще одним підтвердженням найбільш відомого результату автоматичного синтаксичного аналізу слабко контекстно-залежних формалізмів, таких як комбінаторні категоріальні граматики, вершинні граматики, лінійні індексовані граматики та граматики об’єднання дерев, аналіз яких триває O (n4.76). Він також свідчить, трансдукційні інвертовані граматики можна проаналізувати за O(n5.76). Крім того, бінарна ЛКНСП включає в себе багато інших формалізмів і типів граматик, для деяких з яких також вдосконалено асимптотичну складність автоматичного синтаксичного аналізу.
У статті описано алгоритм розпізнавання підмножини бінарних лінійних контекстно-незалежних систем переписування (ЛКНСП) з часом виконання О (nωd), де M (m) = O (mω) - це тривалість перемноження матриць m × m, а d –“контактний ранг” ЛКНСП, тобто максимальна кількість комбінаторних та некомбінаторних точок, які з’являються у правилах граматики. Показано також, що цей алгоритм можна також використовувати як підпрограму для отримання алгоритму розпізнавання загальної бінарної ЛКНСП з тривалістю виконання O (nωd + 1). Нині найбільш відомий ω є меншим, ніж 2,38. Отриманий результат є ще одним підтвердженням найбільш відомого результату автоматичного синтаксичного аналізу слабко контекстно-залежних формалізмів, таких як комбінаторні категоріальні граматики, вершинні граматики, лінійні індексовані граматики та граматики об’єднання дерев, аналіз яких триває O (n4.76). Він також свідчить, трансдукційні інвертовані граматики можна проаналізувати за O(n5.76). Крім того, бінарна ЛКНСП включає в себе багато інших формалізмів і типів граматик, для деяких з яких також вдосконалено асимптотичну складність автоматичного синтаксичного аналізу.
Переклад А. Шульги
Kuhlmann M. Towards a Catalogue of Linguistic Graph Banks [На шляху до каталогу банків лінгвістичних графів] / Marco Kuhlmann, Stephan Oepen // Computational linguistics. – 2016. – Vol. 42. – No. 4. – Pages 819–827. – Режим доступу до анотації: https://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00268 – Режим доступу до повнотекстової статті: https://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00268
Графи, які перевищують формальну складність кореневого дерева, стають все більш актуальними для багатьох прикладних лінгвістичних досліджень. Хоча ця проблема формально добре досліджена в теорії графів, існує значна варіативність у типах лінгвістичних графів та інтерпретаціях різних структурних властивостей. Для забезпечення стандартної термінології та прозорих статистичних даних у різних наборах графів у опрацюванні природної мови, запропоновано створити загальнодоступний ресурс спільноти з відкритою еталонною реалізацією для отримання загальних даних.
Графи, які перевищують формальну складність кореневого дерева, стають все більш актуальними для багатьох прикладних лінгвістичних досліджень. Хоча ця проблема формально добре досліджена в теорії графів, існує значна варіативність у типах лінгвістичних графів та інтерпретаціях різних структурних властивостей. Для забезпечення стандартної термінології та прозорих статистичних даних у різних наборах графів у опрацюванні природної мови, запропоновано створити загальнодоступний ресурс спільноти з відкритою еталонною реалізацією для отримання загальних даних.
Переклад А. Шульги
Sajjad H. Statistical Models for Unsupervised, Semi-Supervised, and Supervised Transliteration Mining [Статистичні моделі для видобування пар із транслітерованими словами без залучення, з частковим і з повним залученням учителя] / Hassan Sajjad, Helmut Schmid, Alexander Fraser, Hinrich Schütze // Computational linguistics. – 2017. – Vol. 43. – No. 2. – Pages 349–375. – Режим доступу до анотації: https://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00286 – Режим доступу до повнотекстової статті: https://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00286
У статті представлено генеративну модель, яка ефективно та послідовно видобуває пари з транслітерованими словами за трьох різних умов: без залучення, з частковим і з повним залученням учителя. Ця модель інтерполює дві підмоделі: одну для генерування пар із транслітерованими словами, а другу для генерування пар без транслітерованих слів (тобто шуму). Модель навчається на зашумлених немаркованих даних за допомогою ЕМ-алгоритму. Під час навчання підмодель транслітерації вчиться генерувати пари з транслітерованими словами, а фіксована модель пар без транслітерованих слів генерує зашумлені пари. Після навчання знімається омонімія немаркованих даних на основі апостеріорної ймовірності двох підмоделей. Систему для видобування пар із транслітерованими словами оцінено на даних із змагань систем видобування пар із транслітерованими словами та паралельних корпусів. Для трьох з чотирьох мовних пар описана система перевершила всі системи з частковим та повним залученням учителя, які приймали участь у змаганнях NEWS 2010. При використанні пар слів, видобутих із паралельних корпусів з менш ніж 2% пар із транслітерованими словами, запропонована система досягає F-показника 86,7% з точністю 77,9% і повнотою 97,8%.
У статті представлено генеративну модель, яка ефективно та послідовно видобуває пари з транслітерованими словами за трьох різних умов: без залучення, з частковим і з повним залученням учителя. Ця модель інтерполює дві підмоделі: одну для генерування пар із транслітерованими словами, а другу для генерування пар без транслітерованих слів (тобто шуму). Модель навчається на зашумлених немаркованих даних за допомогою ЕМ-алгоритму. Під час навчання підмодель транслітерації вчиться генерувати пари з транслітерованими словами, а фіксована модель пар без транслітерованих слів генерує зашумлені пари. Після навчання знімається омонімія немаркованих даних на основі апостеріорної ймовірності двох підмоделей. Систему для видобування пар із транслітерованими словами оцінено на даних із змагань систем видобування пар із транслітерованими словами та паралельних корпусів. Для трьох з чотирьох мовних пар описана система перевершила всі системи з частковим та повним залученням учителя, які приймали участь у змаганнях NEWS 2010. При використанні пар слів, видобутих із паралельних корпусів з менш ніж 2% пар із транслітерованими словами, запропонована система досягає F-показника 86,7% з точністю 77,9% і повнотою 97,8%.
Переклад А. Шульги
Nguyen, D. A Kernel Independence Test for Geographical Language Variation [Тест незалежності ядра для географічного варіювання мов] / Dong Nguyen, Jacob Eisenstein. – 2017. – Vol. 43. – No. 3. – Pages 567–592. – Режим доступу до анотації: https://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00293 – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00293
Кількісна оцінка ступеня просторової залежності лінгвістичних змінних є ключовим завданням для аналізу діалектного різноманіття. Проте існуючі підходи мають суттєві недоліки. По-перше, вони базуються на параметричних моделях залежності, що обмежує їхню ефективність у випадках, коли порушуються основні параметричні припущення. По-друге, їх не можна застосувати до всіх видів лінгвістичних даних. Одні підходи застосовуються лише до частот, інші – до булевих вказівників наявності мовної змінної. У статті представлено новий метод вимірювання географічного варіювання мови, який вирішує обидві ці проблеми. Запропонований підхід ґрунтується на представленнях Відтворюваного Ядра Гілбертового Простору (ВЯГП) для непараметричних статистичних даних і має форму тестової статистики, яка обчислюється з пар окремих геотегованих спостережень без агрегації до заданих географічних контейнерів. Здійснено порівняння цього тесту з попередньою роботою із використанням синтетичних даних, а також неоднорідного набору автентичних сукупностей даних: корпусу нідерландських твітів, голландського синтаксичного атласу та набору листів, адресованих редакторам північноамериканських газет. Продемонстровано, що запропонований тест підтверджує стійкі висновки в широкому діапазоні сценаріїв та типів даних.
Кількісна оцінка ступеня просторової залежності лінгвістичних змінних є ключовим завданням для аналізу діалектного різноманіття. Проте існуючі підходи мають суттєві недоліки. По-перше, вони базуються на параметричних моделях залежності, що обмежує їхню ефективність у випадках, коли порушуються основні параметричні припущення. По-друге, їх не можна застосувати до всіх видів лінгвістичних даних. Одні підходи застосовуються лише до частот, інші – до булевих вказівників наявності мовної змінної. У статті представлено новий метод вимірювання географічного варіювання мови, який вирішує обидві ці проблеми. Запропонований підхід ґрунтується на представленнях Відтворюваного Ядра Гілбертового Простору (ВЯГП) для непараметричних статистичних даних і має форму тестової статистики, яка обчислюється з пар окремих геотегованих спостережень без агрегації до заданих географічних контейнерів. Здійснено порівняння цього тесту з попередньою роботою із використанням синтетичних даних, а також неоднорідного набору автентичних сукупностей даних: корпусу нідерландських твітів, голландського синтаксичного атласу та набору листів, адресованих редакторам північноамериканських газет. Продемонстровано, що запропонований тест підтверджує стійкі висновки в широкому діапазоні сценаріїв та типів даних.
Переклад М. Дубка
Constant, M. Multiword Expression Processing: A Survey [Опрацювання багатослівних виразів: огляд] / Mathieu Constant, Gülşen Eryiğit, Johanna Monti, Lonneke van der Plas, Carlos Ramisch, Michael Rosner, Amalia Todirascu // Computational linguistics. – 2017. – Vol. 43. – No. 4. – Pages 837–892. – Режим доступу до анотації: http://www.mitpressjournals.org/doi/abs/10.1162/COLI_a_00302 – Режим доступу до повнотекстової статті: http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00302
Багатослівні вирази (БВ) – це клас мовних форм, які збігаються із звичайними словами, і які є як унікальними, так і поширеними в різних мовах. Для врахування БВ потрібно переосмислити структуру опрацювання природної мови, яка залежить від чіткого розмежування слів і фраз. Питання опрацювання БВ має вирішальне значення для програм опрацювання природної мови, де воно викликає низку проблем. Цей огляд, обумовлений появою рішень за відсутності керівних принципів, має на меті не лише цілеспрямований аналіз опрацювання БВ, а й уточнення характеру взаємодії між опрацюванням БВ та цільовими програмами. Запропоновано концептуальну основу, в рамках якої можна розглядати складні проблеми та результати досліджень. Вона забезпечує спільне розуміння того, що мається на увазі під «опрацюванням БВ», відокремлюючи підзадачі знаходження та ідентифікації БВ. Вона також висвітлює взаємодію між опрацюванням БВ і двома варіантами використання: автоматичним синтаксичним аналізом і машинним перекладом. Багато підходів у літературі можна диференціювати залежно від того, як вимірюється час опрацювання БВ відносно варіантів використання. Проаналізовано, яким чином такі механізми управління впливають на можливості систем, які опрацьовують БВ. Для кожної з двох підзадач опрацювання БВ і для кожного з двох варіантів використання зроблено висновок про невирішені питання та перспективи дослідження.
Багатослівні вирази (БВ) – це клас мовних форм, які збігаються із звичайними словами, і які є як унікальними, так і поширеними в різних мовах. Для врахування БВ потрібно переосмислити структуру опрацювання природної мови, яка залежить від чіткого розмежування слів і фраз. Питання опрацювання БВ має вирішальне значення для програм опрацювання природної мови, де воно викликає низку проблем. Цей огляд, обумовлений появою рішень за відсутності керівних принципів, має на меті не лише цілеспрямований аналіз опрацювання БВ, а й уточнення характеру взаємодії між опрацюванням БВ та цільовими програмами. Запропоновано концептуальну основу, в рамках якої можна розглядати складні проблеми та результати досліджень. Вона забезпечує спільне розуміння того, що мається на увазі під «опрацюванням БВ», відокремлюючи підзадачі знаходження та ідентифікації БВ. Вона також висвітлює взаємодію між опрацюванням БВ і двома варіантами використання: автоматичним синтаксичним аналізом і машинним перекладом. Багато підходів у літературі можна диференціювати залежно від того, як вимірюється час опрацювання БВ відносно варіантів використання. Проаналізовано, яким чином такі механізми управління впливають на можливості систем, які опрацьовують БВ. Для кожної з двох підзадач опрацювання БВ і для кожного з двох варіантів використання зроблено висновок про невирішені питання та перспективи дослідження.
Переклад М. Дубка