2
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ .............................................................................................................. 3
ГЛАВА 1. ИСТОРИЯ РАЗВИТИЯ МАШИННОГО ОБУЧЕНИЯ ..................... 6
1.1. Машинное обучение в 1930-1960е годы………………………………..6
1.2. Машинное обучение в 1960-1990е годы. ............................................... 12
1.3. Машинное обучение в настоящее время. .............................................. 21
ГЛАВА 2. ПРИКЛАДНОЕ МАШИННОЕ ОБУЧЕНИЕ ................................... 30
2.1. Анализ текста, виды анализа текста. ...................................................... 30
2.2. Синтаксический анализ. .......................................................................... 34
2.2.1. Методы построения синтаксических деревьев составляющих. ... 38
2.2.2. Методы построения синтаксических деревьев зависимостей. .... 43
2.2.3. Графовый подход к построению синтаксических деревьев
зависимостей. ......................................................................................................... 45
2.2.4. Метод синтаксического анализа на основе системы переходов. . 47
2.2.5. Системы синтаксического анализа текстов на русском языке. ... 49
ГЛАВА 3. ИСПОЛЬЗОВАНИЕ ИНСТРУМЕНТОВ СИНТАКСИЧЕСКОГО
АНАЛИЗА, ИХ ХАРАКТЕРИСТИКА ................................................................ 51
3.1. Использование Maltparser для синтаксического анализа. ................... 51
3.2. Использование AOT для синтаксического анализа. ............................. 56
3.3. Использование ABBYY Compreno для синтаксического анализа. ..... 61
ЗАКЛЮЧЕНИЕ……………………………………………………………….…65
СПИСОК ИСПОЛЬЗОВАННО ЛИТЕРАТУРЫ ............................................. 65
3
ВВЕДЕНИЕ
Компьютерный лингвистический анализ текстов на естественном языке
– одна из самых перспективных областей искусственного интеллекта. Одна из
ключевых задач такого анализа заключается в построении
структурированного представления текста, к которому можно применять
способы и алгоритмы решения прикладных задач. Многие исследователи
отмечают, что качественное решение таких задач, как вопросно-ответный
поиск, извлечение информации и знаний из текстов, автоматическое
реферирование, невозможно без проведения синтаксического и
семантического анализа. Есть множество разновидностей методов
синтаксического и семантического анализа, которые основаны на разных
моделях синтаксической структуры предложения и различном понимании
семантики.
В данной дипломной работе исследуются в частности методы
построения синтаксических деревьев зависимостей как основной способ
синтаксического анализа. Деревья зависимостей моделируют синтаксическую
структуру предложений в виде иерархии слов, связанных дугами,
обозначающими синтаксическое подчинение между главным и зависимым
словами. Подчинение объясняется набором общих принципов, основная
мысль которых состоит в том, что зависимое слово в предложении является
необязательным, не таким важным для передачи смысла высказывания, как
главное.
Задачи синтаксического и семантического анализа, как правило,
решаются раздельно: сначала строится синтаксическая структура
предложения, на основе которой затем строится семантическая структура. Для
этого существует ряд методов, основанных как на правилах, так и на
машинном обучении. Хотя современные технологии позволяют добиваться
достаточно высокого качества решения подобных задач, остается
значительное пространство для улучшения этих методов. Семантический
4
анализ текста не представляется возможным без синтаксического,
выявляющего основную структуру единицы(предложения), отмечающего
зависимости между частями предложения. Однако, согласно последним
тенденциям, семантический анализ будет хорошо дополнять синтаксический,
снижая количество ошибок и погрешностей.
Несмотря на то, что на данный момент существует достаточное
количество научных работ по машинному обучению и компьютерной
лингвистике, ни одна не носит обзорный характер с элементами исторического
экскурса и детализации именно синтаксического анализа. В следствие чего,
данная работа является актуальной.
Практическая значимость работы заключается в том, что на основе
исследования и сравнения синтаксических анализаторов можно сделать
обоснованный выбор для использования определенного анализатора в ПО для
обработки естественного языка или использовать данные как базу для
создания собственных инструментов парсинга.
Объект исследования – машинное обучение в рамках анализа
естественного языка. Предмет – методы и алгоритмы синтаксического
анализа.
Целью выпускной квалификационной работы является исследование
ретроспективы машинного обучения и его методов для анализа текстов на
естественном языке в задачах синтаксического анализа, в том числе на
примере современных анализаторов MaltParser, AOT, ABBYY Compreno.
Задачи дипломной работы:
1. Изучить историю развития искусственного интеллекта и
машинного обучения в том числе в задачах, связанных с анализом
естественного языка.
2. Рассмотреть состояние и тенденции развития машинного
обучения в настоящее время.
5
3. Описать существующие способы автоматического анализа
естественного языка
4. Изучить и дать краткую характеристику методам синтаксического
анализа естественного языка в рамках машинного обучения.
5. Исследовать синтаксические анализаторы MaltParser, AOT,
ABBYY Compreno, определить их основные характеристики.
Для решения поставленных задач применены следующие методы
исследования:
1. Исторический метод
2. Методы машинного обучения.
3. Методы компьютерной лингвистики.
4. Методы оценки качества алгоритмов машинного обучения.
5. Методы исследования качества синтаксического анализа.
6. Методы объектно-ориентированного проектирования программного
обеспечения.
При написании выпускной квалификационной работы использовались
научные труды следующих авторов: Н. Хомского [10], . Нивре [20], Е. А.
Сулеймановой [24], И. М. Ножова [62] и другие.
Выпускная квалификационная работа состоит из Введения, трех глав,
Заключения, Списка использованной литературы.
В первой главе выпускной квалификационной работы рассматривается
история развития искусственного интеллекта и машинного обучения в том
числе в задачах, связанных с анализом естественного языка.
Во второй главе работы дается описание существующих способов
автоматического анализа естественного языка, изучается синтаксический
анализ и его методы, дается их краткая характеристика.
В третьей главе работы исследуются анализаторы MaltParser, AOT,
ABBY Compreno, дается их характеристика, приводятся примеры.
6
ГЛАВА 1. ИСТОРИЯ РАЗВИТИЯ МАШИННОГО
ОБУЧЕНИЯ
1.1. Машинное обучение в 1930-1960е годы.
Машинное обучение - относительно новое направление развития науки,
однако за время своего существования они успело внушительно развиться.
Одной из отправных точек можно считать создание синтезатора речи в
1936 году инженером Bell Labs, Хоумером Дадли на основе патента 1930 года,
вокодера. По дизайну он не использовал голос в качестве образца, а работал
от специализированного контроллера, состоящего из клавиатуры, на которой
выбирались частотные полосы, педали управляющей высотой тона и
специальной дощечки под запястье, которая переключала тип фильтруемого
сигнала с тона на шум. После года обучения, оператор мог играть на этом
инструменте так, чтобы он синтезировал речь и даже пел песни.
Первой признанной работой в области искусственного интеллекта
считается труд Уоррена МакКалоха и Уолтера Питтса (1943). Авторы
основывались на трёх компонентах: знание общей физиологии и работы
нейронов в мозге; формальный анализ пропозициональной логики по Расселу
и Уайтхеду и теории алгоритмов Тьюринга.
Они описали модель искусственных нейронов, в которой каждый нейрон
имеет состояние “включен” или “выключен”, которое может переключаться в
зависимости от реакции на стимулирование от определенного количества
соседних нейронов. Состояние нейрона рассматривалось как "фактически
эквивалентное высказыванию, в котором предлагается адекватное количество
стимулов". Работы этих ученых показали, например, что любая вычислимая
функция может быть вычислена с помощью некоторой сети из соединенных
нейронов и что все логические связки ("И", "ИЛИ", "НЕ" и т.д.) могут быть
реализованы с помощью простых сетевых структур. Кроме того, МакКаллоx и
Питтс выдвинули предположение, что сети, структурированные
7
соответствующим образом, способны к обучению. Дональд Хебб
продемонстрировал простое правило обновления для модификации
количества соединений между нейронами. Предложенное им правило,
называемое теперь правилом хеббовского обучения, продолжает служить
основой для моделей, широко используемых и в наши дни.
Два аспиранта факультета математики Принстонского университета,
Марвин Мински и Дин Эдмондс, в 1951 году собрали первый компьютер на
основе нейронной сети. В этом компьютере, получившем название SNARC,
использовалось 3000 электронных ламп и дополнительный механизм
автопилота с бомбардировщика В-24 для моделирования сети из 40 нейронов.
Аттестационная комиссия, перед которой Мински защищал диссертацию,
выразила сомнение в том, может ли работа такого рода рассматриваться как
математическая, на что фон Нейман, по словам современников, возразил:
"Сегодня — нет, но когда-то будет". В дальнейшем Мински доказал очень
важные теоремы, показывающие, с какими ограничениями должны
столкнуться исследования в области нейронных сетей.
В 1956 году Джон МакКарти убедил Минского, Шеннона и Рочестера
помочь ему в организации конференции, в которой могли бы принять участие
ученые, интересующихся вопросами моделирования человеческого разума.
Мероприятие утвердило появление новой области науки и дала ей название —
«Artificial Intelligence» — «Искусственный интеллект» (термин был
предложен Джоном Маккарти).
Согласно Маккарти, под интеллектом понимается «вычислительная
составляющая способности достигать цели, причем исследователи вольны
использовать методы, которые не наблюдаются у людей, если это необходимо
для решения конкретных проблем, как в конструировании машины, так и в
работе алгоритмов».
Дартмутская конференция стала катализатором для научных изысканий
в этой области. То, что раньше было работой единичных энтузиастов вдруг
8
стало объектом работы целого профессионального сообщества со своими
научными целями и четким самоопределением. Через год после Дартмутского
семинара подобные лаборатории по изучению искусственного интеллекта
были основаны в целом ряде университетов: Карнеги - Меллон под
руководством Аллена Ньюэлла и Герберта Саймона, в Стэнфорде под
руководством Маккарти, в МИТ под руководством Марвина Минского и в
Эдинбурге под руководством Дональда Миши.
С 1952 г. Артур Сэмюэл, пионер в области компьютерных игр и
машинного обучения, создает ряд программ для игры в шашки. Важнейшим
результатом его работы является программа «Checkers-playing» – одна из
первых, в которой реализованы функции самообучения и наглядно
демонстрируются базовые принципы ИИ. В ходе своих исследований Сэмюэл
опроверг утверждение, что компьютеры способны выполнять только то, чему
их учили: одна из его программ «научилась» играть в шашки лучше, чем ее
создатель. Разработки А. Сэмюэла принято считать основополагающими в
данном направлении.
Сэмюэль использовал идею таблиц сигнатур — иерархии таблиц: 38
характеристик группируются по типу (некоторые могут входить в разные
группы); к одному типу относятся те характеристики, которые считаются, по
мнению экспертов и самого Сэмюэля, взаимосвязанными. Каждая из них
ограничена тем, что может принимать не более семи различных значений. В
то же время коэффициент теперь приписывается всей комбинации значений
внутри одного типа.
Сэмюэль вновь ввел 180 000 экспертных ходов и рассчитал параметры с
использованием метода корреляции. Было установлено, что примерно после
80 000 ходов ситуация стабилизируется. В действительности все происходит
так, как если бы каждый матричный элемент был единственным элементом:
имеется 315 X 9 элементов для типа А, 125 X 3 для типа В и 343 для типа С, т.
е. около 3500 элементов вместо 16 в программе 1.
9
Так как большинство характеристик участвуют только в определенных
фазах игры, ход всей партии делится на шесть фаз в зависимости от числа
продвигающихся пешек и степени продвинутости. Такое деление
дополнительно уменьшает время расчетов.
Это время весьма незначительно, потому что оценивание представляет
просто поиск в таблице. Вычисление F(S) происходит по одной инструкции:
https://monosnap.com/file/anMNLtK5T9y3vpDIQ3lM2m6ERwVOz8
Эта программа стала и останется настоящим чемпионом мира игры в
шашки. Без использования процедуры альфа — бета она выбирает наилучший
ход в 68% случаев (против 32% с полиномиальным оцениванием и 16% со
случайным выбором), а с использованием процедуры альфа — бета
существенно улучшает ее показатели. Кроме того, рассмотренный подход
придает игре регулярность — исключает плохие ходы в течение всей партии.
В это же время американский исследователь Аллен Ньюэлл вместе с
Гербертом Саймоном занялся разработкой программы игры в шахматы. В
состав рабочей команды вошли аналитики корпорации RAND (компания,
занимающаяся разработкой новых методов решения стратегических проблем),
а также группа голландских психологов под руководством Де Гроота,
изучавших стили игры выдающихся шахматистов. Результатом двухлетней
работы стал язык программирования «IPL» – первый символьный язык
обработки списков. Через некоторое время на этом языке была написана
интеллектуальная программа «Логик-Теоретик», предназначенная для
автоматического доказательства теорем в исчислении высказываний. С ее
помощью было заново доказано 38 из 52 теорем одного из разделов
математической логики – исчисления высказываний. Впоследствии на ЭВМ с
большим быстродействием удалось вывести все 52 теоремы» [2, с. 141].
Однако, Аллен Ньюэлл и Герберт Саймон не остановились на этом, и за
предыдущим успехом последовал Универсальный Решатель Задач (General
Problem Solver, GPS).
10
Методология, использованная в GPS, отличается от стандартных методов
поиска в пространстве состояний тем, что она выбирает путь, по которому
продолжить поиск. Т.е. система пытается искать решение в первую очередь в
"наиболее перспективных" ветвях поиска. Такая методология была названа
"анализ средств и целей" (means-ends analysis). Ее суть заключалась в том, что
сначала отыскивалось различие (difference) между текущим объектом и
объектом, который мы хотим получить. Это различие относилось к одному из
ряда классов различий. С каждым классом был сопоставлен набор действий,
способных уменьшить различие между текущим и целевым объектами.
На каждом шаге поиска GPS искал различие объектов и выбирал один
из релевантных операторов, который и пытался затем применить к текущему
объекту. Поиск подходящей последовательности операторов выполнялся в
глубину до тех пор, пока операторы оказывались применимы, а ветвь поиска
"выглядела перспективной". Если ветвь поиска была бесперспективной, то
выполнялся откат. Важной особенностью анализа средств и целей является то,
что всегда выбирается "релевантный" оператор, уменьшающий различие
объектов, даже если он и не применим к текущему объекту. Вместо того чтобы
отказаться от неприменимого к текущему объекту оператора, GPS пытался
преобразовать текущий объект в объект, пригодный для применения
выбранного оператора. Применение такой стратегии привело к появлению
рекурсивной, целеориентированной процедуры, которая фиксирует историю
поиска в графе с частично-проработанными узлами.
Несмотря на то, что в качестве объекта могла выступать модель мира, а
в качестве оператора — действие, задача планирования перед системой GPS
не ставилась. Такой вариант использования GPS был осуществлен
значительно позднее, когда была разработана система STRIPS.
В 1954 г. была проведена демонстрация работы устройства,
представляющего отдельное направление в исследованиях ИИ, а именно
машинного перевода с одного естественного языка на другой с сохранением
11
семантических отношений при помощи специальной компьютерной
программы. Идея была предложена ещё в 1947 г. специалистом по
криптографии Уорреном Уивером, а 7 января 1954 г. корпорация IBM
совместно с Джорджтаунским университетом продемонстрировала IBM Mark
II, осуществившее полностью автоматический перевод более 60 предложений
с русского языка на английский. Событие было названо «джорджтаунским
экспериментом». Оно дало мощный старт в развитии данного направления,
вызвав широкий резонанс в научном сообществе и положительно повлияв на
разработку подобных систем в дальнейшем [1, с. 4].
В 1958 г. Джон Маккарти также внес существенный вклад в разработку
нового языка программирования высокого уровня «Lisp». Этот язык до сих
пор остается одним из главных инструментов при написании программной
части интеллектуальных систем. Следующим открытием Маккарти,
обусловленным нехваткой средств на увеличение мощности компьютерных
ресурсов, стал «режим разделения времени» (одновременный доступ
нескольких пользователей к одной ЭВМ). Этот режим позволил раскрыть
потенциал вычислительных машин и в разы увеличить производительность
работ.
В том же году Маккарти описал гипотетическую программу «Advice
Taker», основным назначением которой явилось использование знаний, в том
числе и общих представлений об окружающем мире, при решении
поставленных задач. Основывая свои действия на наборе аксиом, программа,
в зависимости от условий, способна расширять набор фундаментальных
установок, тем самым воплощая принципы представления знаний и
проведения рассуждений, не нуждаясь в перепрограммировании.
Advice Taker воплотил основные идеи о представлении знаний, а
именно, высокую полезность формального, расширенного представление о
мире и того, как на мир могут влиять некоторые действия агентов(=