В современное время большей популярностью пользуется статистический подход. В особенности это касается наработок для текстов не на русском языке [20].

Традиционная задача статистического обучения (statistical learning/ machine learning/ pattern recognition) в своем самом общем виде выглядит следующим образом. Есть несколько объектов, с какими - то наблюдаемыми свойствами и какими-то ненаблюдаемыми, но известными. Требуется построить алгоритм, правильно распознающий эти ненаблюдаемые свойства по наблюдаемым, причем не только для предварительно объявленным объектов, но и для ряда любых других. Или хотя бы построить такой алгоритм, который будет ошибаться не очень часто и не очень сильно. Однако, нужно не однократно построить такой алгоритм, а создать впоследствии алгоритм более высокого уровня (мета-алгоритм, метод …), который будет способен построить вычисляющий алгоритм по любому предъявленному набору объектов, чтобы в большинстве случаев этот алгоритм получался приемлемым. Описанную выше задачу будем называть распознаванием (recognition).

Приведем список неформальных примеров таких задач:

§ Распознавание рукописного текста. Имеется некоторое число отсканированных страниц рукописей и параллельных текстов, с правильно прочитанным содержанием рукописей. Требуется построить алгоритмы, читающие рукописный текст непосредственно с листа.

§ Распознавание речи. Имеется звуковой файл голоса, содержащий записи речи на естественном языке, и текстовый файл, расшифровывающий записи. Построить алгоритм, записывающий запись в виде текста.

§ Одним из интереснейших направлений является медицинская диагностика. Имеется некоторое количество историй болезни, к которым приложены результаты обследований больных. Требуется построить алгоритм, который по результатам обследования будет способен поставить ему диагноз, назначить лечение и / или спрогнозировать результаты назначенного исследования. Или, например, более реально, что построенный алгоритм способен будет подсказать врачу наиболее правдоподобные диагнозы.

Кроме распознавания статистическое обучение занимается и такими задачами, как например задачей кластеризации (cluster analysis). Данная задача может быть описана так. Есть некоторое количество объектов с рядом наблюдаемых слов. Требуется построить алгоритм, который будет способен разбить объекты на определенные группы, называемые кластерами (cluster). Также требуется построить алгоритм, определяющий, какому кластеру принадлежит тот или иной объект так, чтобы внутри одного кластера объекты были похожи друг на друга, а объекты разных кластеров - наоборот. Причем необходимо, чтобы полученные данные были верными не только для заранее предоставленных объектов, но и для любых других.

2. Теоретическая часть исследования

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

Общая характеристика имени собственного

По Лингвистическому энциклопедическому словарю Ярцевой имя собственное представляет собой слово, словосочетание или предложение, которое служит для выделения именуемого им объекта из ряда подобных, индивидуализируя и идентифицируя данный объект. К именам собственным относятся следующие объекты ономастики: антропонимы, топонимы, теонимы.ю зоонимы, астронимы, космонимы, фитонимы, хрононимы, идеонимы и др. [16]

Разграничение имён собственных было достигнуто ономастикой в 60-70х гг. 20 в. Ономастика противопоставляет ономастическую лексику апеллятивной, т.е. всему остальному лексическому составу языка, соответственно, противопоставляет оним - апеллятиву (любому слову лексического состава языка). В грамматиках имя собственное противопоставляется имени нарицательному, но только в классе существительных.

Имя собственное не связано с понятием, оно вторично по отношению к апеллятиву. Основное значение имени собственного заключено в его связи с денотатом. Также, имя собственное является значительным межъязыковым слоем лексики и, как правило, не требует перевода. Это ведет к появлению иноязычных имён собственных в любом языке. В состав имени собственного могут быть включены любые части речи, артикли. Так, имя собственное может частично или полностью совпадать по форме с апеллятивом, например «ведь» - фамилия «Ведь», «чёрная» - река Чёрная, «суглинок» - деревня Суглинки. Оно может также совпадать с чистой основой, словом, словосочетанием, предложением в связи с тем, что любая из этих форм субстантивируется благодаря основной функции имени собственного - называть индивидуальный объект.

