Читаем без скачивания Верховный алгоритм - Педро Домингос

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

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

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

Коннекционистские модели вдохновлены головным мозгом. Нейронам в них соответствуют сети S-образных кривых, а синапсам — взвешенные соединения между ними. В Alchemy две переменные соединены между собой, если они появляются вместе в какой-то формуле, и вероятность переменной при данных соседях — это сигмоида. (Я не буду объяснять, почему это так, но это прямое следствие верховного уравнения, которое мы видели в предыдущем разделе.) Свой верховный алгоритм — обратное распространение ошибки — коннекционисты используют для того, чтобы определить, какие нейроны отвечают за какие ошибки, и в соответствии с этим подобрать веса. Обратное распространение — это разновидность градиентного спуска, который используется в Alchemy для оптимизации весов логической сети Маркова.

Эволюционисты используют генетические алгоритмы для симуляции естественного отбора. Генетический алгоритм поддерживает популяцию гипотез и в каждом поколении проводит кроссинговер и мутации наиболее приспособленных из них, чтобы породить следующее поколение. Alchemy поддерживает популяцию гипотез в виде взвешенных формул, на каждом этапе по-разному их модифицирует и поддерживает вариации, которые больше всего увеличивают апостериорную вероятность данных (или какую-то другую оценивающую функцию). Если популяция — это одна гипотеза, все сводится к восхождению на выпуклые поверхности. В данный момент доступный для скачивания алгоритм Alchemy не включает кроссинговер, но его несложно добавить. Верховный алгоритм эволюционистов — это гене­тическое программирование, которое применяет кроссинговер и мутации к компьютер­ным программам, представленным в виде деревьев под­программ. Сами деревья по­дпрограмм могут быть представлены наборами логических правил, и язык программирования Prolog делает именно это: каждое правило в нем соответствует подпрограмме, а его предшественники — подпрограммам, которые она вызывает. Поэтому можно представить себе Alchemy с кроссинговером как генетическое программирование с использованием похожего на Prolog языка. Дополнительным преимуществом станет то, что правила могут быть вероятностными.

Байесовцы убеждены, что ключ к обучению — моделирование неопределенности, и применяют для этого формальные представления, например байесовские и марковские сети. Как мы уже видели, марковские сети — это особый тип логической сети Маркова, а байесовские сети можно легко представить с помощью основного уравнения логической сети Маркова со свойством для каждого возможного состояния переменной и ее родителей и логарифмом соответствующей условной вероятности в качестве весов. (Нормировочная константа Z удобно сводится к единице, то есть ее можно проигнорировать.) Верховный алгоритм байесовцев — это теорема Байеса, внедренная с помощью алгоритмов вероятностного вывода, например распространения степени уверенности и MCMC. Как вы, может быть, заметили, теорема Байеса — это частный случай верховного уравнения, где P = P(A|B), Z = P(B), а свойства и веса соответствуют P(A) и P(B|A). Система Alchemy включает для логического вывода и распространение степени уверенности, и MCMC, обобщенные, чтобы оперировать взвешенными логическими формулами. Применяя вероятностный вывод к предоставленным логикой линиям доказательств, Alchemy взвешивает аргументы «за» и «против» и выдает вероятность вывода. Это контрастирует с «типовой» логикой «все или ничего», которую применяют символисты и которая не работает, если дать ей противоречивые доказательства.

Аналогизаторы учатся, выдвигая гипотезу, что у объектов со схожими известными качествами неизвестные качества тоже схожи: пациенты с аналогичными симптомами имеют аналогичные диагнозы, читатели, которые купили в прошлом те же самые книги, будут их покупать и в будущем и так далее. Логические сети Маркова могут представлять схожесть между объектами в виде формул, например «Люди с одинаковыми вкусами покупают одинаковые книги». В таком случае чем больше одинаковых книг купили Элис и Боб, тем больше вероятность, что у них одинаковые вкусы, и (применяя ту же самую формулу в противо­положном направлении) тем больше вероятность, что Элис купит книгу, если ее купил Боб. Сходство между ними представлено вероятностью совпадения вкусов. Чтобы извлечь из этого настоящую пользу, можно ввести разный вес для частных случаев одного правила: если Элис с Бобом купили одну и ту же редкую книгу, это, вероятно, дает больше информации, чем если бы они купили бестселлер, поэтому вес события будет выше. В данном случае свойства, сходства которых мы вычисляем, дискретны (купил / не купил), но можно представить сходство и между непрерывными характеристиками, например расстоянием между двумя городами, если ввести в логическую сеть Маркова такое сходство в виде свойства. Если функция оценки — не апостериорная вероятность, а похожая на зазор функция присвоения очков, получится обобщение метода опорных векторов, верховного алгоритма аналогизаторов. Более серьезным вызовом для нашего варианта верховного обучающего алгоритма будет воспроизведение отображения структур — мощной разновидности аналогии, способной переносить выводы из одной области (например, Солнечной системы) в другую. Этого можно достичь путем выведения формул, которые не обращаются к конкретным отношениям в исходной области. Например, утверждение «Друзья курильщиков тоже курят» относится к дружбе и курению, а «Связанные объекты имеют схожие свойства» — к любому отношению и свойству. Такие формулы можно получить путем обобщения частных случаев: «Друзья друзей тоже курят», «Коллеги экспертов тоже эксперты» и других таких паттернов в социальной сети, а затем применить полученные формулы, скажем, к сети с частными случаями вроде «Интересные страницы имеют ссылки на интересные страницы» или к молекулярной биологи, где случаями будут «Белки, которые взаимодействуют с регулирующими гены белками, тоже регулируют гены». Ученые в моем и не только моем коллективе сделали все это и многое другое.

Благодаря Alchemy возможны пять типов обучения без учителя, которые мы видели в предыдущей главе. Очевидно, что он способен на реляционное обучение, и пока в большинстве случаев его применяли именно так. Alchemy использует логику для представления отношений между объектами, а сети Маркова — чтобы они могли быть неопределенными. Его можно превратить в обучающийся алгоритм с подкреплением, обернув вокруг него отложенные награды и применяя его для получения значений каждого состояния таким же образом, как в традиционных обучающихся алгоритмах с подкреплением, например нейронных сетях. Мы можем выполнять с помощью Alchemy образование фрагментов, если введем новую операцию, которая будет сжимать цепочки правил в отдельные правила. (Например, «Если A, то B» и «Если B, то C» в «Если A, то С».) Логическая сеть Маркова с одной ненаблюдаемой переменной, соединенной со всеми наблюда­емыми, выполняет кластеризацию. (Ненаблюдаемая переменная — это переменная, значение которой мы никогда не видим в данных. Можно сказать, что она «скрыта» и ее можно только вывести.)