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

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

Если в логической сети Маркова более одной ненаблюдаемой переменной, она выполняет своего рода дискретное понижение размерности, делая выводы о значении этих (менее многочисленных) переменных на основе (более много­численных) наблюдаемых. Alchemy может справиться и с логической сетью Маркова с непрерывными ненаблюдаемыми переменными, которые нужны, например, для анализа главных компонентов и Isomap. Таким образом, Alchemy в принципе может делать все, что мы хотим от Робби, или по меньшей мере все, что мы обсуждали в этой книге. В действительности мы использовали Alchemy, чтобы научить робота картировать среду, определяя по данным из сенсоров, где находятся стены и двери, их углы и расстояния и так далее, а это первый шаг к созданию квалифицированного домашнего робота.

Наконец, Alchemy можно превратить в метаалгоритм наподобие стэкинга, если закодировать индивидуальные классификаторы, как логическая сеть Маркова, и добавить или вывести обучающие формулы, чтобы их соединить. Именно это сделали в DARPA. Проект PAL (Personalized Assistant that Learns) был для них крупнейшим в области искусственного интеллекта и стал предшественником Siri. Целью PAL было создание автоматического секретаря. Марковская логика использовалась в нем как всеобъемлющее представление, соединяя выходы из разных модулей в решения, что делать. Кроме того, это позволяло модулям PAL учиться друг у друга путем эволюции в сторону консенсуса.

На сегодняшний день одним из самых успешных применений Alchemy было создание семантической сети (или графа знаний, как это называют в Google) на основе интернета. Семантическая сеть — набор понятий (например, «планеты» и «звезды») и отношений между этими понятиями (планеты вращаются вокруг звезд). Alchemy вывел из полученных из сети фактов более миллиона таких паттернов (например, то, что Земля вращается вокруг Солнца) и совершенно самостоятельно открыл такие понятия, как «планета». Мы использовали более совершенную версию, чем базовый алгоритм, которую я описываю в этой книге, но важнейшие идеи те же. Различные исследовательские группы применяли Alchemy в своей работе для решения проблем обработки естественных языков, компьютерного зрения, распознавания активности, анализа социальных сетей, а также в молекулярной биологии и многих других областях.

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

Машинное обучение в планетарном масштабе

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

Логический вывод в Alchemy — сочетание логического и вероятностного выводов. Первый реализован путем доказательства теорем, а второй — путем распространения степени уверенности, MCMC и другими методами, которые мы рассматривали в главе 6. Мы соединили и то и другое в вероятностное доказательство теорем, и ключевым элементом системы Alchemy в настоящее время стал единый алгоритм вывода, способный вычислить вероятность любой логической формулы. Однако он может быть очень затратным с точки зрения вычислений. Если бы ваш мозг пользовался вероятностным доказательством теорем, тигр съел бы вас, прежде чем вы сообразили бы, что надо бежать. Это высокая цена за обобщенность марковской логики. Поскольку мозг человека эволюционировал в реальном мире, в нем должны быть закодированы дополнительные допущения, благодаря которым он делает выводы очень эффективно. В последние несколько лет мы начали понимать, какими могут быть эти допущения, и встроили их в Alchemy.

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

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

Мир состоит из элементов, а элементы относятся к классам: соеди­нение этих факторов в основном дает нам все, что нужно, чтобы позволить алго­ритму Alchemy делать выводы. Мы можем получать имеющиеся в мире логические сети Маркова, разбивая его на элементы и подэлементы так, чтобы взаимодействия в основном происходили между субэлементами одного элемента, а затем будем группировать элементы в классы и подклассы. Если мир — это конструктор лего, его можно разложить на детали, запомнить, как они крепятся, а потом сгруппировать кирпичики по цвету и форме. Если мир — это «Википедия», можно извлечь объекты, о которых она повествует, объединить их в классы и узнать, как эти классы соотносятся друг с другом. Если потом кто-то спросит нас: «Арнольд Шварценеггер — звезда боевиков?» — мы ответим: «Да», потому что он кинозвезда и играет в боевиках. Шаг за шагом мы можем получать все большие логические сети Маркова, пока не дойдем до того, что один мой друг — сотрудник Google — называет «машинным обучением в планетарном масштабе»: моделированием всего в мире сразу, когда данные текут, а ответы вытекают непрерывным потоком.

Конечно, для обучения в таком масштабе нужно намного больше, чем простое внедрение алгоритмов, которые мы уже видели. Во-первых, в какой-то момент одного процессора станет мало: обучение придется распределить по многим серверам. Ученые, работающие в промышленности и в научных учреждениях, интенсивно исследуют, как, например, выполнять градиентный спуск, используя параллельно много компьютеров. Один из вариантов — разделить данные между процессорами, другой — разделить параметры модели. После каждого этапа результаты соединяются и работа перераспределяется. Так или иначе сделать это, не жертвуя качеством и не давая затратам на коммуникацию между процессорами вас задавить, — далеко не тривиальная задача. Другая проблема заключается в том, что, имея бесконечный поток поступающих данных, нельзя определиться с решением, пока не увидишь их целиком. Выйти из такой ситуации помогает, например, принцип выборочного обследования. Если вы хотите предсказать, кто победит на следующих президентских выборах, не обязательно спрашивать каждого избирателя, за кого он собирается голосовать: пробы из нескольких тысяч человек будет достаточно, если вы готовы смириться с некоторой долей неопределенности. Фокус в том, чтобы обобщить этот подход до сложных моделей с миллионами параметров, но это можно сделать, отбирая на каждом этапе ровно столько примеров из каждого потока, сколько нужно. Вы должны быть достаточно уверены в правильности решения и в том, что общая неопределенность по всем решениям остается в разумных пределах. Таким образом можно эффективно учиться на бесконечном количестве данных в конечное время: об этом я писал в одной из первых статей, предлагающих этот подход.