Касательно частотности употребления грамматических и словообразовательных средств языка, у имен собственных и апеллятивов имеются значительные расхождения: то, что частотно у имени собственного может редко встречаться или отсутствовать совсем в апеллятивах в данной языковой среде и наоборот. Данный факт позволяет выявлять определенные словообразовательные модели для имен собственных, которые будут отличаться от словообразовательных моделей апеллятивов по флексиям и грамматическому роду, а также стоит подчеркнуть особое словоизменение. Таким образом можно говорить об ономастических системах и подсистемах и об особых ономастических закономерностях. Например, элементы лексики избирательно вовлекаются в формирование имен собственных, получают особые условия функционирования и зачастую из-за длительности существования «консервируются», особенно у антропонимов и теонимов, что способствует сохранению уникальных языковых единиц.

Собственные имена имеют 3 основных источника формирования: онимизация - переход апеллятива в имя собственное, трансонимизация - переход имени собственного из одного разряда в другой, заимствование иноязычных имен собственных. Также, имена собственные могут быть созданы и искусственно. Такие имена-окказионализмы далеки от сферы образования несобственных имен, например личные имена Эпик, Виоланта, Фрит и т.д. Само возникновение имени собственного диктуется общественной необходимостью различать однотипные объекты. Характер имени собственного определяется рядом факторов, таких как культура народа и религия (антропонимы и теонимы), история народа (все категории онимов), географическая среда (топонимы, астронимы и др), социальной средой и ее изменениями (изменение состава имен, мода на конкретные имена, появление новых имен и моделей). В каждую эпоху у каждого народа имеется свой ономастикон, который включает в себя имена разных сфер ономастического пространства.

Имя собственное является составной частью коммуникативной системы. Так, оно может быть подвержено апеллятивации (село Палех - изделие палех), фразеологизации (город Вавилон - Вавилонское столпотворение), терминологизации (Генри - генри как единица индуктивности). Говоря об ономастической системе, часто наблюдают иррадизацию (река Дон, город Донецк, Донбасс, Дмитрий Донской, роман «Тихий Дон» и др.), стилистическую переоценку, а также заимствованное имя собственное подвергают адаптации.

Ономастический аспект при рассмотрении именованных сущностей

Антропонимика - раздел ономастики, который изучает антропонимы. Под антропонимами понимаются собственные именования людей: личные имена, патронимы, фамилии, родовые имена, прозвища и псевдонимы, криптонимы (скрываемые имена). Каждый этнос в каждую эпоху имеет свой антропонимикон - реестр личных имён. [16]

Антропоним, в особенности личное имя, отличается от многих других омонимов характером индивидуализации объекта: каждый объект номинации (человек) имеет имя. Однако, реестр имен ограничен. Личные имена зачастую повторяются, и это заставляет давать дополнительные именования.

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

Теоретическая антропонимика изучает закономерности возникновения и развития антропонимов, их структуру, модели антропонимов, исторические пласты в антропонимии какого-либо этноса, взаимодействие в антропонимии, а также уневерсалии.

Прикладная антропонимика, в свою очередь, изучает проблемы нормы в именах, способы передачи одного имени в разных языках. Данный раздел способствует созданию антропонимических словарей.

Топонимика - раздел ономастики, который исследует географические названия, их функционирование, значение и происхождение, структуру, ареал распространения, изменение и развитие во времени. Совокупность топонимов на определенной территории составляет её топонимию. [16]

Выделяют следующие основные виды топонимии: ойконимия - наименования населенных пунктов (город Омск, село Бородино), гидронимия - наименования водных объектов (озеро Байкал, река Волга), оронимия - наименования особенностей рельефа (Уральские горы, Альпы), космонимия - наименования внеземных объектов (планета Меркурий и тп).

