Вспомните, что сеть Маркова, во многом как перцептрон, определяется взвешенной суммой свойств. Представьте, что у вас есть коллекция фотографий людей. Мы случайным образом выбираем одну и вычисляем ее свойства, например «у этого человека седые волосы», «этот человек пожилой», «этот человек женщина» и так далее. В перцептроне мы проводим взвешенную сумму этих свойств через порог, чтобы решить, например, это ваша бабушка или нет. В марковских сетях мы делаем нечто совершенно другое (по крайней мере на первый взгляд): взвешенная сумма возводится в степень, превращается в произведение факторов, и это произведение будет вероятностью выбора конкретно этой картинки из коллекции, независимо от того, есть ли на ней ваша бабушка. Если у вас много картинок с изображениями пожилых людей, взвешенная сумма этого свойства растет. Если большинство из них — мужчины, вес свойства «этот человек — женщина» идет вниз. Свойства могут быть какими угодно, поэтому сети Маркова — замечательно гибкий способ представления вероятностных распределений.
На самом деле я погрешил против истины: произведение факторов — это еще не вероятность, потому что сумма вероятностей всех картинок должна быть равна единице, и нет гарантии, что произведение факторов для всех картинок приведет к такому результату. Нам нужно их нормализовать, то есть разделить каждое произведение на сумму факторов. В таком случае сумма всех нормализованных произведений будет гарантированно равна единице, потому что это просто некое число, разделенное само на себя. Вероятность картинки, таким образом, будет взвешенной суммой ее свойств, возведенной в степень и нормализованной. Если вы вспомните уравнение в пятиконечной звезде, то, наверное, начнете догадываться, что оно означает. P — это вероятность, w — вектор весов (будем обозначать вектора жирным шрифтом), n — вектор чисел, а их скалярное произведение · возводится в степень и делится на Z, сумму всех произведений. Если первый компонент n равен единице, когда первое свойство изображения верно, и нулю в противном случае и так далее, то w·n — это просто сокращение для взвешенной суммы черт, о которой мы постоянно говорили.
Поэтому уравнение дает нам вероятность изображения (или чего угодно) согласно марковской сети, но оно более общее, потому что это не просто уравнение марковской сети, а уравнение логической сети Маркова — так мы ее назвали. В логической сети Маркова числа в n не обязательно должны быть равны нулю или единице, и они обращаются не к свойствам, а к логическим формулам. В конце главы 8 мы уже увидели, как выйти за пределы сетей Маркова в реляционные модели, определенные в терминах шаблонов свойств, а не просто свойств. «И у Элис, и у Боба грипп» — это свойство, специфичное для Элис и Боба. «И у X, и у Y грипп» — это шаблон свойств, частными случаями которого могут быть Элис и Боб, Элис и Крис и любая другая пара. Шаблон свойств — мощный инструмент, потому что он может суммировать миллиарды свойств в одном коротком выражении. Однако для определения шаблонов свойств нам нужен формальный язык, и он у нас есть: это логика.
Логическая сеть Маркова — просто набор логических формул и их весов. В приложении к конкретному набору объектов он определяет марковскую сеть их возможных состояний. Например, если объекты — Элис и Боб, возможным состоянием будет то, что Элис и Боб — друзья, у Элис грипп и у Боба тоже. Давайте предположим, что у логической сети Маркова две формулы: «у всех грипп» и «если у человека грипп, у его друзей тоже грипп». В стандартной логике это была бы довольно бесполезная пара утверждений: первое исключало бы все состояния, где хотя бы один человек здоров, а второе было бы избыточным. Однако в логической сети Маркова первая формула означает только то, что для каждого человека X есть свойство «X болен гриппом» с тем же весом, что и формула. Если люди с большой вероятностью болеют гриппом, и у формулы, и у соответствующих свойств будет большой вес. Состояние, где здоровых людей много, менее вероятно, чем то, где таких людей мало, однако оно не исключено. А благодаря второй формуле состояние, при котором у кого-то грипп, а у его друзей — нет, будет менее вероятно, чем то, где здоровые и зараженные попадают в отдельные кластеры друзей.
Теперь вы, вероятно, догадались, что означает n в верховном уравнении: его первый компонент — число истинных случаев первой формулы в данном состоянии, второй — число истинных случаев второй формулы и так далее. Если рассмотреть десять знакомых, семь из которых больны гриппом, первый компонент из n будет равен семи, и так далее. (Не должна ли вероятность измениться, если больны гриппом семь из двадцати, а не десяти знакомых? Да, и она будет отличаться благодаря Z.) Если все веса в этих пределах будут стремиться к бесконечности, марковская логика сведется к стандартной, потому что нарушение хотя бы одного случая формулы вызовет схлопывание вероятности до нуля, делая состояние невозможным. С точки зрения вероятностей логическая сеть Маркова сводится к марковской сети, если все формулы описывают один объект. Итак, и логика, и марковские сети — частные случаи марковской логики, и это то объединение, которое мы искали.
Обучение в логической сети Маркова — открытие формул, которые верны в мире чаще, чем предсказывали бы случайные шансы, а также определение весов для этих формул, благодаря которым их предсказанные вероятности совпадают с наблюдаемыми частотами. Готовую логическую сеть Маркова можно использовать для ответа на такие вопросы, как «Какова вероятность, что у Боба грипп, при условии, что он друг Элис и у нее грипп?» И знаете что? Оказалось, что эта вероятность задана S-образной кривой, приложенной ко взвешенной сумме свойств, во многом как в многослойном перцептроне, а логическая сеть Маркова с длинными цепочками правил может представлять глубокую нейронную сеть с одним слоем на каждое звено цепи.
Конечно, не стоит верить прогнозам распространения гриппа, сделанным описанной выше простой логической сетью Маркова. Вместо этого представьте себе логическую сеть Маркова для диагностики и лечения рака. Такая сеть будет представлять распределение вероятностей состояний клетки. Каждый элемент клетки, каждая органелла, каждый метаболический путь, каждый ген и белок — это объект сети, а формулы логической сети Маркова кодируют зависимости между ними. Можно спросить сеть: «Эта клетка — раковая?» — проверить ее разными лекарствами и посмотреть, что произойдет. Пока у нас нет таких сетей, но ниже в этой главе я опишу, как их получить.
Подытожим: единый алгоритм машинного обучения, к которому мы пришли, в качестве представления использует логическую сеть Маркова, как функцию оценки — апостериорную вероятность, а оптимизатор в нем — генетический поиск в сочетании с градиентным спуском. При желании можно легко заменить апостериорную вероятность каким-то более точным измерением, а генетический поиск — восхождением на выпуклые поверхности. Мы достигли вершины и можем наслаждаться видами. Однако я бы не торопился называть такой алгоритм Верховным. Во-первых, критерий истины — практика, и, хотя за последнее десятилетие этот алгоритм (или его разновидности) успешно применяли во многих сферах, есть намного больше областей, в которых он не применялся, поэтому пока не ясно, насколько он универсален. Во-вторых, ряд важных проблем он не решает. Но перед тем, как ими заняться, давайте посмотрим, на что он способен.
От Юма до домашних роботов
Скачать обучающийся алгоритм, который я только что описал, можно на сайте alchemy.cs.washington.edu. Мы окрестили его Alchemy, чтобы напомнить самим себе, что, несмотря на все свои успехи, наука
