Содержание к диссертации
Введение
Глава 1. Задачи предсказания структур: проблемы и подходы к их ешению 13
Глава 2. Методы построения отображений на основе вероятностных оделей 28
2.1. Постановка задачи ; 28
2.2. Ядро Фишера для предсказания структур 29
2.3. Ядро ТОР для перестановки гипотез 30
2.4. Применение отображений 37
2.5. Эксперименты 38
2.5.1. Вероятностная модель 39
2.5.2. Построение отображения 42
2.5.3. Обучающий алгоритм 45
2.5.4. Методы оценки точности в синтаксическом анализе 47
2.5.5. Постановка эксперимента и экспериментальные результаты 50
2.6. Выводы 54
Глава 3. Использование вероятностных моделей для оптимизации жидаемой ошибки с произвольными функциями потерь 55
3.1. Постановка задачи 56
3.2. Аппроксимация ожидаемой потери с помощью вероятностной одели 58
3.3. Аппроксимация ожидаемой потери с помощью дискриминативных моделей 59
3.3.1. Аппроксимация с ядром Фишера для предсказания структур. 61
3.3.2. Аппроксимация с ядром TRK 64
3.3.3. Аппроксимация на основе произвольной дискриминативной модели... 65
3.4. Использование отображений, нацеленных на минимизацию ожидаемой ошибки... 66
3.4.1 Ядро потерь 66
3.4.2 Ядро логит потерь 61
3.5. Эксперименты 69
3.5.1. Вероятностная модель и построение отображения 70
3.5.2. Эксперименты с использованием SVM 71
3.5.2. Эксперименты с перцептроном с голосованием и отображением TRK 75
3.5.3. Эксперименты с перцептроном с голосованием и ядром свертки для деревьев 77
3.6. Выводы 78
Глава 4. Адаптация статистических методов с использованием отображений, основанных на вероятностных моделях 80
4.1. Постановка задачи и обзор предлагаемых методов 81
4.2. Возможности по репараметризации отображений 84
4.3. Перемещение в новую область... 84
4.4. Фокусировка на области 87
4.5. Эксперименты 88
4.5.1. Используемые наборы данных и методы 88
4.5.2. Эксперименты для подхода «перемещение» 90
4.5.3. Эксперименты для подхода «фокусировка» 91
4.5.4. Эксперименты: распределение слов против распределения структур 93
4.5.5. Обсуждение результатов 94
4.6. Предшествующие исследования в области адаптации 96
4.7. Выводы 98
Глава 5. Методы объединения вероятностных моделей с линейными моделями, использующими произвольные пространства свойств 99
6.1. Постановка задачи 100
6.2. Построение отображения ... 102
6.3. Оценка обобщающей способности 103
6.4. Выводы 104
Глава 6. Решение проблем с большим, но ограниченным числом ыходных категорий 106
6.1. Постановка задачи 107
6.2. Критерий оптимизации 109
6.3. Оценка обобщающей способности 111
6.4. Эксперименты 114
6.5. Выводы 114
щ Заключение 116
Список литературы
- Ядро ТОР для перестановки гипотез
- Аппроксимация ожидаемой потери с помощью вероятностной одели
- Возможности по репараметризации отображений
- Построение отображения
Введение к работе
Актуальность темы
Большинство вопросов, возникающих в практической деятельности, требуют большего, чем ответ да-нет или выбора решения из нескольких фиксированных альтернативных вариантов. Задачи со сложными ответами (задачи предсказания структур) встают, например, в таких областях, как биология, химия, фармакология, диалоговые системы, вычислительная лингвистика, компьютерное зрение и т. д. Построение эффективных статистических моделей, позволяющих автоматически получать ответы на вопросы, является областью исследования дисциплины машинное обучение, но исследования в области машинного обучения, в первую очередь, были сконцентрированы лишь на задачах с фиксированным и малым числом ответов, стандартных задачах классификации.
Классическим подходом к предсказанию структур, доминировавшим в 90-х годах прошлого века и остающимся актуальным до сих пор, является построение генеративных вероятностных моделей в форме, задаваемой специалистами прикладной области и с параметрами, оцениваемыми на основе составленных вручную обучающих наборов. Построены многие десятки таких моделей для различных прикладных областей. В то же время последние результаты исследований в области машинного обучения продемонстрировали, что точность предсказания с использованием генеративных вероятностных моделей, в общем случае, уступает результатам новых статистических дискриминативных методов, разработанных в последнее десятилетие, например, методов, максимизирующих зазор [1].
Большинство из построенных за последнее время методов машинного обучения не могут быть непосредственно применены к задачам предсказания структур. Существует ряд факторов, ограничивающих их применение. И, в первую очередь, это неограниченность числа возможных структур, необходимость введения функций потерь, сложность моделирования распределения структур и значительная разреженность обучающих наборов. Решение всех этих, а также других проблем, связанных с предсказанием структур, имеет огромную практическую ценность и определяет развитие соответствующих проблемных областей.
Одной из важных и сложных проблем, которые необходимо решать для применения таких статистических методов является необходимость задания адекватного пространства свойств, в котором будет возможно применять статистический дискриминативный метод. Учитывая, что за последние полтора десятка лет предложено большое число вероятностных моделей для различных прикладных областей, привлекательным подходом кажется разработка методики автоматического построения пространств свойств на основе произвольной, но фиксированной вероятностной модели. Этому не изученному в контексте предсказания структур подходу, в первую очередь, и посвящена диссертация. Результирующий метод, состоящий из вероятностной модели и метода, максимизирующего зазор, работающего в сконструированном пространстве свойств, должен позволить улучшить результаты произвольных вероятностных моделей для произвольных прикладных областей.
Для большинства приложений не только полностью правильная, но даже частично правильная структура представляет значительную ценность. Из этого следует необходимость построения моделей, нацеленных на минимизацию не функций потерь точного совпадения (дельта-функций), а более сложных функций потерь, определяемых прикладной областью.
Объединение вероятностных моделей и статистических методов, максимизирующих зазор, может лечь в основу построения новых подходов к решению этой проблемы.
Существует и другая актуальная проблема методов предсказания структур. Это необходимость применения статистических моделей к данным с распределением, отличным от распределения данных в исходном наборе. Совместное использование вероятностных моделей и статистических методов, максимизирующих зазор, позволяет предложить новое решения и для этой проблемы.
Цель работы
Цель работы состояла в разработке нового подхода к решению задач предсказания структур, который позволил бы применять современные методы машинного обучения к произвольным задачам предсказания структур. Для достижения этой цели необходимо решить следующие задачи:
1. Разработать методы построения отображений на основе вероятностных моделей для задачи предсказания структур.
Разработать новые методики учета функции потерь для статистических моделей предсказания структур, направленные на улучшения точности модели.
Создать методики адаптации статистических моделей предсказания к изменению распределения входных и выходных данных.
Предложить новые способы объединения вероятностных моделей и методов, использующих заданные в явном виде пространства свойств.
Провести теоретический анализ предложенных методов и методик и исследовать их свойства на практике. Продемонстрировать на практике преимущества предлагаемых подходов перед альтернативными методами.
Научная новизна
На основе проведенного системного анализа современных методов машинного обучения предложено новое направление решения задач предсказания структур. Разработаны новые методы построения отображений в пространства свойств на основе вероятностных моделей для задач предсказания структур, проведен аналитический и эмпирический анализ методов. Исследованы методики эффективного вычисления таких отображений для моделей на основе многоуровневого перцептрона.
Предложены новые методики учета функции потерь в статистических моделях предсказания структур, позволяющие значительно улучшить результаты для широкого класса моделей.
Предложены новые методики к адаптации статистических моделей предсказания структур при изменении распределения входных и выходных данных, обеспечивающие значительное повышение точности предсказания.
Построен новый способ объединения вероятностных моделей и методов, использующих произвольные пространства свойств.
Получен новый критерий обучения стандартного метода SVM (машины поддерживающих векторов) для случая несимметричной задачи классификации, проведена теоретическая оценка обобщающей способности методов, использующих такой критерий, и проведен экспериментальный анализ.
Практическая значимость работы
Разработанные методы могут применяться для улучшения результатов широкого спектра методов предсказания структур, как при использовании функции потерь точного совпадения, так и в случае более сложных, но более мотивированных функций потерь. Вычисления отображений на базе вероятностных моделей, как правило, не приводят к существенному увеличению вычислительной сложности и не требуют привлечения эксперта прикладной области, но позволяют надеяться на значительное повышение точности классификации по сравнения с точностью, обеспечиваемой используемой вероятностной моделью. Предлагаемая методика адаптации позволяет производить адаптацию обученной модели не только к областям, отличающимся вероятностным распределением структур (например, синтаксический анализатор обучается на корпусе финансовых новостей WSJ, а затем применяется к корпусу биологических статей), но и к областям с отличающимися схемами аннотации.
Программная реализация описанных в диссертации методов для задачи синтаксического анализа доступна для любых исследований в области обработки естественного языка.
Защищаемые положения
Разработанные методы построения пространств свойств на основе вероятностных моделей для задачи предсказания структур позволяют добиться повышения точности предсказания по сравнению с использованием исходной вероятностной модели.
Предложенные новые методики аппроксимации ожидаемой ошибки на основе вероятностных моделей обеспечивают значительное улучшение результатов по сравнению с исходной вероятностной моделью.
Построенные функции отображения могут использоваться для адаптации моделей к распределению данных, отличных от исходного распределения в обучающем наборе.
Разработанная методика построения отображений на основе вероятностных моделей позволяет предложить новый способ объединения вероятностных моделей для предсказания структур и линейных методов, использующих произвольные пространства свойств.
5. Предложенная новая модификация критерия оптимизации стандартного метода Машины Поддерживающих Векторов позволяет добиться повышения точности классификации для случая несбалансированных наборов данных.
Публикации и апробация работы
Содержание диссертации раскрыто в следующих 4 работах, опубликованных по теме диссертации в трудах ведущих российских и международных конференций:
1. Титов И., Хендерсон Дж. Метод синтаксического ' анализа с использованием определяемых обучающим набором ядер, построенных на основе вероятностных моделей.//Международная конференция Компьютерная лингвистика и интеллектуальные технологии (Диалог-2005). Москва, 2005.-С.131-135. Titov I., Henderson J. Deriving Kernels from MLP Probability Estimators for Large Categorization Problems. II In Proc. International Joint Conference on Neural Networks (IJCNN-05). Montreal, Canada, 2005.-p.937-942. Henderson J., Titov I. Data-Defined Kernels for Parse Reranking Derived from Probabilistic Models. II In Proc. 43rd Meeting of Association for Computational Linguistics (ACL-05). Ann Arbor, USA, 2005.-p.l81-188. Kosinov S., Titov I., Marchand-Maillet S.. Large Margin Multiple Hyperplane Classification for Content-Based Multimedia Retrieval. II In Proc. International Conference on Machine Learning (ICML-2005), Workshop on Machine Learning Techniques for Processing Multimedia Content. Bonn, Germany, 2005.-p.60-63.
По результатам проведенных исследований были сделаны доклады на следующих конференциях: Международная конференция «Вычислительная лингвистика и интеллектуальные технологии» (Москва, Россия, 2005 г.); 43rd Annual Meeting of Association for Computation Linguistics, (Анн Арбор, США,
2005 г.); International Joint Conference on Neural Networks (Монреаль, Канада, 2005 г.); International Conference on Machine Learning, Workshop on Machine Learning in Multimedia (Берлин, Германия, 2005).
Личный вклад автора
Основные результаты работы получены автором лично. Научные положения, теоретические выводы, расчеты и эксперименты разработаны и проведены автором самостоятельно. Разработка моделей, методик и способов осуществлялась при участии научного руководителя и соавторов.
Структура и объем диссертации.
Диссертация состоит из введения, 6 глав, заключения и списка литературы. Диссертация содержит 126 страниц, в том числе 9 рисунков. Список литературы включает 90 наименований.
Ядро ТОР для перестановки гипотез
Сделав предположение о том, что истинное распределение вероятности Р(х,у) принадлежит множеству распределений вероятностей, описываемых моделью Р(х,у в) с некоторым значением параметра в, т.е. Р(х,у) = Р(х,у \ в ), получаем возможность аппроксимации логарифма г(у,х) данного выражения вокруг точки в в форме первых двух членов ряда Тейлора:
Если определить отображение как ;)-№л4 ). (2.9) тогда линейный классификатор с вектором = (1,0 -01V..,# -#т) будет осуществлять аппроксимацию (2.8). Таким образом, ядро (2.9) оказывается мотивированным с точки зрения аппроксимации г(у,х) первого порядка. Назовем скалярное произведение в пространстве, задаваемом отображением (2.9), ядром ТОР для перестановки гипотез (TOP Reranking Kernel, TRK).
Легко заметить, что, если список кандидатов велик и Р(у,х\0)« Р(у,х\в), отображение ядра TRK (2.9) близко к отображению усС(х) ядра Фишера (2.3). Однако на практике в значительном большинстве случаев невозможно получение большого списка. Объясняется это тем, что вычислительная сложность поиска списка кандидатов G(x) базовой модели, как правило, связана нелинейной зависимостью с размером этого списка.
Другой способ аргументации TRK близок к аргументации ядра ТОР для бинарной классификации [16] и основывается на оценке условной вероятности Р(у,х\в) или, что то же самое, на оценке величины ожидаемой потери от выбора элемента у. Рассмотрим оценку условной вероятности P(v х\0 } p(y\G(x))= Г; / в форме g(wT p(x,y)), где g - логарифмическая \ Р(у,х\в) y eG(x) сигмоидальная фикция , 8 = -гГ-г- (2-Ю) 1 + е Ожидаемая ошибка подобной оценочной функции с оптимальной гиперплоскостью w может быть записана как D( p) = mmEx wgx\g(wTrtx,y)- 1% }в. . . (2.11) y eG(x) Докажем теорему о связи ошибки оптимального классификатора в пространстве, заданном отображением д : 1 ) = 11 7 = )- ))}) (2.12) w w у eG(jt) с ошибкой оценочной функции D(cp). Теорема 2.1. TR{ p) - L 2D( p), где Ґ- ошибка Байеса, т.е. ошибка классификатора, выбирающего кандидата у с наибольшей вероятностью Р(у,х\в ): Г =1,(1-max 1(У Х}в \). (2.13) У еС(х) п Зафиксируем JC и параметр линейной модели w. Введем обозначения: у -структура, выбранная линейной моделью из списка кандидатов: 3 у = arg max wq){x, у1), у - наиболее вероятная структура в списке кандидатов: у = argmaxP(y, х \ в ). У еО(х) Оценим сверху разность вероятностей структур у и у через точность оценки вероятности в форме g(wT(p(x,y)): Р{у,х\в ) Р(у,х\0 ) ЦР(у ,х\в ) І,Р(У ,Х\Є ) /ев(х) /еС(х) Р(У,х\бГ) ЪПУ ,Х\9 ) y G(x) --g(w (x,/) Р(у,х\6) , Г /" ,«чч \ G(x) а с учетом того, что g(wT p(x,y )) g(wT p(x, у)), Р(/, 0 ) Р{у,х\в ) %Р(у ,х\в ) Пу ,х\в ) Р(/, бГ) /ЄЄ(дг) ir-g X ,/) Р(У,х\в-) Т,Р(У ,Х\Р) Ky zG(x) g(wT p(x,y)) 2max\g(w (x,y))- % }в .\. A yeG(x) 2І,Р{у\х\в ) Из данного неравенства сразу же следует условие теоремы, так как неравенство верно для произвольного входа х и произвольной гиперплоскости W. Из доказанной теоремы следует, что естественным подходом для минимизации TR( p), является выбор отображения р, минимизирующего D((p). Для достижения D( p) = О потребовалось бы выполнение условия:
Аппроксимация ожидаемой потери с помощью вероятностной одели
Как уже обсуждалось в главе 1, оценка результатов моделей с использованием функции потерь точного совпадения, равной единице при совпадении предсказания модели с правильной структурой, и нулю в противном случае, не является правильным подходом. Для большинства приложений частично правильные структуры представляют значительную ценность. Для решения этой проблемы существуют различные подходы для учета функций потерь в обучающих алгоритмах [17,18,23,49]. В ряде прикладных областей, где ставится задача предсказания структур, рассматривалась минимизация ожидаемой ошибки, например, в машинном переводе [50], синтаксическом анализе естественного языка [49], распознавании речи [51,52]. Задача минимизация ошибки также рассматривалась в контексте стандартной задачи классификации [53]. Однако до сих пор не предпринималось попыток непосредственно аппроксимировать ожидаемую ошибку для задачи предсказания структур1. В настоящей главе предложено несколько новых подходов к аппроксимации ошибки на основе списка кандидатов, предоставляемых вероятностной моделью, в частности, подходы, использующие отображения в пространства свойств на основе вероятностных моделей.
Интуитивное объяснение идей, лежащих в основе предлагаемых методов, может быть проведено на следующем простом примере. Рассмотрим ситуацию, когда имеется группа из нескольких очень близких друг к другу кандидатов и один очень сильно отличающийся от них кандидат, вероятность которого лишь немного больше, чем вероятность каждого кандидата из группы, и намного меньше, чем их суммарная вероятность. Метод, выбирающий кандидата с максимальной вероятностью, выберет этого отдельно стоящего кандидата, что является правильным решением, если интересует только точное совпадение структур и если оценки вероятности, которыми располагает метод, абсолютно точны. В то же время, если потеря от ошибки в выборе кандидата мала, когда выбранный кандидат близок к правильному кандидату (то есть используется более сложная функция потерь), то более правильным будет выбор какого-либо кандидата из группы близких кандидатов. При таком выборе кандидата потеря будет велика только, когда отдельно стоящий кандидат оказывается правильным. Другими словами, ожидаемая ошибка от выбора кандидата из группы будет меньше, чем ожидаемая ошибка от выбора отдельно стоящего кандидата.
Более строго, мы можем определить, как и в (1.12) ошибку модели предсказания у = h(x) в виде: R(h) = EXtyA(y,h(x)), (3.1) где математическое ожидание взято по всем возможным входам х и структурам у,, a A(j ,y), как и ранее, обозначает потерю, вызванную предсказанием структуры у в ситуации, когда правильной структурой является у. Как и ранее, мы предполагаем, что функция потерь А принимает значения в диапазоне [0..1], что равносильно требованию ее ограниченности. Из определения ошибки (3.1) следует, что оптимальная модель h выбирает кандидата, который минимизирует ожидаемую ошибку:
Данное допущение позволяет аппроксимировать ожидаемую ошибку для структуры следующим выражением: 1(х,у) = = -. (3.4) уев(х) В случае моделей перестановки, часто вероятностная модель оценивает лишь совместную вероятность Р(х,у), а, следовательно, оценка величины 1(х,у) может быть проблематичной. Однако, коэффициент нормализации не оказывает влияния на классификацию. Поэтому заменив вероятности на их оценки, мы получаем следующую модель предсказания: A( ) = argmin %р(х У\в)А(У У) (3-5) у ев(х) уев(х) где в обозначает, как и ранее, набор параметров вероятностной модели, определенных на основе обучающих данных.
В этом разделе мы предлагаем метод улучшения аппроксимации ошибки, использованной в (3.5), за счет оценки вероятности на основе обученных дискриминативных статистических моделей. Под дискриминативными моделями понимаются методы, нацеленные непосредственно на улучшение способностей модели различать правильные и неправильные предсказания, а не на оптимизацию критериев, лишь косвенно связанных с ожидаемой ошибкой (например, на максимизацию правдоподобия обучающего набора (1.1)). Примером дискриминативных моделей могут служить методы, максимизирующие зазор (см. обсуждение в главе 1). Как мы уже отмечали в Н\х) = атётш Р(у\х)А(у,у ), (3.2) y eG(x) у где G(x) - список кандидатов, предоставляемый базовой моделью, а суммирование производится по всем возможным структурам у для входа х, а не только по кандидатам из списка.
В следующих разделах настоящей главы рассматриваются различные подходы к аппроксимации ожидаемой ошибки от выбора кандидатов и проводится экспериментальное сравнение подходов на примере задачи синтаксического анализа.
Возможности по репараметризации отображений
В сценарии.«перемещение» используем вероятностную модель, которая была обучена только на большом корпусе из исходной области. В нашем эксперименте большой корпус не доступен в процессе перемещения, а маленький корпус для целевой области не доступен во время обучения вероятностной модели. Таким образом, мы имеем подход чистого перемещения парсера, так как он требует лишь парсер для исходной области, но не требует обучающих данных для исходной области. Кроме теоретической значимости такой постановки задачи, этот сценарий обладает еще одним преимуществом: он требует обучения только синтаксического анализатора, что уменьшает временные затраты. К тому же, сценарий не требует доступа к исходным обучающим данным, когда это обучение уже выполнено. Таким образом, получается, что может быть обучено неограниченное число моделей для разных новых областей, и для этого понадобится лишь небольшой объем данных для их обучения, а, следовательно, затрачено будет меньшее время.
Наш подход «перемещение» предполагает вначале определение отображения на основе параметров вероятностной модели. А затем уже метод, максимизирующий зазор, обучается переставлять кандидатов, предоставленных вероятностной моделью. Итак, получаем: итоговая модель синтаксического анализа будет состоять из исходного парсера и очень дешевого вычислительно метода, выбирающего лучшее дерево синтаксического анализа из списка.
Несмотря на то, что обучение стандартных методов, максимизирующих зазор, невозможно на больших обучающих наборах, оно, вместе с тем, вполне допустимо на небольшом корпусе для определенной целевой области . Кроме того, выбор для нашего эксперимента метода, максимизирующего зазор, продиктован лучшими обобщающими свойствами таких моделей на небольших обучающих зазорах. На таких малых наборах невозможно обучение точной вероятностной модели.
В соответствии с нашей гипотезой, главной проблемой для адаптации моделей синтаксического анализа являются имеющиеся различия в распределении слов между областями. Чтобы хотя бы частично решить данную проблему, мы предлагаем строить отображение на основе модели, репараметризированной для большого соответствия набору слов, целевой области. Все лексиколизированные модели4, в том числе и используемая в наших экспериментах модель SSN [30], рассматривают редкие слова как неизвестные и используют только информацию о частях речи, соответствующих этим словам. Такая информация о частях речи предоставляется таггером, он предварительно обрабатывает предложения и выдает соответствие между словами и частями речи.5 Иными словами, получается, что лексикализированная модель не содержит индивидуальных параметров для редких слов. И когда происходит переключение на новую область, значительное число слов из новой области воспринимается уже моделью как неизвестные , что делает синтаксический анализатор лишь слабо лексиколизированным.
Для решения этой проблемы, предлагается репараметризировать вероятностную модель так, чтобы добавить отдельные параметры для слов, достаточно часто встречающихся в обучающем наборе корпуса для целевого домена, но рассматриваемых исходной вероятностной моделью как неизвестные . Для каждой части речи параметры, соответствующие таким «новым» словам, определяются равными параметрам, соответствующим неизвестному слову. И поэтому распределение вероятности, задаваемое моделью, не меняется. Однако когда строится отображения на основе репараметризированнои вероятностной модели, то вектор в пространстве свойств будет содержать отдельные компоненты для каждого из таких слов, и, следовательно, линейная модель получит различные значения соответствующих компонентов решающего вектора w в процессе обучения. Различия в этих компонентах решающего вектора должны отражать различия в распределении этих слов и помогать в выборе наиболее правильного дерева. Расширение словаря (набора слов, различаемых моделью) с использованием такого подхода также может быть аргументировано задачей построения эффективной вычислительной модели. Скорость работы вероятностной порождающей модели, такой как, например, SSN, зависит от величины используемого словаря (числа слов с индивидуальными параметрами), но, в тоже время, он не оказывает существенного влияния на скорость работы метода, максимизирующего зазор.
Построение отображения
Отображение TRK для модели вида (5.2), как и для лог-линейной локально нормализованной модели, рассматривавшейся в главе 2. (2.21), принимает вид: p.(x,y)=(\ogP(x,y\0)-\oe YA y\Qi 1 , - (5.5) ?(Х У)—v T—ЇТ 1Л У) р(х,у)). у єС(х)/у
Как отмечалось ранее, решающие функции для многих критериев обучения могут быть записаны в неявном виде с использованием ядер К((х,у),(х ,у )) = (р(х,уУ(р(х ,у ). Для таких моделей может использоваться бесконечномерное и многомерное отображение. Достаточно лишь обеспечить эффективное вычисление ядра, как правило, с использованием схем динамического программирования. Запишем ядро Ктк от пар кандидатов из списков G(x) и G(JC ), соответствующее отображению (5.5): №,У№,У))- А ЦР(У,Х\0)ЩХ,У), ,У)) уєС{х)/у - - Jj&JMMkyU .?))
Из выражения (5.6) следует квадратичное от длины списка G(x) увеличение сложности вычисления ядра Kj r по сравнению с вьгаислением исходного ядра К. В тоже время, необходимо учесть, что на практике в большинстве случаев требуется производить вычисления ядер между элементами всех пара. И тогда дополнительные издержки будут незначительны, так как ядра К будут вычисляться однократно для каждой пары. Возможно также более эффективное вычисление линейной комбинации ядер Yjfix,y,K((x y) (x y )) ДДЯ большинства ядер К, потому что структуры в y eG(x ) листе кандидатов y eG(x ) близки. Тогда, как правило, они могут быть выровнены. И выровнены так, что было возможно применение схем динамического программирования для вычисления ]/?ху.К((х, у), (У, у )) 2.
Предположение (5.3), а также предположение о реализуемости действительной функции вероятности в обоих распределениях Р и Р9 , то есть предположение о существовании таких в" и С1\ что Р(у,х\в ) Р(у,х) , ч Р,(у 1 ,Q v ; ,L= vr; \, (5.7) уеО(дг( eG(j:( позволяет применить к отображению (5.5) теорию, разработанную в главе 2. Перейдем к рассмотрению следующей теоремы. Она является непосредственным следствием теоремы 2.2. , где М - максимальное значение компонент функций отображения д исходного ядра на суппорте распределения Теорема 5.1. R((pe) L + 2AM2 J 9} - Є] \і=\,т P(y,x), R( pe) - ошибка оптимальной линейной модели в пространстве, заданном рё , L - ошибка оптимальной модели . П. Для применения Теоремы 2.2. нам необходимо получить только оценку модуля первой Мj и второй смешанной М2 производных от логарифма вероятности Рр(у\х) (5.2). Первая производная записывается как 31ogP,(yU,n) " „ , ч яо = Р& У)- ЦРЛУ\х,ПУр;(х,У), (5.8) и, следовательно, получаем М, 2М. (5.9) я Повторно продифференцировав (5.8) по —- , ползаем: дС1к д2\оёРр(у\х,П) ,dbgP y\xA) ,_inV т т- = 2ІРЛх,у)Р,(У\х,П) - , (5.10) Учитывая (5.9) , приходим к следующему: М2 2М\ (5.11)
Подставив оценки модулей производных (5.9) и (5.11) в теорему 2.2, имеем, наконец, заявленную верхнюю оценку обобщающей способности линейного метода. М
Мы предложили новую методику объединения вероятностных моделей и линейных моделей перестановки, использующих произвольное пространство свойств, для задачи предсказания структур. Для этого мы применили разработанную нами методику построения отображений на основе вероятностных моделей. Скалярное произведение в новом пространстве может быть вычислено на основе скалярных произведений в исходном пространстве, и, следовательно, возможно применение нового метода объединения моделей и для линейных методов, производящих классификацию в бесконечномерных и многомерных пространствах.