Важным источником формирования исторически сложившейся топонимии служат местные географические термины («лука» - «Великие Луки»). Наиболее древний слой представляют гидронимы, в первую очередь названия крупных рек. Гидронимы представляют собой важный источник формирования древних топонимов (река Вологда - город Вологда, река Москва - город Москва).

По составу топонимы могут быть однословными (Плёс, Днепр), словосочетаниями (Чистые пруды), топонимическими фразеологизмами («Воздвиженское, что в Игрищах»). Топонимы подразделяются на простые и сложны в соответствии с грамматической структурой. Если сравнивать топонимы с апеллятивной лексикой, важно отметить, что они имеют ряд особенностей в системе морфологии и словообразования. Структурное членение топонима предполагает выделение базовой лексической морфемы - топоосновы, к которой присоединяется топоформант, квазнаффикс, который может быть реализован в чистом аффиксе и застывшей лексической морфеме («Бор-овск», «Бел-город»). Однако топоним может выступать и с нулевым аффиксом («Дон», «Бор»). В восточнославянской топонимии продуктивными способами в образовании топонимов являются префиксальный и префиксально-суффиксальные образования («Переволока», «Запорожье»).

Эргонимика - раздел ономастики, который изучает наименования деловых объединений людей.

По словарю русской ономастической терминологии Н.В. Подольской (1978), эргоним - разряд онимов, собственное имя делового объединения людей (союз, организация, учреждение, предприятие, заведение). Эргонимы, в отличии от других видов онимов, отличаются вторичностью номинации. Также, они отличаются структурно-семантическим разнообразием: так, в качестве наименований может быть использована любая языковая единица (от отдельного знака до целого предложения). Эргонимам присуще слабая структурированности, изменчивость и недолговечность. Слова любой части речи (прилагательное, глагол, наречие, местоимение) могут стать эргонимами, т.к. в результате субстантивации они становятся именами существительными.[13]

Признаки выделения именованных сущностей

На первом этапе реализации задачи извлечения именованной сущности происходит поиск сущности. Выделяют следующие критерии:

* Наличие заглавной буквы

* Обязательное наличие референта:

На прилавки поступила книга братьев Стругацких («Стругацкие» имеют референт, следовательно, являются именованной сущностью)

В честь великой императрицы девочек часто называли Катями. («Катями» не будет являться именованной сущностью, так как не имеет референта)

Вторым этапом признано считать определение границ именованной сущности. К именованной сущности следует относить самую длинную цепочку последовательных слов, отражающих имя.

* Включение/ не включение дескриптора в состав именованной сущности. Под дескриптором будет пониматься слово или словосочетание, которое указывает на родовое понятие именованной сущности. Например, река Нева - «река». Таким образом, дескриптор будет являться частью ИС, если:

* Является аббревиатурой (ОАО «Сокол»);

* Если является вершиной именной группы, но при этом само имя не является приложением (Санкт-Петербургский государственный университет)

А не будет являться частью ИС, в таких случаях: город Москва, военно-патриотическая организация «Родина».

Важной частью также является наличие знаков препинания. Они включаются в ИС, если сами являются частью имени, а не используются в качестве разделителя. Кавычки входят в дескриптор, только когда дескриптор включен в ИС. (фильм «Москва слезам не верит», ОАО «Сокол»).

Однако, ИС является следующее: Владимир Путин (@vputin); Одинцово, Московская область.

Если именованная сущность или дескриптор являются однородными членами, то ИС выделяется отдельно, а дескриптор вообще никак не выделяется:

* Аркадий и Борис Стругацкие;

* станции метро «Белорусская» и «Курская»

На третьем этапе происходит разметка именованных сущностей, обусловленные задачей. Рассмотрим Персону, Местоположение и Организацию.

Персона - обозначает живые существа. Могут быть выделены следующие категории:

* различные вариации Ф.И.О.;

* клички животных;

* имена богов;

* username, прозвища, псевдонимы и др.

Стоит отметить тот факт, что прилагательные, которые не являются частью прозвища или имени, не включаются в ИС: Солнцеподобный Ким Чен Ын.

