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

Поэтому уравнение дает нам вероятность изображения (или чего угодно) согласно марковской сети, но оно более общее, потому что это не просто уравнение марковской сети, а уравнение логической сети Маркова — так мы ее назвали. В логической сети Маркова числа в n не обязательно должны быть равны нулю или единице, и они обращаются не к свойствам, а к логическим формулам. В конце главы 8 мы уже увидели, как выйти за пределы сетей Маркова в реляционные модели, определенные в терминах шаблонов свойств, а не просто свойств. «И у Элис, и у Боба грипп» — это свойство, специфичное для Элис и Боба. «И у X, и у Y грипп» — это шаблон свойств, частными случаями которого могут быть Элис и Боб, Элис и Крис и любая другая пара. Шаблон свойств — мощный инструмент, потому что он может суммировать миллиарды свойств в одном коротком выражении. Однако для определения шаблонов свойств нам нужен формальный язык, и он у нас есть: это логика.

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

Теперь вы, вероятно, догадались, что означает n в верховном уравнении: его первый компонент — число истинных случаев первой формулы в данном состоянии, второй — число истинных случаев второй формулы и так далее. Если рассмотреть десять знакомых, семь из которых больны гриппом, первый компонент из n будет равен семи, и так далее. (Не должна ли вероятность измениться, если больны гриппом семь из двадцати, а не десяти знакомых? Да, и она будет отличаться благодаря Z.) Если все веса в этих пределах будут стремиться к бесконечности, марковская логика сведется к стандартной, потому что нарушение хотя бы одного случая формулы вызовет схлопывание вероятности до нуля, делая состояние невозможным. С точки зрения вероятностей логическая сеть Маркова сводится к марковской сети, если все формулы описывают один объект. Итак, и логика, и марковские сети — частные случаи марковской логики, и это то объединение, которое мы искали.

Обучение в логической сети Маркова — открытие формул, которые верны в мире чаще, чем предсказывали бы случайные шансы, а также определение весов для этих формул, благодаря которым их предсказанные вероятности совпадают с наблюдаемыми частотами. Готовую логическую сеть Маркова можно использовать для ответа на такие вопросы, как «Какова вероятность, что у Боба грипп, при условии, что он друг Элис и у нее грипп?» И знаете что? Оказалось, что эта вероятность задана S-образной кривой, приложенной ко взвешенной сумме свойств, во многом как в многослойном перцептроне, а логическая сеть Маркова с длинными цепочками правил может представлять глубокую нейронную сеть с одним слоем на каждое звено цепи.

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

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

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

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

Конечно, даже если пользоваться Alchemy без исходных формул (так тоже можно), это не лишит его знаний: допущения о мире неявно закодированы в выборе формального языка, оценивающей функции и оптимизатора. Поэтому естественно будет спросить: можно ли получить еще более обобщенный алгоритм машинного обучения, чем Alchemy? Какое допущение делала эволюция, начиная долгий путь от первой бактерии ко всем формам жизни, которые мы сегодня видим вокруг? Я думаю, простое допущение, из которого вытекает все остальное, таково: обучающийся алгоритм — часть мира. Это значит, что, какой бы он ни был, как физическая система он соблюдает те же законы, что и среда, в которой он находится, и тем самым уже неявно их «знает» и настроен на их открытие. В следующем разделе мы увидим, что это может означать и как воплотить этот принцип в Alchemy. А пока просто заметим, что это, наверное, лучший ответ, который вообще можно дать на вопрос Юма. С одной стороны, предположение, что алгоритм машинного обучения — часть мира, — это допущение: в принципе обучающийся алгоритм может соблюдать и другие законы, не те, которые соблюдает окружающий мир, поэтому это согласуется с мнением Юма, что обучение возможно только на основе предшествующего знания. С другой стороны, это допущение настолько базовое и с ним так сложно спорить, что, наверное, для этого мира его будет достаточно.