Верховный алгоритм
Наш объединенный обучающийся алгоритм, наверное, лучше всего ввести с помощью аллегории. Если представить себе машинное обучение в виде континента, разделенного на территории пяти «племен», то Верховный алгоритм будет столицей, расположенной в уникальном месте, где сходятся их границы. Вы приближаетесь к городу издалека и видите, что состоит он из трех концентрических, обнесенных стеной колец. Внешний и без сомнения самый широкий круг — это Городок оптимизации. Дома здесь — алгоритмы всех форм и размеров. Одни только строятся, и вокруг них суетятся местные жители, другие сияют свежестью, третьи выглядят старыми и заброшенными. Выше на холме стоит Цитадель оценки. Из ее особняков и дворцов постоянно исходят приказы алгоритмам внизу. На самой вершине в небо взлетает Башня представлений. Здесь живут отцы города. Их непреложные законы определяют, что можно сделать, а чего нельзя, и не только в городе, но и на всем континенте. На вершине центральной, самой высокой башни развевается флаг Верховного алгоритма: красно-черный, с пятиконечной звездой, внутри которой надпись, но вы пока не можете ее разобрать.
Город разделен на пять секторов, по одному для каждого из пяти «племен». Сектора простираются от Башни представлений вниз, к внешним стенам, опоясывающим Башню, группы дворцов в Цитадели оценки и улицы и дома Городка оптимизации, над которой они возвышаются. Пять секторов и три кольца делят город на 15 районов — 15 форм, 15 кусочков мозаики, которую вам надо сложить:
Вы пристально вглядываетесь в карту, пытаясь расшифровать ее секрет. Пятнадцать кусочков довольно точно подходят друг к другу, но вам надо понять, как они соединяются, чтобы получить всего три элемента: представление, оценку и оптимизацию Верховного алгоритма. Каждый обучающийся алгоритм состоит из этих элементов, но они разнятся от «племени» к «племени».
Представления — формальный язык, на котором алгоритм машинного обучения выражает свои модели. Формальный язык символистов — логика, частные случаи которой — правила и деревья решений. Для коннекционистов это нейронные сети. Для эволюционистов — генетические программы, включая системы классификации. Для байесовцев — графические модели, общий термин для байесовских и марковских сетей. Для аналогизаторов — частные случаи, возможно, с весами, как в методе опорных векторов.
Элемент оценки — функция присвоения баллов, которая говорит, насколько хороша модель. Символисты используют точность и информационный выигрыш. Коннекционисты — непрерывное измерение погрешности, например квадрат ошибки, который представляет собой сумму квадратов различий между предсказанными и истинными значениями. Байесовцы применяют апостериорную вероятность, аналогизаторы (как минимум специалисты по методу опорных векторов) — зазор. В дополнение к оценке того, насколько хорошо модель подходит к данным, все «племена» учитывают другие желательные свойства, например простоту модели.
Оптимизация — это алгоритм, который ищет и выдает модель с наивысшей оценкой. Характерный поисковый алгоритм символистов — обратная дедукция. Коннекционистов — градиентный спуск. Эволюционистов — генетический поиск, включая кроссинговер и мутации. Байесовцы в этом отношении необычны: они не просто ищут лучшую модель, но и усредняют по всем моделям, взвешивая их вероятность. Для эффективного взвешивания они пользуются алгоритмами вероятностного вывода, например MCMC. Аналогизаторы (или, точнее, адепты метода опорных векторов) используют условную оптимизацию для нахождения лучшей модели.
У вас за плечами многодневный путь, солнце начинает быстро клониться к горизонту, и надо поторопиться, пока не стемнело. Во внешней стене пять массивных ворот, каждые под охраной своего «племени», и ведут они в соответствующие районы Городка оптимизации. Давайте пройдем через Ворота градиентного спуска, шепнув стражнику пароль — «глубокое обучение», — и начнем по спирали подниматься к Башням представления. Улицы уходят круто вверх по склону холма к Воротам квадратичной ошибки, ведущим в цитадель, но вы сворачиваете влево, к эволюционистскому сектору. Дома в районе градиентного спуска — это гладкие кривые и густо переплетенные паттерны, напоминающие скорее джунгли, а не город. Но когда градиентный спуск уступает место генетическому поиску, картина резко меняется. Дома здесь выше, структура громоздится на структуру, но сами структуры незаполненные, почти пустые. Они как будто ждут, что в них придут кривые градиентного спуска. Вот он, способ их соединить: надо использовать генетический поиск, чтобы найти структуру модели, а потом позволить градиентному спуску заполнить ее параметры. Именно так поступает природа: эволюция создает структуры головного мозга, а индивидуальный опыт моделирует их.
Первый шаг сделан, и вы спешите в байесовский район. Даже на расстоянии видно, как он лепится к Кафедральному собору теоремы Байеса. Переулок MCMC делает случайные зигзаги. Чтобы не терять времени, вы срезаете путь и выходите на улицу Распространения степени уверенности, но она, похоже, образует бесконечную петлю. И тут вы видите то, что надо: широкий бульвар Наибольшего правдоподобия, ведущий вверх, к воротам Апостериорной вероятности. Вместо того чтобы усреднять все модели, можно направиться прямиком к самой вероятной, с уверенностью, что в итоге прогнозы будут почти такими же. Генетическому поиску можно позволить подобрать структуру модели, а градиентному спуску — ее параметры. Со вздохом облегчения вы понимаете, что это весь вероятностный вывод, который вам нужен, по крайней мере, пока не придет время с помощью модели отвечать на вопросы.
Вы продолжаете свой путь. Район условной оптимизации напоминает лабиринт узких улочек и тупиков. Повсюду плечом к плечу стоят примеры всех сортов, периодически уступая место опорному вектору. Очевидно: чтобы не врезаться в примеры неправильного класса, нужно просто добавить ограничения в уже собранный оптимизатор. Но если подумать, делать это совсем не обязательно. При обучении методу опорных векторов обычно разрешается нарушать зазоры, чтобы избежать переобучения, при условии, что каждое нарушение штрафуется. В этом случае веса оптимальных примеров можно снова получить с помощью одной из форм градиентного спуска. Это было несложно, и вы чувствуете, что начинаете набивать руку.
Плотные ряды частных случаев резко обрываются, и вы попадаете в район Обратной дедукции. Вокруг широкие аллеи и старинные каменные здания. Архитектура здесь геометрическая, строгая, состоящая из прямых линий и прямых углов. Квадратные даже стволы у сильно обрезанных деревьев, а их листья тщательно подписаны предсказаниями класса. Обитатели этого района, видимо, строят свои дома особым образом: они начинают с крыши, которую называют выводами, и постепенно заполняют пустые места между крышей и землей — предпосылками, на их языке. Один за другим они находят каменные блоки, которые хорошо подойдут для заполнения пробелов, и поднимают их на место. Вы замечаете, что форма многих пробелов одинакова, и работа пойдет быстрее, если обрезать и складывать блоки, подгоняя их, а потом повторять процесс столько раз, сколько нужно. Другими словами, для обратной дедукции можно использовать генетический поиск. Прекрасно. Кажется, вы свели все пять оптимизаторов к простому рецепту: генетический поиск структуры и градиентный спуск для параметров. И даже это может быть лишним. Во многих проблемах генетический поиск можно свести к восхождению на выпуклые поверхности, если выполнить три условия: не включать кроссинговер, пробовать в каждом поколении все возможные точечные мутации и всегда выбирать одну лучшую гипотезу, чтобы «заразить» ею следующее поколение.
А что это за статуя впереди? Это Аристотель, который неодобрительно взирает на переплетение и хаос квартала градиентного спуска. Круг замкнулся. У вас есть объединенный оптимизатор, необходимый для Верховного алгоритма, но сейчас не время для поздравлений. Опустилась ночь, а сделать предстоит еще очень много. Вы идете в Цитадель оценки через впечатляющие, но довольно узкие Ворота точности. Надпись над ними гласит: «Оставь надежды на переобучение, всяк сюда входящий». Огибая дворцы алгоритмов оценки всех пяти «племен», вы мысленно ставите кусочки на место. Точность вы станете использовать для оценки предсказаний типа «да или нет», квадратичную ошибку — для непрерывных предсказаний. Приспособленность — просто эволюционистское название функции подсчета очков: ее можно сделать какой вздумается, в том числе точностью и квадратом ошибки. Апостериорная вероятность уменьшает квадрат ошибки, если проигнорировать априорную вероятность и если ошибки следуют нормальному распределению. Зазор, если разрешить нарушать его за определенную цену, становится более мягкой версией точности: вместо того чтобы платить нулевой штраф за правильное предсказание и единицу за каждое неправильное предсказание, штраф будет нулевым, пока вы не попадаете в зазор, а потом он начинает расти. Готово! Сложить алгоритмы оценки оказалось намного проще, чем объединить оптимизаторы. Но над вами нависли Башни представления, и они наполняют вас дурными предчувствиями.
Вы дошли до последнего этапа поисков и стучитесь в дверь Башни опорных векторов. Вам открывает грозного вида стражник, и тут вы понимаете, что не знаете пароль. «Ядро!» — выпаливаете вы, пытаясь не выдать испуг. Страж кланяется и уступает дорогу. Собравшись с духом, вы входите внутрь, тихо браня себя за беспечность. Весь первый этаж башни занимают щедро обставленные округлые покои, а в центре на почетном месте стоит нечто напоминающее мраморное представление метода опорных векторов. Осматривая комнату, вы замечаете где-то сбоку дверь. Она должна вести в центральную башню — Башню Верховного алгоритма. Похоже, дверь не охраняют, и вы решаете срезать путь. Проскользнув через дверной проем и пройдя по короткому коридору, вы оказываетесь в еще большем пятиугольном помещении с дверью в каждой стене. В центре куда-то ввысь уходит винтовая лестница. Оттуда доносятся голоса, и вы ныряете в дверь напротив. Она ведет в Башню нейронных сетей. Вы снова оказываетесь в округлом помещении, в центре которого на этот раз стоит многослойный перцептрон. Его элементы отличаются от метода опорных векторов, но их расположение замечательно схоже. Вдруг вас осеняет: метод опорных векторов — это же просто многослойный перцептрон, но скрытый слой состоит из ядер, а не из сигмоид, а выходной слой — не еще одна S-кривая, а линейная комбинация.
Может быть, другие представления тоже имеют схожую форму? С растущим возбуждением вы бежите обратно в пятиугольную комнату, а оттуда — в Башню логики. Глядя на стоящее в центре изображение набора правил, вы пытаетесь увидеть схему. Есть! Каждое правило — это просто очень сильно стилизованный нейрон. Например, правило «Если это гигантская рептилия и она дышит огнем — это дракон» — это просто перцептрон с весами один для «это гигантская рептилия» и «дышать огнем» и порогом 1,5. А набор правил — многослойный перцептрон со скрытым слоем, содержащий один нейрон для каждого правила и выходящий нейрон для дизъюнкции этих правил. Где-то в глубине души вас гложут сомнения, но сейчас думать о них некогда. Вы бежите через пятиугольную комнату в Башню генетических программ и уже видите, как поставить их в строй. Генетические программы — это просто программы, а программа — это просто логический конструкт. Скульптура генетической программы в комнате имеет форму дерева, подпрограммы ветвятся на еще большее количество подпрограмм, и, присматриваясь к листьям, вы замечаете, что это всего лишь правила. Итак, программы сводятся к правилам, а если правила можно свести к нейронам, значит, можно и программы.
Вперед, в Башню графических моделей! К сожалению, скульптура в круглой комнате оказывается совершенно не похожей на остальные. Графическая модель — это продукт факторов: условных вероятностей, в случае байесовских сетей, и неотрицательных функций состояния — в случае сетей Маркова. Как вы ни стараетесь, уловить связь с нейронными сетями и наборами правил не получается. Вас на секунду охватывает разочарование, но вы надеваете свои лого-очки, которые превращают функции в логарифмы. Эврика! Произведение факторов стало суммой условий, прямо как метод опорных векторов, голосующий набор правил и многослойный перцептрон без S-образной кривой на выходе. Например, можно превратить наивный байесовский классификатор дракона в перцептрон, вес которого для «дышит огнем» будет разностью логарифмов P(дышит огнем | дракон) и P(дышит огнем | не дракон). Но, конечно, графические модели намного более обобщенные, потому что могут представлять вероятностные распределения по многим переменным, а не только распределение одной переменной (класс) при известных других (атрибутах).
Получилось! Или нет? Внедрить метод опорных векторов в нейронные сети и нейронные сети в графические модели можно. То же касается объединения генетических программ и логики. Но как соединить логику и графические модели? Что-то здесь не так. С запозданием вы видите, в чем проблема: у логики есть измерение, которого не хватает графическим моделям, и наоборот. Скульптуры в пяти комнатах подходили друг к другу, потому что это были простые аллегории, но в реальности все сложнее. Графические модели не позволяют представить правила, включающие больше одного объекта, например «Друзья друзей — тоже друзья». Все их переменные должны быть свойствами того же предмета. Еще они не могут представлять произвольные программы, которые передают наборы переменных из одной подпрограммы в другую. Логика умеет делать и то и другое, но она, в свою очередь, не может представлять неопределенность, двузначность и степени схожести. Без представления, которое может делать все это, универсального обучающего алгоритма не получишь.
Вы напрягаете извилины в поисках решения, но чем больше стараетесь, тем хуже выходит. Может быть, объединение логики и вероятностей неподвластно человеку? Усталость подкашивает вас и погружает в сон. Просыпаетесь вы от грозного рыка: на вас набросился похожий на гидру Монстр Сложности. Он щелкает зубами, но в последний момент вы уворачиваетесь и отчаянно рубите чудовище мечом обучения — только им можно его победить — и отрубаете все его головы. Пока не отросли новые, вы бросаетесь к лестнице.
Запыхавшись, вы взбираетесь на самый верх и видите свадебный обряд. Предиктус, Первый лорд Логики, повелитель Символического королевства и Защитник программ, говорит Марковии, Княжне вероятностей и Царице сетей: «Объединим же наши владения! В мои правила добавишь ты веса, и породим мы новые представления, которые умножатся и заселят землю». Княжна добавляет: «А потомство наше мы назовем Марковскими логическими сетями».
У вас кружится голова. Вы выходите на балкон. Над городскими крышами уже взошло солнце. Вокруг во всех направлениях простираются леса серверов: они тихо шумят в ожидании Верховного алгоритма. Караваны везут золото из копей, где добывают данные. Далеко на западе на солнце играет море информации, на котором виднеются точки кораблей. Вы поднимаете голову и смотрите на флаг Верховного алгоритма. Теперь надпись внутри пятиконечной звезды четко видна:
P = ew?n / Z.
Что бы это могло значить?