В конструкциях типа им.Пушкина или имени Пушкина, и даже если имя опущено, мы не различаем персон в составе типа локаций и организаций. Однако, имена будут выделяться, если они являются типовыми обозначениями сущностей: детский сад Монтессори.

Местоположение - обозначают объекты, указывающие на положение в пространстве. Могут быть представлены следующими категориями:

* природные объекты;

* территориальные объекты;

* всевозможные конструкции;

* вымышленные места и др.

Организация - определяет объекты в том случае, если сущность может быть местом работы или в ней можно состоять в качестве члена, и цепочка, в которую входит слово, включает также слова отличные от указания на родовое понятие.

Имя организации может быть выражено вариативно:

* личным именем - компания Sony;

* с дескриптором, как частью имени:

* заимствованное имя - библиотека им. Ленина;

* название по месту - парламент Англии;

* имеющий номер: Школа №87 и др.

Если названия вложены, то размечается длинная цепочка: Отдел экономической безопасности и противодействия коррупции.

Важно также отметить, что даже если название организации встречается в значении местоположения, то она всё равно размечается как организация:

Мы отправили свою заявки в Комитет по борьбе с коррупцией.

На этом данные правила не заканчиваются. Они могут пополняться при исследовании новых текстовых структур.

Парадигматические и синтагматические отношения

Согласно теории Ф. де Соссюра, система языка строится на двух главных типах отношений, которые соответствуют различным формам умственной деятельности человека и проявляются в двух сферах языка: наблюдаемой и ненаблюдаемой. По определению де Соссюра, в каждом состоянии языка все «покоится» на отношениях, которые сводятся либо к синтагматическим либо к ассоциативным (позднее названных Ельмслевым «парадигматическими»), и описать механизм языка можно лишь установив их. В отличие от синтагматических, парадигматические отношения не линейны и не одновременны в потоке речи или тексте, они представляют собой соотношение между единицами языка, которые объединены некими ассоциациями в сознании говорящего. Связь этих элементов происходит ввиду общности их формы или содержания, или сходства обоих признаков одновременно. Синтагматические отношения определяют строение синтагмы как языковой последовательности любого уровня, и они характеризуют комбинаторику более крупных единиц из более мелких. В свою очередь, парадигматические отношения определяют строение группировок или классов, которые выделены в языке исходя из семантической или формальной общности их членов и одновременно противопоставлены друг другу по одному из перечисленных оснований. В отличие от синтагматических отношений, которые проявляются между элементами одной языковой цепочки (отношения in praesintia), парадигматические отношения определяют следующее (отношения in absentia): присутствие одного из компонентов парадигматического ряда в синтагматической цепочке исключает наличие другого, однако они являются взаимозаменяемыми. [16]

Моделирование парадигматических и синтагматических отношений

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

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

Таким образом, алгоритмы машинного обучения по ходу работы моделируют синтагматические отношения, а те данные, которые подаются им на вход, представляют собой частную модель парадигматических отношений. Набор признаков для моделирования парадигматических отношений может быть подобран исходя из задачи исследования.

2.2 Машинное обучение

Для того чтобы решить задачи, связанные с определением вероятности распределения тегов между словами, используются модели машинного обучения. Выделяют два подхода к решению таких задач: математическое моделирование (model-based reasoning) и восстановление зависимостей путем обработки. Таким образом существует два типа машинного обучения: обучение по претендентам (или индуктивное обучение) и дедуктивное обучение. Первый тип основывается на выявлении общих закономерностей по частным эмпирическим данным, в то время как второй тип предполагает формализацию знаний экспертов и запись в базы знаний. [6]

Основное требования для применения второго типа - наличие обучающей информации. Как правило, в качестве нее выступает выборка претендентов, т.е. ситуационных примеров из прошлого.

В ходе данной работы для распознавания именованных сущностей было использовано несколько алгоритмов.

2.3 Вероятностные подходы выделения информации

Если рассматривать подход к решению задачи с точки зрения распределения вероятностей, то выделяют два типа вероятностных моделей: порождающие/генеративные (generative) и дискриминативные (discriminative).

Для генеративных моделей характерно наличие скрытых параметров. Для того чтобы использовать порождающие модели необходимо задать совместное распределение p(X,T) на всём множестве рассматриваемых объектов. Зная это распределение, мы можем моделировать новые объекты из той же генеральной совокупности. Если же возникает проблема, что происходит в большинстве случаев, такая, то что совместное распределение неизвестно, то его можно настроить по обучающей выборке. Таким образом, генеративные модели уточняют дистрибуцию совместной вероятности. При использовании в машинном обучении они моделируют результаты наблюдения из функций условной вероятности или могут выступать в качестве перехода к функциям условной вероятности. Данный тип может решать более сложные задачи, т.к., используя этот тип, можно выразить более сложные отношения между наблюдаемыми и скрытыми параметрами.

Генеративные модели находят своё применение в Mixture models, стохастической контекстно-свободной грамматике, наивный байесовский классификатор, ограниченная машина Больтцмана, скрытые Марковские модели.

Для того чтобы использовать дискриминативные модели, необходимо знать условное распределение p(T|X) на множестве значений скрытых переменных объекта. В свою очередь, зная условное распределение, мы можем определить значение вероятности скрытых переменных. Отличительной чертой дискриминативных моделей по сравнению с генеративными является тот факт, что дискриминативные модели не позволяют моделировать новые объекты из генеральной совокупности. В том случае, если условная вероятность неизвестна, можно попытаться настроить ее по обучающей выборке. Настройка данного типа вероятностной модели более простая, поэтому разработчику программного комплекса требуется лишь уметь определять значения скрытых переменных по наблюдаемым признакам.

Чаще всего в машинном обучении дискриминативные модели используются для логической регрессии, нейронных сетей, условных рандомных моделей, линейной регрессии, boosting / meta-algoritm.

Перцептрон

Первым использованным алгоритмом является перцептрон. В основе данного алгоритма заложена математическая модель восприятия информации мозгом. Персептрон состоит из трех слоев:

1) Каждый сенсор передает свое значение на ассоциативные элементы.

2) Ассоциативные элементы принимают значение сенсоров, умножают их на их значимость или веса и складывают вместе. В подборе данных весов и заключается обучение модели.

3) Ассоциативные элементы передают вычисленные значения на реагирующие элементы.

4) Реагирующие элементы складывают входящие значения и на основании полученной суммы принимают решение. В данном случае о том, является ли данное слово именованной сущностью, а если да, то какой.

Подробное (математическое) описание алгоритма:

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

Перед тем, как дать определение перцептрона, стоит определить его составные части:

· S-элемент (сенсорный) - чувствительный элемент, который под воздействием какой-либо энергии вырабатывает сигнал. Если этот сигнал превышает некоторое значение b, то на выходе получаем «1», если нет - «0». [14]

· А-элемент (ассоциативный) - логический решающий элемент, который на выходе дает сигнал «1», если алгебраическая сумма входящих в них параметров превышает некоторое значение b (означает, что элемент активный), в противоположном случае возвращает «0». [14]

· R-элемент (реагирующий) - элемент, который на выходе отдает «1», если сумма его входных сигналов строго положительная, или «-1», если полученная сумма строго отрицательна. Если же сумма равна нулю, то выход считается равным нулю (неопределенный). [14]

Описанные выше составные элементы называются простыми, т.к. они реализованы скачкообразными функциями и могут быть представлены в виде схемы, где веса связей S-A могут иметь значения -1, 0, 1, а веса W для связей A-R могут быть любыми:

Рис. 1

Ф. Розенблаттом было введено следующее определение перцептрона:

- сеть, состоящая из S-, A-, R- элементов, с переменной матрицей взаимодействия W (элементы этой матрицы - весовые коэффициенты), которая определяется последовательностью прошлых состояний активности сети. [14]

Если сравнивать разработки Розенблатта и современные статьи, можно выделить четыре класса перцептронов:

· Перцептрон с одним скрытым слоем - классический перцептрон, его изучением занимался Розенблатт. Схема на Рис. 1 отображает принцип его работы - имеется по одному слою S-, A-, R- элементов.

· Однослойный перцептрон - модель, в которой входные элементы соединены напрямую с выходными элементами при помощи системы весов. Является частным случаем классического персептрона, где каждый S-элемент однозначно соответствует одному А-элементу, связи S-А имеют вес «1» и порог А-элементов является b=1.

· Многослойный перцептрон (Розенблатт) - перцептрон, в которым содержатся дополнительные слои А-элементов.

· Многослойный перцептрон (по Румельхарту) - перцептрон, в котором содержатся дополнительные слои А-элементов, и обучение такой сети проводится по методу обратного распространения ошибки. Все слои перцептрона являются обучаемыми.

В современной литературе по машинному обучению под термином «перцептрон» понимают чаще всего однослойный перцептрон.

Таким образом, перцептрон имеет следующее определение:

Дан набор данных D, который содержит в себе набор обучающих данных Х и выходные метки Y, и может быть представлен в виде матрицы.

Каждый из множества X, может быть представлен в следующем виде:

= {, , …, }.

Каждый показывает на отнесенность или не отнесенность классу и принимает бинарные значения: {-1;1}.

W представляет собой вектор весов. Для каждого существует соответствующий вектор весов .

Таким образом, т.к. перцептрон является линейной комбинацией X и W, он может быть определен следующим образом:

Каждый нейрон может быть представлен следующим образом:

где , 1 - если сумма больше некоторой заранее заданной величины , в противном случае 0.

Линейный классификатор со стохастическим градиентным спуском

Следующий алгоритм, это линейный классификатор.

Иначе, провести множество разделяющих линий и по положению относительно этих линий определить класс.

Стохастический градиентный спуск

Для реализации алгоритма необходимо выбрать один объект из обучающей выборки, и затем вычислить градиент функционала только на этом объекте (градиент только одного слагаемого в функционале ошибки). Таким образом, сперва необходимо инициализировать . Цикл идёт по t = 1,2,3…Затем, выбирается случайный объект из X. Вычисления происходя по следующей формуле:

И, если , тогда завершить.

На градиентном спуске в отличии от стохастического, на каждой итерации стараемся уменьшить ошибку на всей выборке, соответственно, график получается гладким. По мере увеличения числа итераций ошибка монотонно уменьшается. Для стохастического - необходимо уменьшить на каждой итерации ошибку только на одном объекте, но при этом, ошибку можно увеличить на другом объекте. Поэтому график получается пилообразный. На какой-то итерации возможно увеличение ошибки, но в целом, ошибка уменьшается. [18][19]

У стохастического градиентного спуска есть ряд преимуществ:

· быстрое вычисление одного шага;

· не требуется хранения всей обучающей выборки в памяти (обучение может происходить на больших данных);

· подходит для онлайн обучения

Линейный классификатор

Может быть представлен следующей формулой:

Где - свободный коэффициент, - веса, - признаки.

Чтобы убрать свободный коэффициент, необходимо добавить единичный признак. Получается следующая формула:

- знак скалярного произведения вектора весов на вектор признаков.

Для задачи бинарной классификации уравнение задает плоскость. Линейный классификатор проводит гиперплоскость в пространстве признаков, и все объекты с одной стороны - относят к классу +1, другой стороны - к классу -1.

Линейный классификатор вычисляет значение скалярного произведения, которое имеет вещественное значение, а затем берет только знак, тем самым отбрасывая часть информации. Однако само значение скалярного произведения имеет смысл. Если взять модуль скалярного произведения и «отнормировать» его (поделить на норму вектора весов), то получается расстояние от точки х до гиперплоскости.

Для понимания работы линейного классификатора важно определить понятие отступ. Отступ представляет собой некоторую величину, которая характеризует корректность ответа. Данная величина может быть представлена в следующем виде:

Соответственно,

- классификатор даёт верный результат;

- классификатор ошибается

Чем дальше отступ от нуля, тем больше уверенности в классификации объекта.

Доля ошибочных ответов представляется в следующем виде:

Доля ошибочных ответов через отступ может быть представлена в следующем виде:

Данная функция ведет себя следующим образом, где по оси Х указывается величина отступа:

Рис. 2

Функция пороговая. Она разрывна, т.к. имеет разрыв в 0, и ее нельзя оптимизировать градиентными методами.

Чтобы решить данную проблему, необходимо задать гладкую оценку пороговой функции, например:

Оценим через нее функционал ошибки:

В данном случае нужно стараться минимизировать не долю неправильных ответов, а среднее значение гладкой функции потерь L~.

Существуют следующие примеры гладких оценок [22]:

· Логистическая:

· Экспоненциальная:

· Кусочно-линейная:

Их графики по отношению к пороговой функции выглядят следующим образом:

Рис. 3

Применив логистическую функцию потерь, формула становится следующей:

Если подставить в формулу скалярное произведение, то получится следующее:

При обучении линейного классификатора нужно оценить сверху долю неправильных ответов с помощью некоторой гладкой функции потерь, и затем минимизировать гладкую функцию потерь с помощью метода оптимизации (например, стохастический градиентный спуск)

Условные случайные поля

Условные случайные поля являются одной из возможных реализаций Марковских случайных полей.

Марковским случайным полем (сетью) называют такую графовую модель, которая используется для представления совместных распределений набора нескольких случайных переменных. Марковское поле формально состоит из следующих компонентов [26]:

· неориентированный граф G = (V,E) такой, что каждая вершина - случайная переменная Х, и каждое ребро -зависимость между случайными величинами .

· набор потенциальных функций , по одной для каждой клики. Данная функция ставит возможному состоянию элементов клики в соответствие некоторое неотрицательное число.

Вершины, которые не являются смежным, соответствуют условно независимым случайным величинам, а группа смежных вершин - образует клики, где набор вершин является аргументом соответствующей потенциальной функции.

Формула совместного распределения набора случайных величин в Марковском случайном поле выглядит следующим образом:

где - потенциальная функция, которая описывает состояние случайных величин в к-ой клике.

Формула для подсчета нормализации Z:

Множество случайных переменных V представляет собой объединение множества входных данных X и множество соответствующим им классов (типов). Для решения задачи извлечения данных из текста достаточно найти условную вероятность P(Y|X). Таким образом, потенциальная функция имеет следующий вид:

где - параметрический вектор с вещественными значениями, и - набор признаковых функций.

Таким образом, линейным условным случайным полем называется следующее распределение вероятности:

А коэффициент нормализации вычисляется по следующей формуле:

Данный метод относится к дискриминативным вероятностным методам. Выбор признаков для данного метода зависит от специфики конкретных данных, а также CRF может учитывать любые взаимосвязи и особенности, которые имеются в исходных данных. Вектор признаков L = {} определяется на основе обучающей выборки и находит вес для каждой потенциальной функции.

В работе С. Суттона [29] было рассмотрено, что скрытую Марковскую модель можно рассматривать как частный случай условного случайного поля (CRF), тогда как CRF является разновидностью Марковского случайного поля.

Для скрытых Марковских моделей:

Рис. 4

Для условного случайного поля:

Рис. 5

На рисунках представлены графы для двух различных методов. Белые окружности говорят о том, что в модели не учитывается распределение случайной величин, а стрелки показывают на зависимые узлы.

Преимущество данного метода заключается в том, что алгоритм не требует предположения о независимости наблюдаемых переменных. Более того, использование произвольным образом взятых факторов позволяет описать разнообразные признаки для определяемых объектов, а это, в свою очередь позволяет использовать корпуса разного наполнения [1].

3. Практическая часть

сущность лингвистический синтаксический

3.1 Общее описание работы программы