Верховный алгоритм: как машинное обучение изменит наш мир Домингос Педро
Эту похожую на вытянутую букву S кривую называют по-разному: логистической, S-образной, сигмоидой. Присмотритесь к ней повнимательнее, потому что это самая важная кривая в мире. Сначала выход медленно растет вместе с входом: так медленно, что кажется постоянным. Затем он начинает меняться быстрее, потом очень быстро, а после все медленнее и медленнее и наконец вновь становится почти постоянным. Кривая транзистора, которая связывает входящее и выходящее напряжение, тоже S-образна, поэтому и компьютеры, и головной мозг наполнены S-кривыми. Но это еще не все. Форму сигмоиды имеют всевозможные фазовые переходы: вероятность, что электрон сменит спин в зависимости от приложенного поля, намагничивание железа, запись бита памяти на твердый диск, открытие ионного канала в клетке, таяние льда, испарение воды, инфляционное расширение молодой Вселенной, прерывистое равновесие в эволюции, смена научных парадигм, распространение новых технологий, бегство белого населения из смешанных районов, слухи, эпидемии, революции, падения империй и многое другое. Книгу The Tipping Point: How Little Things Can Make a Big Difference[64] можно было бы (хотя и менее заманчиво) назвать «Сигмоида». Землетрясение — это фазовый переход в относительном положении двух прилегающих тектонических плит, а стук, который мы иногда слышим ночью, — просто сдвиг микроскопических «тектонических плит» в стенах дома, так что не пугайтесь. Йозеф Шумпетер[65] говорил, что экономика развивается трещинами и скачками: творческое разрушение тоже имеет S-образную форму. Финансовые приобретения и потери тоже воздействуют на человеческое счастье по сигмоиде, поэтому не стоит излишне надрываться и переживать. Вероятность, что произвольная логическая формула будет выполнимой — самая суть NP-полных проблем, — следует фазовому переходу от почти единицы к почти нулю по мере увеличения длины формулы. Статистические физики могут изучать фазовые переходы всю жизнь.
В романе Хемингуэя «И восходит солнце» Майка Кэмпбелла спрашивают, как он обанкротился, и тот отвечает: «Двумя способами. Сначала постепенно, а потом сразу». То же самое могли бы сказать в банке Lehman Brothers. В этом суть сигмоиды. Одно из правил прогнозирования, сформулированных футуристом Полом Саффо, гласит: ищите S-образные кривые. Если не получается «поймать» комфортную температуру в душе — вода сначала слишком холодная, а потом сразу слишком горячая, — вините S-кривую. Развитие по S-образной кривой хорошо видно, когда готовишь воздушную кукурузу: сначала ничего не происходит, затем лопается несколько зерен, потом сразу много, потом почти все взрываются фейерверком, потом еще немного — и можно есть. Движения мышц тоже следуют сигмоиде: медленно, быстро и опять медленно: мультфильмы стали гораздо естественнее, когда диснеевские мультипликаторы поняли это и начали имитировать. По S-кривой движутся глаза, фиксируясь вместе с сознанием то на одном, то на другом предмете. Согласно фазовому переходу меняется настроение. То же самое с рождением, половым созреванием, влюбленностью, браком, беременностью, поступлением на работу и увольнением, переездом в другой город, повышением по службе, выходом на пенсию и смертью. Вселенная — огромная симфония фазовых переходов, от космических до микроскопических, от самых обыденных до меняющих нашу жизнь.
Сигмоида важна не просто как модель. В математике она трудится не покладая рук. Если приблизить ее центральный отрезок, он будет близок прямой. Многие явления, которые мы считаем линейными, на самом деле представляют собой S-образные кривые, потому что ничто не может расти бесконечно. В силу относительности и вопреки Ньютону ускорение не увеличивается линейно с увеличением силы, а следует по сигмоиде, центрированной на нуле. Аналогичная картина наблюдается с зависимостью электрического тока от напряжения в резисторах электрических цепей и в лампочках (пока нить не расплавится, что само по себе очередной фазовый переход). Если посмотреть на S-образную кривую издалека, она будет напоминать ступенчатую функцию, в которой выход в пороговом значении внезапно меняется с нуля до единицы. Поэтому, в зависимости от входящего напряжения, работу транзистора в цифровых компьютерах и аналоговых устройствах, например усилителях и тюнерах, будет описывать та же самая кривая. Начальный отрезок сигмоиды по существу экспоненциальный, а рядом с точкой насыщения она приближается к затуханию по экспоненте. Когда кто-то говорит об экспоненциальном росте, спросите себя: как скоро он перейдет в S-образную кривую? Когда замедлится взрывной рост населения, закон Мура исчерпает свои возможности, а сингулярность так и не наступит? Дифференцируйте сигмоиду, и вы получите гауссову кривую: «медленно — быстро — медленно» превратится в «низко — высоко — низко». Добавьте последовательность ступенчатых S-образных кривых, идущих то вверх, то вниз, и получится что-то близкое к синусоиде. На самом деле каждую функцию можно близко аппроксимировать суммой S-образных кривых: когда функция идет вверх, вы добавляете сигмоиду, когда вниз — отнимаете. Обучение ребенка — это не постепенное улучшение, а накопление S-образных кривых. Это относится и к технологическим изменениям. Взгляните на Нью-Йорк издали, и вы увидите, как вдоль горизонта разворачивается совокупность сигмоид, острых, как углы небоскребов.
Для нас самое главное то, что S-образные кривые ведут к новому решению проблемы коэффициентов доверия. Раз Вселенная — это симфония фазовых переходов, давайте смоделируем ее с помощью фазового перехода. Именно так поступает головной мозг: подстраивает систему фазовых переходов внутри к аналогичной системе снаружи. Итак, давайте заменим ступенчатую функцию перцептрона сигмоидой и посмотрим, что произойдет.
Альпинизм в гиперпространстве
В алгоритме перцептрона сигнал ошибки действует по принципу «все или ничего»: либо правильно, либо неправильно. Негусто, особенно в случае сетей из многих нейронов. Можно понять, что ошибся нейрон на выходе (ой, это была не ваша бабушка?), но как насчет какого-то нейрона в глубинах мозга? И вообще, что значат правота и ошибка для глубинного нейрона? Однако если выход нейрона непрерывный, а не бинарный, картина меняется. Прежде всего мы можем оценить, насколько ошибается выходной нейрон, по разнице между получаемым и желаемым выходом. Если нейрон должен искрить активностью («Ой, бабушка! Привет!») и он немного активен, это лучше, чем если бы он не срабатывал вовсе. Еще важнее то, что теперь можно распространить эту ошибку на скрытые нейроны: если выходной нейрон должен быть активнее и с ним связан нейрон A, то чем более активен нейрон A, тем больше мы должны усилить соединение между ними. Если A подавляется нейроном B, то B должен быть менее активным и так далее. Благодаря обратной связи от всех нейронов, с которыми он связан, каждый нейрон решает, насколько больше или меньше надо активироваться. Это, а также активность его собственных входных нейронов диктует ему, усиливать или ослаблять соединения с ними. Мне надо быть активнее, а нейрон B меня подавляет? Значит, его вес надо снизить. А нейрон C очень активен, но его соединение со мной слабое? Усилим его. В следующем раунде нейроны-«клиенты», расположенные дальше в сети, подскажут, насколько хорошо я справился с задачей.
Всякий раз, когда «сетчатка» обучающегося алгоритма видит новый образ, сигнал распространяется по всей сети, пока не даст выход. Сравнение полученного выхода с желаемым выдает сигнал ошибки, который затем распространяется обратно через все слои и достигает сетчатки. На основе возвращающегося сигнала и вводных, полученных во время прохождения вперед, каждый нейрон корректирует веса. По мере того как сеть видит все новые и новые изображения вашей бабушки и других людей, веса постепенно сходятся со значениями, которые позволяют отличить одно от другого. Метод обратного распространения ошибки, как называется этот алгоритм, несравнимо мощнее перцептрона. Единичный нейрон может найти только прямую линию, а так называемый многослойный перцептрон — произвольно запутанные границы, при условии что у него есть достаточно скрытых нейронов. Это делает обратное распространение ошибки верховным алгоритмом коннекционистов.
Обратное распространение — частный случай стратегии, очень распространенной в природе и в технологии: если вам надо быстро забраться на гору, выбирайте самый крутой склон, который только найдете. Технический термин для этого явления — «градиентное восхождение» (если вы хотите попасть на вершину) или «градиентный спуск» (если смотреть на долину внизу). Бактерии умеют искать пищу, перемещаясь согласно градиенту концентрации, скажем, глюкозы, и убегать от ядов, двигаясь против их градиента. С помощью градиентного спуска можно оптимизировать массу вещей, от крыльев самолетов до антенных систем. Обратное распространение — эффективный способ такой оптимизации в многослойном перцептроне: продолжайте корректировать веса, чтобы снизить возможность ошибки, и остановитесь, когда станет очевидно, что корректировки ничего не дают. В случае обратного распространения не надо разбираться, как с нуля корректировать вес каждого нейрона (это было бы слишком медленно): это можно делать слой за слоем, настраивая каждый нейрон на основе уже настроенных, с которыми он соединен. Если в чрезвычайной ситуации вам придется выбросить весь инструментарий машинного обучения и спасти что-то одно, вы, вероятно, решите спасти градиентный спуск.
Так как же обратное распространение решает проблему машинного обучения? Может быть, надо просто собрать кучу нейронов, подождать, пока они наколдуют все, что надо, а потом по дороге в банк заехать получить Нобелевскую премию за открытие принципа работы мозга? К сожалению, в жизни все не так просто. Представьте, что у вашей сети только один вес; зависимость ошибки от него показана на этом графике:
Оптимальный вес, в котором ошибка самая низкая, — это 2,0. Если сеть начнет работу, например, с 0,75, обратное распространение ошибки за несколько шагов придет к оптимуму, как катящийся с горки мячик. Однако если начать с 5,5, мы скатимся к весу 7,0 и застрянем там. Обратное распространение ошибки со своими поэтапными изменениями весов не сможет найти глобальный минимум ошибки, а локальные минимумы могут быть сколь угодно плохими: например, бабушку можно перепутать со шляпой. Если вес всего один, можно перепробовать все возможные значения c шагом 0,01 и таким образом найти оптимум. Но когда весов тысячи, не говоря уже о миллионах или миллиардах, это не вариант, потому что число точек на сетке будет увеличиваться экспоненциально с числом весов. Глобальный минимум окажется скрыт где-то в бездонных глубинах гиперпространства — ищи иголку в стоге сена.
Представьте, что вас похитили, завязали глаза и бросили где-то в Гималаях. Голова раскалывается, с памятью не очень, но вы твердо знаете, что надо забраться на вершину Эвереста. Как быть? Вы делаете шаг вперед и едва не скатываетесь в ущелье. Переведя дух, вы решаете действовать систематичнее и осторожно ощупываете ногой почву вокруг, чтобы определить самую высокую точку. Затем вы робко шагаете к ней, и все повторяется. Понемногу вы забираетесь все выше и выше. Через какое-то время любой шаг начинает вести вниз, и вы останавливаетесь. Это градиентное восхождение. Если бы в Гималаях существовал один Эверест, причем идеальной конической формы, все было бы прекрасно. Но, скорее всего, место, где все шаги ведут вниз, будет все еще очень далеко от вершины: вы просто застрянете на каком-нибудь холме у подножья. Именно это происходит с обратным распространением ошибки, только на горы оно взбирается в гиперпространстве, а не в трехмерном пространстве, как наше. Если ваша сеть состоит из одного нейрона и вы будете шаг за шагом подниматься к наилучшим весам, то придете к вершине. Но в многослойном перцептроне ландшафт очень изрезанный — поди найди высочайший пик.
Отчасти поэтому Минский, Пейперт и другие исследователи не понимали, как можно обучать многослойные перцептроны. Они могли представить себе замену ступенчатых функций S-образными кривыми и градиентный спуск, но затем сталкивались с проблемой локальных минимумов ошибки. В то время ученые не доверяли компьютерным симуляциям и требовали математических доказательств работоспособности алгоритма, а для обратного распространения ошибки такого доказательства не было. Но, как мы уже видели, в большинстве случаев локального минимума достаточно. Поверхность ошибки часто похожа на дикобраза: много крутых пиков и впадин, и на самом деле неважно, найдем ли мы самую глубокую, абсолютную впадину — сойдет любая. Еще лучше то, что локальный минимум бывает даже предпочтительнее, потому что он меньше подвержен переобучению, чем глобальный.
Гиперпространство — обоюдоострый меч. С одной стороны, чем больше количество измерений, тем больше места для очень сложных поверхностей и локальных экстремумов. С другой стороны, чтобы застрять в локальном экстремуме, надо застрять во всех измерениях, а во многих одновременно застрять сложнее, чем в трех. В гиперпространстве есть перевалы, проходящие через всю (гипер)местность, поэтому с небольшой помощью со стороны человека обратное распространение ошибки зачастую способно найти путь к идеально хорошему набору весов. Может быть, это не уровень моря, а только легендарная долина Шангри-Ла, но на что жаловаться, если в гиперпространстве миллионы таких долин и к каждой ведут миллиарды перевалов?
Тем не менее придавать слишком большое значение весам, которые находит обратное распространение ошибки, не стоит. Помните, что есть, вероятно, много очень разных, но одинаково хороших вариантов. Обучение многослойного перцептрона хаотично в том смысле, что, начав из слегка отличающихся мест, он может привести к весьма различным решениям. Этот феномен проявляется в случае незначительных отличий как в исходных весах, так и в обучающих данных и имеет место во всех мощных обучающихся алгоритмах, а не только в обратном распространении ошибки.
Мы могли бы избавиться от проблемы локальных экстремумов, убрав наши сигмоиды и позволив каждому нейрону просто выдавать взвешенную сумму своих входов. Поверхность ошибки стала бы в этом случае очень гладкой, и остался бы всего один минимум — глобальный. Дело, однако, в том, что линейная функция линейных функций — по-прежнему линейная функция, поэтому сеть линейных нейронов ничем не лучше, чем единичный нейрон. Линейный мозг, каким бы большим он ни был, будет глупее червяка. S-образные кривые — просто хороший перевалочный пункт между глупостью линейных функций и сложностью ступенчатых функций.
Перцептроны наносят ответный удар
Метод обратного распространения ошибки был изобретен в 1986 году Дэвидом Румельхартом, психологом из Калифорнийского университета в Сан-Диего, в сотрудничестве с Джеффом Хинтоном и Рональдом Уильямсом[66]. Они доказали, кроме всего прочего, что обратное распространение способно справиться с исключающим ИЛИ, и тем самым дали коннекционистам возможность показать язык Минскому и Пейперту. Вспомните пример с кроссовками Nike: подростки и женщины среднего возраста — их наиболее вероятные покупатели. Это можно представить с помощью сети из трех нейронов: один срабатывает, когда видит подростка, другой — женщину среднего возраста, а третий — когда активизируются оба. Благодаря обратному распространению ошибки можно узнать соответствующие веса и получить успешный детектор предполагаемых покупателей Nike. (Вот так-то, Марвин.)
В первых демонстрациях мощи обратного распространения Терри Сейновски и Чарльз Розенберг обучали многослойный перцептрон читать вслух. Их система NETtalk сканировала текст, подбирала фонемы согласно контексту и передавала их в синтезатор речи. NETtalk не только делал правильные обобщения для новых слов, чего не умели системы, основанные на знаниях, но и научился говорить очень похоже на человека. Сейновски любил очаровывать публику на научных мероприятиях, пуская запись обучения NETtalk: сначала лепет, затем что-то более внятное и наконец вполне гладкая речь с отдельными ошибками. (Поищите примеры на YouTube по запросу sejnowski nettalk.)
Первым большим успехом нейронных сетей стало прогнозирование на фондовой бирже. Поскольку сети умеют выявлять маленькие нелинейности в очень зашумленных данных, они приобрели популярность и вытеснили распространенные в финансах линейные модели. Типичный инвестиционный фонд тренирует сети для каждой из многочисленных ценных бумаг, затем позволяет выбрать самые многообещающие, после чего люди-аналитики решают, в какую из них инвестировать. Однако ряд фондов пошел до конца и разрешил алгоритмам машинного обучения осуществлять покупки и продажи самостоятельно. Сколько именно из них преуспело — тайна за семью печатями, но, поскольку специалисты по обучающимся алгоритмам в устрашающем темпе исчезают в недрах хеджевых фондов, вероятно, в этом что-то есть.
Нелинейные модели важны далеко не только на фондовой бирже. Ученые повсеместно используют линейную регрессию, потому что хорошо ее знают, но изучаемые явления чаще нелинейные, и многослойный перцептрон умеет их моделировать. Линейные модели не видят фазовых переходов, а нейронные сети впитывают их как губка.
Другим заметным успехом ранних нейронных сетей стало обучение вождению машины. Беспилотные автомобили впервые привлекли всеобщее внимание на соревнованиях DARPA Grand Challenge[67] в 2004-м и 2005 годах, но за десять с лишним лет до этого ученые Университета Карнеги–Меллон успешно обучили многослойный перцептрон водить машину: узнавать дорогу на видео и поворачивать руль в нужном месте. С небольшой помощью человека — второго пилота — этот автомобиль сумел проехать через все Соединенные Штаты от океана до океана, хотя «зрение» у него было очень мутное (30 32 пикселя), а мозг меньше, чем у червяка. (Проект назвали No Hands Across America.) Может быть, это не была первая по-настоящему беспилотная машина, но даже она выгодно отличалась от большинства подростков за рулем.
У метода обратного распространения ошибки несметное количество применений. По мере того как росла его слава, становилось все больше известно о его истории. Оказалось, что, как это часто бывает в науке, метод изобретали несколько раз: французский информатик Ян Лекун и другие ученые наткнулись на него примерно в то же время, что и Румельхарт. Еще в 1980-е годы сообщение о методе обратного распространения отклонили на ведущей конференции по проблемам искусственного интеллекта, потому что, по мнению рецензентов, Минский и Пейперт доказали, что перцептроны не работают. Вообще говоря, Румельхарт считается изобретателем метода скорее по «тесту Колумба»: Колумб не был первым человеком, который открыл Америку, но он был последним. Оказалось, что Пол Вербос, аспирант Гарвардского университета, предложил схожий алгоритм в своей диссертации в 1974 году, а самая большая ирония в том, что Артур Брайсон и Хэ Юци, специалисты по теории управления, добились этого в 1969 году — именно когда Минский и Пейперт публиковали свою книгу Perceptrons! Так что сама история машинного обучения показывает, зачем нам нужны обучающиеся алгоритмы: если бы алгоритмы автоматически выявили, что статьи по теме есть в научной литературе с 1969 года, мы бы не потратили впустую десятилетия, и кто знает, какие открытия были бы сделаны быстрее.
В истории перцептрона много иронии, но печально то, что Фрэнк Розенблатт так и не увидел второго акта своего творения: он утонул в Чесапикском заливе в том же 1969 году.
Полная модель клетки
Живая клетка — прекрасный пример нелинейной системы. Она выполняет все свои функции благодаря сложной сети химических реакций, превращающих сырье в конечные продукты. Как мы видели в предыдущей главе, структуру этой сети можно открыть символистскими методами, например обратной дедукцией, но для построения полной модели работы клетки нужен количественный подход: надо узнать параметры, которые связывают уровень экспрессии различных генов, соотносят переменные окружающей среды с внутренними переменными и так далее. Это непросто, потому что между этими величинами нет простой линейной зависимости. Свою стабильность клетка скорее поддерживает благодаря пересекающимся петлям обратной связи, и ее поведение очень сложно. Для решения этой проблемы хорошо подходит метод обратного распространения ошибки, который способен эффективно учиться нелинейным функциям. Если бы у нас в руках была полная карта метаболических цепочек и мы располагали достаточными данными наблюдений за всеми соответствующими переменными, обратное распространение теоретически могло бы получить подробную модель клетки и многослойный перцетрон предсказывал бы любую переменную как функцию ее непосредственных причин.
Однако в обозримом будущем у нас будет только частичное понимание клеточного метаболизма и мы сможем наблюдать лишь долю нужных параметров. Для получения полезных моделей в условиях недостатка информации и неизбежных противоречий нужны байесовские методы, в которые мы погрузимся в главе 6. То же касается прогнозов для конкретного пациента, если модель уже имеется: байесовский вывод извлечет максимум из неизбежно неполной и зашумленной картины. Хорошо то, что для лечения рака не обязательно понимать функционирование опухолевых клеток полностью и во всех подробностях: достаточно просто обезвредить их, не повреждая нормальные клетки. В главе 6 мы увидим, как правильно сориентировать обучение, обходя то, чего мы не знаем и не обязательно должны знать.
На нынешнем этапе нам известно, что на основе данных и предыдущего знания можно с помощью обратной дедукции сделать вывод о структуре клеточных сетей, однако количество способов его применения порождает комбинаторный взрыв, так что требуется какая-то стратегия. Поскольку метаболические сети были разработаны эволюцией, возможно, симулирование эволюции в обучающихся алгоритмах как раз подойдет. В следующей главе мы посмотрим, как это сделать.
В глубинах мозга
Когда метод обратного распространения ошибки «пошел в народ», коннекционисты рисовали в воображении быстрое обучение все больших и больших сетей до тех пор, пока, если позволит «железо», они не сравняются с искусственным мозгом. Оказалось, все не так. Обучение сетей с одним скрытым слоем проходило хорошо, но после этого все резко усложнялось. Сети с несколькими слоями работали только в случае, если их тщательно разрабатывали под конкретное применение (скажем, распознавание символов), а за пределами этих рамок метод обратного распространения терпел неудачу. По мере добавления слоев сигнал ошибки расходился все больше и больше, как река, ветвящаяся на мелкие протоки вплоть до отдельных незаметных капелек. Обучение с десятками и сотнями скрытых слоев, как в мозге, оставалось отдаленной мечтой, и к середине 1990-х восторги по поводу многослойных перцептронов поутихли. Стойкое ядро коннекционистов не сдавалось, но в целом внимание переместилось в другие области машинного обучения (мы увидим их в главах 6 и 7).
Однако сегодня коннекционизм возрождается. Мы обучаем более глубокие сети, чем когда бы то ни было, и они задают новые стандарты в зрении, распознавании речи, разработке лекарственных средств и других сферах. Новая область — глубокое обучение — появилась даже на первой странице New York Times, но, если заглянуть под капот, мы с удивлением увидим, что там гудит все тот же старый добрый двигатель — метод обратного распространения ошибки. Что изменилось? В общем-то, ничего нового, скажут критики: просто компьютеры сделались быстрее, а данных cтало больше. На это Хинтон и другие ответят: «Вот именно! Мы были совершенно правы!»
По правде говоря, коннекционисты добились больших успехов. Одним из героев последнего взлета на американских горках коннекционизма стало непритязательное маленькое устройство под названием автокодировщик — многослойный перцептрон, который на выходе выдает то же, что получил на входе. Он получает изображение вашей бабушки и выдает ту же самую картинку. На первый взгляд это может показаться дурацкой затеей: где вообще можно применить эту штуку? Но вся суть в том, чтобы скрытый слой был намного меньше, чем входной и выходной, то есть чтобы сеть не могла просто научиться копировать вход в скрытый слой, а скрытый слой — в выходной, потому что в таком случае устройство вообще никуда не годится. Однако если скрытый слой маленький, происходит интересная вещь: сеть вынуждена кодировать вход всего несколькими битами, чтобы представить его в скрытом слое, а затем эти биты декодируются обратно до полного размера. Система может, например, научиться кодировать состоящее из миллиона пикселей изображение бабушки всего лишь семью буквами — словом «бабушка» — или каким-то коротким кодом собственного изобретения и одновременно научиться раскодировать это слово в картинку милой вашему сердцу пенсионерки. Таким образом, автокодировщик похож на инструмент для сжатия файлов, но имеет два преимущества: сам разбирается, как надо сжимать, и, как сети Хопфилда, умеет превращать зашумленное, искаженное изображение в хорошее и чистое.
Автокодировщики были известны еще в 1980-х, но тогда их было очень сложно учить, несмотря на всего один скрытый слой. Разобраться, как упаковать большой объем информации в горсть битов, — чертовски сложная проблема (один код для вашей бабушки, немного другой — для дедушки, еще один — для Дженнифер Энистон[68] и так далее): ландшафт гиперпространства слишком изрезан, чтобы забраться на хороший пик, а скрытые элементы должны узнать, из чего складывается избыток исключающих ИЛИ на входе. Из-за этих проблем автокодировщики тогда по-настоящему не привились. Чтобы преодолеть сложности, потребовалось больше десятилетия. Был придуман следующий трюк: скрытый слой надо сделать больше, чем входной и выходной. Что это даст? На самом деле это только половина решения: вторая часть — заставить все, кроме некоторого количества скрытых единиц, быть выключенными в данный момент. Это все еще не позволяет скрытому слою просто копировать вход и, что самое главное, сильно облегчает обучение. Если мы позволим разным битам представлять разные входы, входы перестанут конкурировать за настройку одних и тех же битов. Кроме того, у сети появится намного больше параметров, поэтому у гиперпространства будет намного больше измерений, а следовательно, и способов выбраться из того, что могло бы стать локальными максимумами. Этот изящный трюк называется разреженным автокодировщиком.
Однако по-настоящему глубокого обучения мы пока не видели. Следующая хитрая идея — поставить разреженные автокодировщики друг на друга, как большой сэндвич. Скрытый слой первого становится входом/выходом для второго и так далее. Поскольку нейроны нелинейные, каждый скрытый слой учится более сложным представлениям входа, основываясь на предыдущем. Если имеется большой набор изображений лиц, первый автокодировщик научится кодировать мелкие элементы, например уголки и точки, второй использует это для кодирования черт лица, например кончика носа и радужки глаза, третий займется целыми носами и глазами и так далее. Наконец, верхний слой может быть традиционным перцептроном — он научится узнавать вашу бабушку по чертам высокого уровня, которые дает нижележащий слой. Это намного легче, чем использовать только сырые данные одного скрытого слоя или пытаться провести обратное распространение сразу через все слои. Сеть Google Brain, прорекламированная New York Times, представляет собой бутерброд из девяти слоев автокодировщиков и других ингредиентов, который учится узнавать кошек на видеороликах на YouTube. На тот момент эта сеть была крупнейшей, которую когда-либо обучали: в ней был миллиард соединений. Неудивительно, что Эндрю Ын, один из руководителей проекта, — горячий сторонник идеи, что человеческий разум сводится к одному алгоритму и достаточно просто его найти. Ын, за обходительными манерами которого скрывается невероятная амбициозность, убежден, что многоярусные разреженные автокодировщики могут привести нас ближе к разгадке искусственного интеллекта, чем все, что мы имели раньше.
Многоярусные автокодировщики — не единственная разновидность глубоких обучающихся алгоритмов. Еще одна основана на машинах Больцмана, встречаются модели зрительной коры на сверточных нейронных сетях. Однако, несмотря на замечательные успехи, все это пока еще очень далеко от головного мозга. Сеть Google умеет распознавать кошачьи мордочки только анфас, а человек узнает кота в любой позе, даже если тот вообще отвернется. Кроме того, сеть Google все еще довольно мелкая: автокодировщики составляют всего три из девяти ее слоев. Многослойный перцептрон — удовлетворительная модель мозжечка — части мозга, ответственной за низкоуровневый контроль движений. Однако кора головного мозга — совсем другое дело. В ней нет, например, обратных связей, необходимых для распространения ошибки, и тем не менее именно в коре происходит настоящее волшебство обучения. В своей книге On Intelligence («Об интеллекте») Джефф Хокинс отстаивает разработку алгоритмов, основанных на близком воспроизведении строения коры головного мозга, но ни один из этих алгоритмов пока не может соперничать с сегодняшними глубокими сетями.
По мере того как мы будем лучше понимать мозг, ситуация может измениться. Вдохновленная проектом «Геном человека», новая дисциплина — коннектомика — стремится составить карту всех мозговых синапсов. В построение полноценной модели Евросоюз вложил миллиарды евро, а американская программа BRAIN, имеющая схожие цели, только в 2014 году получила 100 миллионов долларов финансирования. Тем не менее символисты очень скептически смотрят на этот путь к Верховному алгоритму. Даже если мы будем представлять себе весь мозг на уровне отдельных синапсов, понадобятся (какая ирония) более совершенные алгоритмы машинного обучения, чтобы превратить эту картину в монтажные схемы: о том, чтобы сделать это вручную, не может быть и речи. Хуже то, что, даже получив полную карту головного мозга, мы все еще будем теряться в догадках, как он работает. Нервная система червя Caenorhabditis elegans, состоящая всего из 302 нейронов, была полностью картирована еще в 1986 году, однако мы по-прежнему понимаем ее работу лишь фрагментарно. Чтобы что-то понять в болоте мелких деталей и «выполоть» специфичные для человека подробности и просто причуды эволюции, нужны более высокоуровневые концепции. Мы не строим самолеты путем обратной инженерии птичьих перьев, и самолеты не машут крыльями, однако в основе конструкции самолета лежат принципы аэродинамики, единые для всех летающих объектов. Аналогичных принципов мышления мы все еще не имеем.
Может быть, коннектомика впадает в крайности: некоторые коннекционисты, по слухам, утверждают, что метод обратного распространения и есть Верховный алгоритм: надо просто увеличить масштаб. Но символисты высмеивают эти взгляды и предъявляют длинный перечень того, что люди делать умеют, а нейронные сети — нет. Взять хотя бы «здравый смысл», требующий соединять фрагменты информации, до этого, может быть, никогда и рядом не стоявшие. Ест ли Мария на обед ботинки? Не ест, потому что она человек, люди едят только съедобные вещи, а ботинки несъедобные. Символические системы справляются с этим без проблем — они просто составляют цепочки соответствующих правил, — а многослойные перцептроны этого делать не умеют и, обучившись, будут раз за разом вычислять одну и ту же фиксированную функцию. Нейронные сети — не композиционные, а композиционность — существенный элемент человеческого познания. Еще одна большая проблема в том, что и люди, и символические модели, например наборы правил и деревья решений, способны объяснять ход своих рассуждений, в то время как нейронные сети — большие горы чисел, которые никто не может понять.
Но если у человека есть все эти способности и мозг не выучивает их путем подбора синапсов, откуда они берутся? Вы не верите в волшебство? Тогда ответ — «эволюция». Убежденный критик коннекционизма просто обязан разобраться, откуда эволюция узнала все, что ребенок знает при рождении, — и чем больше мы списываем на врожденные навыки, тем труднее задача. Если получится все это понять и запрограммировать компьютер выполнять такую задачу, будет очень неучтиво отказывать вам в лаврах изобретателя Верховного алгоритма — по крайней мере, одного из его вариантов.
ГЛАВА 5
ЭВОЛЮЦИЯ: ОБУЧАЮЩИЙСЯ АЛГОРИТМ ПРИРОДЫ
Перед вами Robotic Park — огромная фабрика по производству роботов. Вокруг нее — тысяча квадратных миль джунглей, каменных и не очень. Джунгли окружает самая высокая и толстая в мире стена, утыканная наблюдательными вышками, прожекторами и орудийными гнездами. У стены две задачи: не пустить на фабрику нарушителей и не выпустить ее обитателей — миллионы роботов, сражающихся за выживание и власть. Роботы-победители размножаются путем доступа к программированию 3D-принтеров. Шаг за шагом роботы становятся умнее, быстрее и смертоноснее. Robotic Park принадлежит Армии США и призван путем эволюции вывести совершенного солдата.
Пока такой фабрики не существует, но однажды она может появиться. Несколько лет назад на мастер-классе DARPA я предложил эту идею в рамках мысленного эксперимента, и один из присутствующих в зале высших чинов сухо заметил: «Да, это реализуемо». Его решимость будет выглядеть не такой пугающей, если вспомнить, что для обучения своих подразделений американская армия построила в калифорнийской пустыне полноценный макет афганской деревни вместе с жителями, так что несколько миллиардов долларов — небольшая цена за идеального бойца.
Первые шаги в этом направлении уже сделаны. В лаборатории Creative Machines Lab в Корнелльском университете, которой руководит Ход Липсон, роботы причудливых форм учатся плавать и летать — возможно, прямо сейчас, когда вы читаете эти строки. Один из них похож на ползающую башню из резиновых блоков, другой — на вертолет со стрекозиными крыльями, еще один — на меняющий форму конструктор Tinkertoy. Эти роботы созданы не инженерами, а эволюцией — тем самым процессом, который породил разнообразие жизни на Земле. Изначально роботы эволюционируют внутри компьютерной симуляции, но, как только они становятся достаточно перспективными, чтобы выйти в реальный мир, их автоматически печатают на 3D-принтере. Творения Липсона пока не готовы захватить мир, но они уже далеко ушли от первобытного набора элементов в компьютерной программе, в которой они родились.
Алгоритм, обеспечивший эволюцию этих роботов, изобрел в XIX веке Чарльз Дарвин. В то время он не воспринимал эволюцию как алгоритм, отчасти потому, что в ней недоставало ключевой подпрограммы. Как только Джеймс Уотсон и Фрэнсис Крик[69] в 1953 году открыли ее, все было готово для второго пришествия: эволюция in silico вместо in vivo[70], происходящая в миллиард раз быстрее. Ее пророком стал Джон Холланд — румяный улыбчивый парень со Среднего Запада[71].
Алгоритм Дарвина
Как и многие другие ученые, работавшие над ранними этапами машинного обучения, Холланд начинал с нейронных сетей, но, после того как он — тогда еще студент Мичиганского университета — прочитал классический трактат Рональда Фишера The Genetical Theory of Natural Selection[72], его интересы приобрели другое направление. В своей книге Фишер, который также был основателем современной статистики, сформулировал первую математическую теорию эволюции. Теория Фишера была блестящей, но Холланд чувствовал, что в ней не хватает самой сути эволюции: автор рассматривал каждый ген изолированно, а ведь приспособленность организма — комплексная функция всех его генов. Если бы гены были независимы, частотность их вариантов очень быстро сошлась бы в точку максимальной приспособленности и после этого оставалась бы в равновесии. Но если гены взаимодействуют, эволюция — поиск максимальной приспособленности — становится невообразимо сложнее. Когда в геноме тысяча генов и у каждого два варианта, это даст 21000 возможных состояний: во Вселенной нет такой древней и большой планеты, чтобы все перепробовать. И тем не менее эволюция на Земле сумела создать ряд замечательно приспособленных организмов, и теория естественного отбора Дарвина объясняет, как именно это происходит, по крайней мере качественно, а не количественно. Холланд решил превратить все это в алгоритм.
Но сначала ему надо было окончить университет. Он благоразумно выбрал более традиционную тему — булевы схемы с циклами — и в 1959 году защитил первую в мире диссертацию по информатике. Научный руководитель Холланда Артур Бёркс[73] поощрял интерес к эволюционным вычислениям: помог ему устроиться по совместительству на работу в Мичиганском университете и защищал его от нападок старших коллег, которые вообще не считали эту тему информатикой. Сам Бёркс был таким открытым для новых идей, потому что тесно сотрудничал с Джоном фон Нейманом[74], доказавшим принципиальную возможность существования самовоспроизводящихся машин. Бёрксу выпало завершить эту работу после того, как в 1957 году фон Нейман умер от рака. То, что фон Нейману удалось доказать возможность существования таких машин, — замечательное достижение, учитывая примитивное состояние генетики и информатики в то время, однако его автомат просто делал точные копии самого себя: эволюционирующие автоматы ждали Холланда.
Ключевой вход генетического алгоритма, как назвали творение Холланда, — функция приспособленности. Если имеется программа-кандидат и некая цель, которую эта программа должна выполнить, функция приспособленности присваивает программе баллы, показывающие, насколько хорошо она справилась с задачей. Можно ли так интерпретировать приспособленность в естественном отборе — большой вопрос: приспособленность крыла к полету интуитивно понятна, однако цель эволюции как таковой неизвестна. Тем не менее в машинном обучении необходимость чего-то похожего на функцию приспособленности не вызывает никаких сомнений. Если нам нужно поставить диагноз, то программа, которая дает правильный результат у 60 процентов пациентов в нашей базе данных, будет лучше, чем та, что попадает в точку только в 55 процентах случаев, и здесь возможной функцией приспособленности станет доля правильно диагностированных случаев.
В этом отношении генетические алгоритмы во многом похожи на искусственную селекцию. Дарвин открывает «Происхождение видов» дискуссией на эту тему, чтобы, оттолкнувшись от нее, перейти к более сложной концепции естественного отбора. Все одомашненные растения и животные, которые мы сегодня воспринимаем как должное, появились в результате многих поколений отбора и спаривания организмов, лучше всего подходящих для наших целей: кукурузы с самыми крупными початками, деревьев с самыми сладкими фруктами, самых длинношерстных овец, самых выносливых лошадей. Генетические алгоритмы делают то же самое, только выращивают они не живых существ, а программы, и поколение длится несколько секунд компьютерного времени, а не целую жизнь.
Функция приспособленности воплощает роль человека в этом процессе, но более тонкий аспект — это роль природы. Начав с популяции не очень подходящих кандидатов — возможно, совершенно случайных, — генетический алгоритм должен прийти к вариантам, которые затем можно будет отобрать на основе приспособленности. Как это делает природа? Дарвин этого не знал. Здесь в игру вступает генетическая часть алгоритма. Точно так же как ДНК кодирует организм в последовательности пар азотистых оснований, программу можно закодировать в строке битов. Вместо нулей и единиц алфавит ДНК состоит из четырех символов — аденина, тимина, гуанина и цитозина. Но различие лишь поверхностное. Вариативность последовательности ДНК, или строки битов, можно получить несколькими способами. Самый простой подход — это точечная мутация, смена значения произвольного бита в строке или изменение одного основания в спирали ДНК. Но Холланд видел настоящую мощь генетических алгоритмов в более сложном процессе: половом размножении.
Если снять с полового размножения все лишнее (не хихикайте), останется суть: обмен генетического материала между хромосомами отца и матери. Этот процесс называется кроссинговер, и его результат — появление двух новых хромосом. Первая состоит из материнской хромосомы до точки перекреста, после которой идет отцовская, вторая — наоборот:
Генетический алгоритм основан на подражании этому процессу. В каждом поколении он сводит друг с другом самые приспособленные особи, перекрещивает их битовые строки в произвольной точке и получает двух потомков от каждой пары родителей. После этого алгоритм делает в новых строках точечные мутации и отпускает в виртуальный мир. Когда строки возвращаются с присвоенным значением приспособленности, процесс повторяется заново. Каждое новое поколение более приспособлено, чем предыдущее, и процесс прерывается либо после достижения желаемой приспособленности, либо когда заканчивается время.
Представьте, например, что нам нужно вывести правило для фильтрации спама. Если в обучающих данных десять тысяч разных слов, каждое правило-кандидат можно представить в виде строки из 20 тысяч битов, по два для каждого слова. Первый бит для слова «бесплатно» будет равен единице, если письмам, содержащим слово «бесплатно», разрешено соответствовать правилу, и нулю, если не разрешено. Второй бит противоположен: один, если письма, не содержащие слова «бесплатно», соответствуют правилу, и ноль — если не соответствуют. Если единице равны оба бита, письмо будет соответствовать правилу вне зависимости от того, содержит оно слово «бесплатно» или нет, то есть правило, по сути, не содержит условий для этого слова. С другой стороны, если оба бита равны нулю, правилу не будут соответствовать никакие письма, поскольку либо один, либо другой бит всегда ошибается и такой фильтр пропустит любые письма (ой!). В целом письмо соответствует правилу, только если оно разрешает весь паттерн содержащихся и отсутствующих в нем слов. Приспособленностью правила может быть, например, процент писем, который оно правильно классифицирует. Начиная с популяции произвольных строк, каждая из которых представляет собой правило с произвольными условиями, генетический алгоритм будет выводить все более хорошие правила путем повторяющегося кроссинговера и мутаций самых подходящих строк в каждом поколении. Например, если в текущей популяции есть правило «Если письмо содержит слово “бесплатный” — это спам» и «Если письмо содержит слово “легко” — это спам», перекрещивание их даст, вероятно, более подходящее правило «Если письмо содержит слова “бесплатный” и “легко” — это спам», при условии, что перекрест не придется между двумя битами, соответствующими одному из этих слов. Кроссинговер также породит правило «Все письма — спам», которое появится в результате отбрасывания обоих условий. Но у этого правила вряд ли будет много потомков в следующем поколении.
Поскольку наша цель — создать лучший спам-фильтр из всех возможных, мы не обязаны честно симулировать настоящий естественный отбор и можем свободно хитрить, подгоняя алгоритм под свои нужды. Одна из частых уловок — допущение бессмертия (жаль, что в реальной жизни его нет): хорошо подходящая особь будет конкурировать за размножение не только в своем поколении, но и с детьми, внуками, правнуками и так далее — до тех пор пока остается одной из самых приспособленных в популяции. В реальном мире все не так. Лучшее, что может сделать очень приспособленная особь, — передать половину своих генов многочисленным детям, каждый из которых будет, вероятно, менее приспособлен, так как другую половину генов унаследует от второго родителя. Бессмертие позволяет избежать отката назад, и при некотором везении алгоритм быстрее достигнет желаемой приспособленности. Конечно, если оценивать по количеству потомков, самые приспособленные индивидуумы в истории были похожи на Чингисхана — предка одного из двух сотен живущих сегодня людей. Так что, наверное, не так плохо, что в реальной жизни бессмертие не дозволено.
Если мы хотим вывести не одно, а целый набор правил фильтрации спама, можно представить набор — кандидат из n правил в виде строки n 20 000 битов (20 тысяч для каждого правила, если в данных, как раньше, 10 тысяч разных слов). Правила, содержащие для каких-то слов 00, выпадают из набора, поскольку они, как мы видели выше, не подходят ни к каким письмам. Если письмо подходит к любому правилу в наборе, оно классифицируется как спам. В противном случае оно допустимо. Мы по-прежнему можем сформулировать приспособленность как процент правильно классифицированных писем, но для борьбы с переобучением, вероятно, будет целесообразно вычитать из результата штраф,пропорциональный сумме активных условий в наборе правил.
Мы поступим еще изящнее, если разрешим выводить правила для промежуточных концепций, а затем выстраивать цепочки из этих правил в процессе работы. Например, мы можем получить правила «Если письмо содержит слово “кредит” — это мошенничество» и «Если письмо — мошенничество, значит, это письмо — спам». Поскольку теперь следствие из правила не всегда «спам», требуется ввести в строки правил дополнительные биты, чтобы представить эти следствия. Конечно, компьютер не использует слово «мошенничество» буквально: он просто выдает некую строку битов, представляющую это понятие, но для наших целей этого вполне достаточно. Такие наборы правил Холланд называет системами классификации. Они «рабочие лошадки» эволюционистов — основанного им племени машинного обучения. Как и многослойные перцептроны, системы классификации сталкиваются с проблемой присвоения коэффициентов доверия — какова приспособленность правил к промежуточным понятиям? — и для ее решения Холланд разработал так называемый алгоритм пожарной цепочки. Тем не менее системы классификации используются намного реже, чем многослойные перцептроны.
По сравнению с простой моделью, описанной в книге Фишера, генетические алгоритмы — довольно большой скачок. Дарвин жаловался, что ему не хватает математических способностей, но, живи он на столетие позже, то, вероятно, горевал бы из-за неумения программировать. Поймать естественный отбор в серии уравнений действительно крайне сложно, однако выразить его в виде алгоритма — совсем другое дело, и это могло бы пролить свет на многие мучающие человечество вопросы. Почему виды появляются в палеонтологической летописи внезапно? Где доказательства, что они постепенно эволюционировали из более ранних видов? В 1972 году Нильс Элдридж и Стивен Джей Гулд[75] предположили, что эволюция состоит из ряда «прерывистых равновесий»: перемежающихся длинных периодов застоя и коротких всплесков быстрых изменений, одним из которых стал кембрийский взрыв[76]. Эта теория породила жаркие дебаты: критики прозвали ее «дерганной эволюцией». На это Элдридж и Гулд отвечали, что постепенную эволюцию можно назвать «ползучей». Эксперименты с генетическими алгоритмами говорят в пользу скачков. Если запустить такой алгоритм на 100 тысяч поколений и понаблюдать за популяцией в тысячепоколенных отрезках, график зависимости приспособленности от времени будет, вероятно, похож на неровную лестницу с внезапными скачками улучшений, за которыми идут плоские периоды затишья, со временем длящиеся все дольше. Несложно догадаться, почему так происходит: когда алгоритм достигнет локального максимума — пика на ландшафте приспособленности, — он будет оставаться там до тех пор, пока в результате счастливой мутации или кроссинговера какая-то особь не окажется на склоне более высокого пика: в этот момент такая особь начнет размножаться и с каждым поколением взбираться по склону все выше. Чем выше текущий пик, тем дольше приходится ждать такого события. Конечно, в природе эволюция сложнее: во-первых, среда может меняться — как физически, так и потому, что другие организмы тоже эволюционируют, и особь на пике приспособленности вдруг может почувствовать давление и будет вынуждена эволюционировать снова. Так что текущие генетические алгоритмы полезны, но конец пути еще очень далеко.
Дилемма изучения–применения
Обратите внимание, насколько генетические алгоритмы отличаются от многослойных перцептронов. Метод обратного распространения в любой момент времени рассматривает одну гипотезу, и эта гипотеза постепенно меняется, пока не найдет локальный оптимум. Генетические алгоритмы на каждом этапе рассматривают всю популяцию гипотез и благодаря кроссинговеру способны делать большие скачки от одного поколения к другому. После установления небольших произвольных исходных весов обратное распространение действует детерминистски, а в генетических алгоритмах много случайных выборов: какие гипотезы оставить в живых и подвергнуть кроссинговеру (более вероятные кандидаты — лучше приспособленные гипотезы), где скрестить две строки, какие биты мутировать. Процесс обратного распространения получает веса для заранее определенной архитектуры сети: более густые сети эластичнее, но их сложнее обучать. Генетические алгоритмы не делают априорных допущений об изучаемой структуре, кроме общей формы.
Благодаря этому генетические алгоритмы с намного меньшей вероятностью, чем обратное распространение ошибки, застревают в локальном оптимуме и в принципе более способны прийти к чему-то по-настоящему новому. В то же время их намного сложнее анализировать. Откуда нам знать, что генетический алгоритм получит что-то осмысленное, а не будет, как пьяный, слоняться вокруг да около? Главное здесь — мыслить в категориях кирпичиков. Каждый поднабор битов в строке потенциально кодирует полезный кирпичик, и, если скрестить две строки, кирпичики сольются в более крупный блок, который мы будем использовать в дальнейшем. Иллюстрировать силу кирпичиков Холланд любил с помощью фотороботов. До появления компьютеров полицейские художники умели по показаниям свидетелей быстро рисовать портрет подозреваемого: подбирали бумажную полоску из набора типичных форм рта, потом полоску с глазами, носом, подбородком и так далее. Система из десяти элементов по десять вариантов каждого позволяла составить 10 миллиардов разных лиц. Это больше, чем людей на планете.
В машинном обучении и вообще в информатике нет ничего лучше, чем сделать комбинаторный взрыв не врагом, а союзником. В генетических алгоритмах интересно то, что каждая строка косвенно содержит экспоненциальное число строительных блоков — схем, — поэтому поиск намного эффективнее, чем кажется. Дело в том, что каждый поднабор битов в строке — это схема, представляющая некую потенциально подходящую комбинацию свойств, а количество поднаборов в строке экспоненциально. Схему можно представить, заменив не входящие в нее биты звездочкой: например, строка 110 содержит схемы ***, **0, *1*, 1**, *10, 11*, 1*0 и 110. Каждый выбор битов дает свою схему, а поскольку для каждого бита у нас есть два варианта действий (включать / не включать в схему), это дает 2n схем. И наоборот, конкретную схему в популяции могут представлять многие строки, и каждый раз схема неявно оценивается. Представьте, что вероятность выживания и перехода гипотезы в следующее поколение пропорциональна ее приспособленности. Холланд показал, что в таком случае чем более приспособлены представления схемы в одном поколении по сравнению со средним значением, тем с большей вероятностью можно ожидать увидеть их в следующем поколении. Поэтому, хотя генетический алгоритм явно оперирует строками, косвенно он ищет в гораздо более обширном пространстве схем. Со временем в популяции начинают доминировать более приспособленные схемы, и, в отличие от пьяного, генетические алгоритмы находят дорогу домой.
Одна из самых важных проблем как машинного обучения, так и жизни — дилемма изучения–применения. Если вы нашли что-то работающее, лучше просто это использовать или попытаться поискать дальше, зная, что это может оказаться пустой тратой времени, а может привести к более хорошему решению. Лучше быть ковбоем или фермером? Основать новую компанию или управлять уже существующей? Поддерживать постоянные отношения или непрерывно искать свою половинку? Кризис среднего возраста — тяга к изучению после многих лет применения. Человек срывается с места и летит в Лас-Вегас, полный решимости потратить сбережения всей жизни ради шанса стать миллионером. Он входит в первое попавшееся казино и видит ряд игровых автоматов. Сыграть надо в тот, который даст в среднем лучший выигрыш, но где он стоит — неизвестно. Чтобы разобраться, надо попробовать каждый автомат достаточное количество раз, но, если заниматься этим слишком долго, все деньги уйдут на проигрышные варианты. И наоборот, если перестать пробовать слишком рано и выбрать автомат, который случайно показался удачным в первые несколько раундов, но на самом деле не самый хороший, можно играть на нем остаток ночи и просадить все деньги. В этом суть дилеммы изучения–применения: каждый раз приходится выбирать между повторением хода, принесшего наибольший на данный момент выигрыш, и другими шагами, которые дадут информацию, ведущую, возможно, к еще большему выигрышу. Холланд доказал, что для двух игровых автоматов оптимальная стратегия — каждый раз подбрасывать неправильную монету, которая по мере развития событий становится экспоненциально более неправильной. (Только не подавайте на меня в суд, если этот метод не сработает. Помните, что в конечном счете казино всегда выигрывает.) Чем перспективнее выглядит игровой автомат, тем дольше вы должны в него играть, но нельзя совсем отказываться от второго на случай, если в конце концов он окажется лучшим.
Генетический алгоритм похож на вожака банды профессиональных игроков, которые играют в автоматы сразу во всех казино города. Две схемы конкурируют друг с другом, если включают одни и те же биты, но отличаются по крайней мере одним из них, например *10 и *11, а n конкурирующих схем — как n игровых автоматов. Каждый набор конкурирующих схем — это казино, и генетический алгоритм одновременно определяет автомат-победитель в каждом из них, следуя оптимальной стратегии: игре на самых перспективных машинах с экспоненциально увеличивающейся частотой. Хорошо придумано.
В книге «Автостопом по галактике»[77] инопланетная цивилизация строит огромный суперкомпьютер, чтобы ответить на Главный Вопрос, и спустя долгое время компьютер выдает ответ: «42». При этом компьютер добавляет, что инопланетяне не знают, в чем заключается этот вопрос, поэтому те строят еще больший компьютер, чтобы это определить. К сожалению, этот компьютер, известный также как планета Земля, уничтожают, чтобы освободить место для космического шоссе, за несколько минут до завершения вычислений, длившихся много миллионов лет. Теперь можно только гадать, какой это был вопрос, но, наверное, он звучал так: «На каком автомате мне сыграть?»
Выживание самых приспособленных программ
Первые несколько десятилетий сообщество, занимавшееся генетическими алгоритмами, состояло в основном из самого Джона Холланда, его студентов и студентов его студентов. Примерно в 1983 году самой большой проблемой, которую умели решать генетические алгоритмы, было обучение управлению системами газопроводов. Но затем, примерно в период второго пришествия нейронных сетей, интерес к эволюционным вычислениям начал набирать обороты. Первая международная конференция по генетическим алгоритмам состоялась в 1985 году в Питтсбурге, а потом произошел кембрийский взрыв разновидностей генетических алгоритмов. Некоторые из них пробовали моделировать эволюцию более точно: в конце концов, базовый генетический алгоритм был только грубым ее приближением. Другие шли в самых разных направлениях, скрещивая эволюционные идеи с концепциями из области информатики, которые смутили бы Дарвина.
Одним из самых выдающихся студентов Холланда был Джон Коза[78]. В 1987 году он возвращался на самолете в Калифорнию с конференции в Италии, и его озарило: почему бы не получать путем эволюции полноценные компьютерные программы, а не сравнительно простые вещи вроде правил «Если…, то…» и контроллеров газопроводов? А если поставить себе такую цель, зачем держаться за битовые строки как их представление? Программа на самом деле — дерево обращений к подпрограммам, поэтому лучше непосредственно скрещивать эти поддеревья, а не втискивать их в битовые строки и рисковать разрушить отличные подпрограммы, перекрещивая их в произвольной точке.
Например, представьте, что вы хотите вывести программу, вычисляющую длину года на некой планете (T) на основе ее расстояния от солнца (D). По третьему закону Кеплера, T — это квадратный корень из D в кубе, умноженный на постоянную C, которая зависит от используемых единиц времени и расстояния. Генетический алгоритм должен уметь работать на основе данных Тихо Браге о планетарных движениях, как когда-то сам Кеплер работал. В подходе Коза D и C — это листья программного дерева, а операции, которые их соединяют, например умножение и извлечение квадратного корня, — это внутренние узлы. Вот программное дерево, которое правильно вычисляет T:
В генетическом программировании, как Коза назвал свой метод, мы скрещиваем два программных дерева, произвольно меняя местами два их поддерева. Например, одним из результатов кроссинговера деревьев на рисунке ниже, проведенного в выделенных узлах, будет правильная программа для вычисления T:
Мы можем измерить приспособленность программы (или ее неприспособленность) по расстоянию между ее фактическим выходом и правильным выходом на обучающих данных. Например, если программа говорит, что на Земле в году 300 дней, это вычтет из ее приспособленности 65 пунктов. Генетическое программирование начинает с популяции случайных программных деревьев, а потом использует кроссинговер, мутации и выживание для постепенного выведения лучших программ, пока не будет удовлетворено результатом.
Конечно, расчет продолжительности планетарного года — очень простая задача: в ней есть только умножение и квадратный корень. В целом программные деревья могут включать полный спектр элементов программирования, например утверждения «если… то…», циклы и рекурсию. Более показательный пример возможностей генетического программирования — это определение последовательности действий робота для достижения определенной цели. Представьте, что я попросил своего офисного робота принести мне степлер из кладовки. У робота для этого есть большой набор возможных действий: пройти по коридору, открыть дверь, взять предмет и так далее. Каждое из них, в свою очередь, может состоять из различных поддействий: например, протянуть манипулятор к предмету, схватить его в самых разных точках. В зависимости от результатов предыдущих действий новые действия могут выполняться или не выполняться, иногда нужно их повторить некоторое количество раз и так далее. Задача состоит в том, чтобы составить правильную структуру действий и поддействий, а также определить параметры каждого из них, например, как далеко выдвинуть манипулятор. Из «атомарных», мельчайших действий робота и их допустимых комбинаций генетическое программирование может собрать сложное поведение для достижения желаемой цели. Многие ученые таким образом выводили стратегии для роботов-футболистов.
Одно из последствий применения кроссинговера к программным деревьям вместо битовых строк заключается в том, что получающиеся в результате программы могут быть любого размера и обучение делается более гибким. Однако такие программы имеют тенденцию к разбуханию: по мере эволюции деревья становятся все больше и больше (это еще называют «выживанием толстейших»). Эволюционисты могут утешиться фактом, что программы, написанные человеком, в этом отношении не лучше — Microsoft Windows содержит 45 миллионов строк кода, — к тому же к созданному человеком коду нельзя применить такие простые решения, как прибавление к функции приспособленности штрафа за сложность.
Первым успехом генетического программирования стала в 1995 году разработка электронных схем. Начав с кучи элементов — транзисторов, резисторов и конденсаторов, — система Коза вновь изобрела запатентованный ранее фильтр нижних частот, который можно использовать, например, для усиления басов в танцевальной музыке. С тех пор Коза превратил повторное изобретение запатентованных устройств в своего рода спорт и начал выдавать их дюжинами. Следующей вехой стал патент на разработанную таким образом промышленную систему оптимизации, выданный в 2005 году Ведомством США по патентам и торговым знакам. Если бы тест Тьюринга[79] заключался в обмане патентного эксперта, а не собеседника, 25 января 2005 года вошло бы в учебники истории.
Своей самоуверенностью Коза выделяется даже среди представителей дисциплины, где скромность не в чести. Он видит в генетическом программировании машину для изобретений, Кремниевого Эдисона XXI столетия. Коза и другие эволюционисты верят, что такой алгоритм может получить любую программу, и ставят на него в гонке за Верховным алгоритмом. В 2004 году они учредили ежегодную премию Humies, которую вручают за «соперничающие с человеком» генетические творения. На сегодняшний день присуждено 39 премий.
Зачем нужен секс?
Несмотря на все успехи и озарения, которые принесли нам генетические алгоритмы в таких вопросах, как градуализм против прерывистого равновесия, одна великая тайна остается неразгаданной: какую роль в эволюции играет половое размножение. Эволюционисты возлагают большие надежды на кроссинговер, однако представители других «племен» считают, что игра не стоит свеч. Ни один из теоретических результатов Холланда не показывает, что кроссинговер полезен: чтобы со временем экспоненциально увеличить частоту наиболее подходящих схем в популяции, достаточно мутаций, а логика «строительных блоков» привлекательна, но быстро сталкивается с проблемами даже при использовании генетического программирования. Когда в ходе эволюции появляются крупные блоки, кроссинговер со все большей вероятностью начинает их разбивать, а если удается вывести очень приспособленную особь, ее потомки, как правило, быстро захватывают популяцию и закрывают собой потенциально более перспективные схемы, содержащиеся в менее приспособленных в целом особях. В результате поиск вариантов сводится к определению чемпиона по приспособленности. Исследователи придумали много приемов сохранения разнообразия в популяции, но результаты пока неубедительны. Инженеры, несомненно, широко используют строительные блоки, но для их правильного соединения нужно, скажем так, много инженерии: сложить их вместе любым старым способом непросто, и неясно, может ли кроссинговер здесь помочь.
Если исключить половое размножение, у эволюционистов в качестве двигателя останутся одни мутации. Когда размер популяции значительно превышает количество генов, есть шанс, что все точечные мутации в ней уже представлены, и тогда поиск становится разновидностью восхождения по выпуклой поверхности: попробуй все возможные шаги, выбери лучший и повтори. (Или выбери несколько лучших вариантов: в таком случае это называется лучевой поиск.) Символисты, например, постоянно используют такой подход для получения наборов правил и не считают его формой эволюции. Чтобы не застрять в локальном максимуме, восхождение можно усилить случайностью (допустить с некоторой вероятностью движение вниз) и случайными перезапусками (через некоторое время перепрыгнуть в произвольное состояние и продолжать восхождение там). Этого достаточно, чтобы найти удачные решения проблем. Оправдывает ли польза от добавления кроссинговера лишние затраты на вычисления — вопрос открытый.
Никто точно не знает, почему половое размножение так распространено в природе. Было выдвинуто несколько теорий, но ни одна из них не стала общепринятой. Ведущее положение занимает гипотеза Черной Королевы[80], популяризированная Мэттом Ридли в книге The Red Queen: Sex and the Evolution of Human Nature («Черная королева. Секс и эволюция человеческой натуры»). Черная Королева говорит Алисе: «Приходится бежать со всех ног, чтобы только остаться на том же месте». Организмы находятся в постоянной гонке с паразитами, и половое размножение помогает популяции быть настолько разнообразной, чтобы ни один микроб не смог заразить ее целиком. Если дело в этом, тогда половое размножение не имеет отношения к машинному обучению, по крайней мере пока полученные путем эволюции программы не начнут соревноваться с компьютерными вирусами за время работы процессора и память. (Что интересно, Дэнни Хиллис[81] утверждает, что целенаправленное введение в генетический алгоритм попутно эволюционирующих паразитов может помочь избежать локальных максимумов путем постепенного наращивания сложности, однако пока по этому пути никто не пошел.) Христос Пападимитриу[82] и его коллеги показали, что половое размножение оптимизирует не приспособленность, а то, что они назвали смешиваемостью: способность гена в среднем хорошо справляться при соединении с другими генами. Это может пригодиться, если функция приспособленности либо неизвестна, либо непостоянна, как в естественном отборе, однако в машинном обучении и оптимизации, как правило, лучше справляется восхождение на выпуклые поверхности.
На этом проблемы генетического программирования не заканчиваются. Получается, что даже его успехи, возможно, совсем не такие «генетические», как хотелось бы эволюционистам. Возьмем разработку электронных схем — знаковый успех генетического программирования. Как правило, даже относительно простые схемы требуют огромного объема поиска, причем неясно, насколько мы обязаны результатами грубой силе, а насколько — генетическому интеллекту. Чтобы ответить растущему хору критиков, Коза включил в свою опубликованную в 1992 году книгу Genetic Programming эксперименты, показывающие, что генетическое программирование превосходит случайно сгенерированных кандидатов в проблеме синтеза булевых схем, но отрыв был небольшой. В 1995 году на Международной конференции по машинному обучению (International Conference on Machine Learning, ICML) в Лейк-Тахо Кевин Лэнг опубликовал статью о том, что восхождение на выпуклые поверхности побеждает генетическое программирование в тех же самых программах, причем часто со значительным перевесом. Коза и другие эволюционисты неоднократно пытались опубликовать свои работы в материалах ICML, ведущем мероприятии в этой области, но, к их растущему разочарованию, их постоянно отклоняли из-за недостаточной эмпирической обоснованности. Коза и так был раздосадован тем, что его не публикуют, поэтому работа Лэнга просто вывела его из равновесия. На скорую руку он написал статью на 23 страницах в два столбца, в которой опровергал выводы Лэнга и обвинял рецензентов ICML в нарушении научной этики, а затем положил по экземпляру на каждое кресло в конференц-зале. Статья Лэнга (а может, и ответ Коза — как посмотреть) стали последней каплей: инцидент в Тахо привел к окончательному расхождению между эволюционистами и остальным сообществом ученых, занимающихся машинным обучением. Эволюционисты хлопнули дверью. Специалисты по генетическому программированию начали проводить собственные конференции, которые впоследствии слились с конференциями по генетическим алгоритмам в GECCO — Genetic and Evolutionary Computing Conference. А мейнстрим машинного обучения во многом просто забыл об их существовании. Печальная развязка, но не первый случай в истории, когда секс приводит к разводу.
Может быть, секс не преуспел в машинном обучении, но в утешение можно сказать, что он все же сыграл видную роль в эволюции технологий. Порнография стала непризнанным «приложением-приманкой» Глобальной сети, не говоря уже о печатной прессе, фотографии и видео. Вибратор был первым ручным электрическим устройством, на столетие опередившим мобильные телефоны. Мотороллеры получили распространение в послевоенной Европе, особенно в Италии, потому что на них молодые пары могли скрыться от своих семей. Одной из «приманок» огня, который миллион лет назад открыл Homo erectus, было, несомненно, то, что с его помощью легче стало назначать свидания. Несомненно и то, что индустрия секс-ботов станет мотором, толкающим человекоподобных роботов ко все большей реалистичности. Просто секс, по-видимому, не средство, а цель технологической эволюции.
Воспитание природы
У эволюционистов и коннекционистов есть одно важное сходство: и те и другие разрабатывают обучающиеся алгоритмы, вдохновленные природой. Однако потом их пути расходятся. Эволюционисты сосредоточены на получении структур: для них тонкая настройка результата путем оптимизации параметров имеет второстепенное значение. Коннекционисты же предпочитают брать простые, вручную написанные структуры со множеством соединений и предоставлять весовому обучению делать всю работу. Это все тот же извечный вопрос о приоритете природы и воспитания, на этот раз в машинном обучении, и у обоих оппонентов имеются веские аргументы.
С одной стороны, эволюция породила много удивительных вещей, самая чудесная из которых — вы сами. С кроссинговером или без него, получение структур путем эволюции — существенный элемент Верховного алгоритма. Мозг может узнать все, но он не может получить еще один мозг. Если как следует разобраться в его архитектуре, можно просто воплотить его в «железе», но пока мы очень далеки от этого, поэтому однозначно надо обратиться за поддержкой к компьютерной симуляции эволюции. Более того, путем эволюции мы хотим получать мозг для роботов, системы с произвольными сенсорами и искусственный сверхинтеллект: нет причин держаться за устройство человеческого мозга, если для этих целей что-то подойдет лучше. С другой стороны, эволюция работает ужасно медленно. Вся жизнь организма дает всего лишь один фрагмент информации о его геноме: приспособленность, выраженную в числе потомков. Это колоссальная расточительность, которую нейронное обучение избегает путем получения информации в месте использования (если можно так выразиться). Как любят подчеркивать коннекционисты, например Джефф Хинтон, нет смысла носить в геноме информацию, если мы легко можем получить ее из органов чувств. Когда новорожденный открывает глаза, в его мозг начинает потоком литься видимый мир, и нужно просто все организовать, а в геноме должна быть задана архитектура машины, которая займется этой организацией.
Как и в дебатах по поводу наследственности и воспитания, ни у одной стороны нет полного ответа, и нужно понять, как соединить оба фактора. Верховный алгоритм — это не генетическое программирование и не обратное распространение ошибки, однако он должен включать основные элементы обоих подходов: обучение структурам и весам. С традиционной точки зрения первую часть дает природа, которая создает мозг в ходе эволюции, а затем за дело берется воспитание, заполняя мозг информацией. Это можно легко воспроизвести в алгоритмах машинного обучения. Сначала происходит обучение структуре сети с использованием (например) восхождения на выпуклые поверхности для определения, какие нейроны соединены друг с другом: надо попробовать добавить в сеть все возможные новые соединения, сохранить те, которые больше всего улучшают ее результативность, и повторить процедуру. Затем нужно узнать вес соединений методом обратного распространения ошибки — и новенький мозг готов к использованию.
Однако в этом месте и в естественной, и в искусственной эволюции появляется важная тонкость: вес надо узнать для всех рассматриваемых структур-кандидатов, а не только для последней, чтобы посмотреть, как хорошо она будет справляться с борьбой за выживание (в природе) или с обучающими данными (в искусственной системе). На каждом этапе нам будут нужны структуры, которые работают лучше всех не до, а после нахождения весов. Поэтому в реальности природа не предшествует воспитанию: они скорее перемежаются, и каждый раунд обучения «воспитанием» готовит сцену для следующего раунда обучения «природой», и наоборот. Природа эволюционирует ради воспитания, которое получает. Эволюционный рост ассоциативных зон коры головного мозга основан на нейронном обучении в сенсорных зонах — без этого он был бы бесполезным. Гусята постоянно ходят за своей мамой (поведение, сформировавшееся в ходе эволюции), но для этого они должны ее узнавать (выученная способность). Если вместо гусыни вылупившиеся птенцы увидят человека, они будут следовать за ним: это замечательно показал Конрад Лоренц[83]. В мозге новорожденного свойства среды уже закодированы, но косвенно: эволюция оптимизирует мозг для извлечения этих свойств из ожидаемых вводных. Аналогично для алгоритма, который итерационно учится новым структурам и весам, каждая новая структура неявно — функция весов, которые он получил в предыдущих раундах.
Из всех возможных геномов лишь немногие соответствуют жизнеспособным организмам, поэтому типичный ландшафт приспособленности представляет собой обширные равнины с периодическими резкими пиками, что очень затрудняет эволюцию. Если начать в Канзасе путь с завязанными глазами, не имея представления, в какой стороне Скалистые горы, можно очень долго блуждать в поисках предгорий и только потом начать восхождение. Однако если соединить эволюцию с нейронным обучением, результат будет очень интересный. Если вы стоите на плоской поверхности, но горы не слишком далеко, нейронное обучение может вас туда привести, причем чем ближе вы к горам, тем с большей вероятностью до них доберетесь. Это как способность видеть горизонт: в степях Уичито такая способность вам не пригодится, зато в Денвере вы увидите вдали Скалистые горы и направитесь к ним. Денвер, таким образом, станет намного более подходящим местом, чем Канзас, где у вас на глазах была повязка. Суммарный эффект — расширение пиков приспособленности и возможность найти путь к ним из мест, которые раньше были проблемными, например точки A на графике ниже:
В биологии это называется эффектом Болдуина, в честь Джеймса Марка Болдуина[84], предложившего его в 1896 году. В эволюции, по Болдуину, выученное поведение впоследствии становится генетически обусловленным: если похожие на собак млекопитающие способны научиться плавать, у них больше шансов эволюционировать в морских котиков (как это и произошло), чем у животных, которые плавать не умеют. Таким образом, индивидуальное обучение может повлиять на эволюцию и без ламаркистских теорий. Джефф Хинтон и Стивен Нолан продемонстрировали эффект Болдуина в машинном обучении путем применения генетических алгоритмов: они получили с помощью эволюции структуру нейронной сети и обнаружили, что ее приспособленность со временем увеличивается, только если разрешено индивидуальное обучение.
Побеждает тот, кто быстрее учится
Эволюция ищет удачные структуры, а нейронное обучение их заполняет: такое сочетание — самый легкий шаг к Верховному алгоритму. Этот подход может удивить любого, кто знаком с бесконечными перипетиями спора о роли природы и воспитания, который не утихает две с половиной тысячи лет. Однако если смотреть на жизнь глазами компьютера, многое проясняется. «Природа» для компьютера — это программа, которую он выполняет, а «воспитание» — получаемые им данные. Вопрос, что важнее, очевидно абсурден. И без программы, и без данных никакого результата не будет, и нельзя сказать, что программа дает 60 процентов результата, а данные — 40. Знакомство с машинным обучением — прививка от такого прямолинейного мышления.
С другой стороны, возникает вопрос: почему наши поиски до сих пор не увенчались успехом? Ведь если соединить два верховных алгоритма природы — эволюцию и головной мозг, — большего и пожелать нельзя! К сожалению, пока мы имеем лишь очень грубую картину того, как учится природа: достаточно хорошую для множества применений, но все еще бледную тень реальности. Например, критически важная часть жизни — развитие эмбриона, а в машинном обучении ему нет аналога: «организм» — самая непосредственная функция генома, и, возможно, здесь нам не хватает чего-то важного. Но еще одна причина в том, что даже полное понимание того, как учится природа, будет недостаточным. Во-первых, природа работает слишком медленно: у эволюции обучение отнимает миллиарды лет, а у мозга — всю жизнь. Культура в этом отношении лучше: результат целой жизни обучения можно дистиллировать в книге, которую человек прочтет за несколько часов. Но обучающиеся алгоритмы должны уметь учиться за минуты или секунды. Побеждает тот, кто учится быстрее, будь то эффект Болдуина, ускоряющий эволюцию, устное общение, ускоряющее человеческое обучение, или компьютеры, открывающие паттерны со скоростью света. Машинное обучение — последняя глава в гонке жизни на Земле, и более быстрое «железо» — лишь половина успеха. Вторая часть — это более умное программное обеспечение.
Важнейшая цель машинного обучения — любой ценой найти лучший обучающийся алгоритм из всех возможных, и эволюция и головной мозг вряд ли на это способны. У порождений эволюции много очевидных изъянов. Например, зрительный нерв млекопитающих связан с передней, а не с задней частью сетчатки, из-за чего рядом с центральной ямкой, областью самого четкого зрения, появляется просто вопиюще ненужное слепое пятно. Молекулярная биология живых клеток — это хаос, поэтому специалисты часто шутят, что верить в разумный замысел могут только люди, которые об этом не подозревают. В архитектуре головного мозга тоже могут быть недостатки: у мозга много ограничений, которых лишены компьютеры — например, очень ограниченная краткосрочная память, — и нет причин их сохранять. Более того, известно много ситуаций, в которых люди постоянно поступают неправильно, и Даниэль Канеман пространно иллюстрирует это в своей книге Thinking, Fast and Slow[85].
В отличие от коннекционистов и эволюционистов, символисты и байесовцы не верят в подражание природе и скорее хотят чисто теоретически понять, что надо делать при обучении — и алгоритмам, и людям. Например, если мы хотим научиться диагностировать рак, недостаточно сказать: «Вот так учится природа, давайте сделаем то же самое». Ставки слишком высоки: ошибки стоят жизней. Врачи должны диагностировать болезнь самым надежным способом, какой только можно придумать, и методы должны быть схожими с теми, которыми математики доказывают теоремы, или хотя бы максимально близкими к ним, учитывая, что такая строгость встречается нечасто. Надо взвешивать доказательства, чтобы свести к минимуму вероятность неверного диагноза, или, точнее, чтобы чем дороже была ошибка, тем меньше была бы вероятность ее совершить. (Например, неспособность найти имеющуюся опухоль потенциально намного опаснее, чем ложное подозрение.) Врачи должны принимать оптимальные решения, а не просто такие, которые кажутся удачными.
Это частный случай линии разлома, проходящего через значительную часть науки и философии: различия между дескриптивными и нормативными теориями, между «есть вот так» и «должно быть вот так». В то же время символисты и байесовцы любят подчеркивать, что попытки понять, как мы должны учиться, могут помочь разобраться, как мы учимся на самом деле, потому что и то и другое предположительно очень даже взаимосвязано. В частности, поведение, которое важно для выживания и которое долго эволюционировало, должно быть близко к оптимальному. Человек не очень хорошо умеет отвечать на письменные вопросы о вероятностях, зато прекрасно, не задумываясь выбирает движение руки и кисти, чтобы попасть в мишень. Многие психологи применяли символистские и байесовские модели для объяснения некоторых аспектов человеческого поведения. Символисты доминировали в первые несколько десятилетий когнитивной психологии. В 1980-х и 1990-х власть захватили коннекционисты, а теперь на взлете сторонники байесовского подхода.
Для самых сложных проблем — тех, которые мы по-настоящему хотим, но не можем решить, например для лечения рака, — истинные «природные» подходы, вероятно, слишком просты и не принесут успеха, даже если дать им огромное количество данных. В принципе можно узнать полную модель метаболической сети клетки путем сочетания поиска структур, с кроссинговером или без, и подбора параметров методом обратного распространения ошибки, однако есть слишком много локальных экстремумов, в которых можно крепко увязнуть. Рассуждать нужно более крупными блоками, собирая и переставляя их при необходимости и используя обратную дедукцию, чтобы заполнить пробелы. А направлять обучение должна цель — оптимальная диагностика рака и нахождение наилучших лекарств для его лечения.
Оптимальное обучение — это главная цель байесовцев, и они не сомневаются, что поняли, как ее достичь. Сюда, пожалуйста…
ГЛАВА 6
В СВЯТИЛИЩЕ ПРЕПОДОБНОГО БАЙЕСА
Из ночной тьмы выступает глыба кафедрального собора. Мозаичные окна льют свет на мостовую и соседние здания, проецируя замысловатые уравнения. Вы подходите ближе и слышите, что изнутри доносятся песнопения. Кажется, это латынь или, может быть, язык математики, но «вавилонская рыбка»[86] у вас в ухе переводит слова на понятный язык: «Поверни ручку! Поверни ручку!» Как только вы входите, пение переходит во вздох удовлетворения. По толпе проносится ропот: «Постериор! Постериор!» Вы проталкиваетесь вперед. Над алтарем возвышается массивная каменная таблица. На ней трехметровыми буквами выгравирована формула:
P(A|B) = P(A) P(B|A) / P(B)
Вы непонимающе смотрите на нее, но очки Google Glass услужливо подсказывают: «Теорема Байеса». Толпа начинает петь: «Больше данных! Больше данных!» Вереницу жертв безжалостно толкают к алтарю. Вдруг вы понимаете, что вы тоже среди них, но слишком поздно. Над вами нависла ручка. Вы кричите: «Нет! Я не хочу быть точкой данных! Пусти-и-ите!» И — просыпаетесь в холодном поту. На коленях у вас лежит книга под названием «Верховный алгоритм». Трясясь от пережитого кошмара, вы продолжаете читать с того места, где остановились.
Теорема, которая правит миром
О формуле, с которой начинается путь к оптимальному обучению, многие слышали: это теорема Байеса. Но в этой главе мы посмотрим на нее в совершенно другом свете и увидим, что она намного мощнее, чем может показаться, если судить по ее повседневному применению. По правде говоря, теорема Байеса — это просто несложное правило обновления уровня доверия к гипотезе при получении новых доказательств: если свидетельство совпадает с гипотезой, ее вероятность идет вверх, если нет — вниз. Например, если тест на СПИД положительный, вероятность соответствующего диагноза повышается. Но когда доказательств — например, результатов анализов — много, все становится интереснее. Чтобы соединить их без риска комбинаторного взрыва, нужно сделать упрощающие допущения. Еще любопытнее рассматривать одновременно большое количество гипотез, например все возможные диагнозы у пациента. Вычисление на основе симптомов вероятности каждого заболевания за разумное время — серьезный интеллектуальный вызов. Когда мы поймем, как это сделать, мы будем готовы учиться по-байесовски. Для этого «племени» обучение — это «просто» еще одно применение теоремы Байеса, где целые модели — гипотезы, а данные — доказательства: по мере накопления данных некоторые модели становятся более вероятными, а некоторые — менее, пока в идеале одна модель не побеждает вчистую. Байесовцы изобрели дьявольски хитрые разновидности моделей, так что давайте приступим.
Томас Байес — английский священник, живший в XVIII веке, — сам того не подозревая, стал центром новой религии. Такой поворот может показаться удивительным, но стоит заметить, что то же самое произошло и с Иисусом: христианство в том виде, в котором мы его знаем, изобрел апостол Павел, а сам Иисус видел в себе вершину иудейской веры. Аналогично байесианство в привычном для нас виде было изобретено Пьер-Симоном де Лапласом — французом, родившимся на пять десятилетий позже Байеса. Байес был проповедником и первым описал новый подход к вероятностям, но именно Лаплас выразил его идеи в виде теоремы.
Лаплас, один из величайших математиков всех времен и народов, наверное, больше всего известен своей мечтой о ньютоновском детерминизме:
Разум, которому в каждый определенный момент были бы известны все силы, приводящие природу в движение, и положение всех тел, из которых она состоит, будь он также достаточно обширен, чтобы подвергнуть эти данные анализу, смог бы объять единым законом движение величайших тел Вселенной и мельчайшего атома; для такого разума ничего не было бы неясного и будущее существовало бы в его глазах точно так же, как прошлое.
Это забавно, поскольку Лаплас был отцом теории вероятностей, которая, как он полагал, представляла собой просто здравый смысл, сведенный к вычислениям. В сердце его исследований вероятности лежала озабоченность вопросом Юма. Откуда, например, мы знаем, что завтра взойдет солнце? Каждый день, вплоть до сегодняшнего, это происходило, но ведь нет никаких гарантий, что так будет и впредь. Ответ Лапласа состоит из двух частей. Первая — то, что мы теперь называем принципом безразличия или принципом недостаточного основания. Однажды — скажем, в начале времен, которое для Лапласа было приблизительно 5 тысяч лет назад, — мы просыпаемся, прекрасно проводим день, а вечером видим, что солнце заходит. Вернется ли оно? Мы никогда не видели восхода, и у нас нет причин полагать, что оно взойдет или не взойдет. Таким образом мы должны рассмотреть два одинаково вероятных сценария и сказать, что солнце снова взойдет с вероятностью 12. Но, продолжал Лаплас, если прошлое хоть как-то указывает на будущее, каждый день, когда солнце восходит, должен укреплять нашу уверенность, что так будет происходить и дальше. Спустя пять тысячелетий вероятность, что солнце завтра снова взойдет, должна быть очень близка единице, но не равняться ей, потому что полной уверенности никогда не будет. Из этого мысленного эксперимента Лаплас вывел свое так называемое правило следования, согласно которому вероятность, что солнце снова взойдет после n восходов, равна (n + 1) / (n + 2). Если n = 0, то это просто 12, а когда n увеличивается, растет и вероятность, стремясь к единице, когда n стремится к бесконечности.
Это правило вытекает из более общего принципа. Представьте, что вы проснулись посреди ночи на чужой планете. Хотя над вами только звездное небо, у вас есть причины полагать, что солнце в какой-то момент взойдет, поскольку большинство планет вращаются вокруг своей оси и вокруг звезды. Поэтому оценка соответствующей вероятности должна быть больше 12 (скажем, 23). Это называется априорной вероятностью восхода солнца, поскольку она предшествует любым доказательствам: вы не исходите из подсчета восходов на этой планете в прошлом, потому что вас там не было и вы их не видели. Априорная вероятность скорее отражает наши убеждения по поводу того, что может произойти, основанные на общих знаниях о Вселенной. Но вот звезды начинают бледнеть, и уверенность, что солнце на этой планете действительно восходит, начинает расти, подкрепляемая земным опытом. Ваша уверенность теперь — это апостериорная вероятность, поскольку она возникает после того, как вы увидели некие доказательства. Небо светлеет, и апостериорная вероятность подскакивает еще раз. Наконец над горизонтом показывается краешек яркого диска, и солнечный луч «ловит башню гордую султана… в огненный силок», как в «Рубаи» Омара Хайяма. Если вы не страдаете галлюцинациями, то можете быть уверены, что солнце взойдет.
Возникает важнейший вопрос: как именно должна меняться апостериорная вероятность при появлении все большего объема доказательств? Ответ дает теорема Байеса. Мы можем рассматривать ее в причинно-следственных категориях. Восход солнца заставляет звезды угасать и делает небо светлее, однако последний факт — более сильное доказательство в пользу рассвета, поскольку звезды могут угасать и посреди ночи, скажем, из-за спустившегося тумана. Поэтому после того, как посветлело небо, вероятность рассвета должна увеличиться больше, чем после того, как вы заметили блекнущие звезды. Математики скажут, что P(рассвет | светлое-небо), то есть условная вероятность восхода солнца при условии, что небо светлеет, будет больше, чем P(рассвет | гаснущие-звезды) — условной вероятности при условии, что звезды блекнут. Согласно теореме Байеса, чем более вероятно, что следствие вызвано причиной, тем более вероятно, что причина связана со следствием: если P(светлое-небо | рассвет) выше, чем P(гаснущие-звезды | рассвет), — может быть, потому что некоторые планеты настолько удалены от своих солнц, что звезды там продолжают светить и после восхода, — следовательно, P(рассвет | светлое-небо) тоже будет выше, чем P(рассвет | гаснущие-звезды).
Однако это еще не все. Если мы наблюдаем следствие, которое может произойти даже без данной причины, то, несомненно, имеется недостаточно доказательств наличия этой причины. Теорема Байеса учитывает это, говоря, что P(причина | следствие) уменьшается вместе с P(следствие), априорной вероятностью следствия (то есть ее вероятностью при отсутствии какого-либо знания о причинах). Наконец, при прочих равных, чем выше априорная вероятность причины, тем выше должна быть апостериорная вероятность. Если собрать все это вместе, получится теорема Байеса, которая гласит:
P(причина | следствие) = P(причина) P(следствие | причина) / P(следствие).
Замените слово «причина» на A, а «следствие» на B, для краткости опустите все знаки умножения, и вы получите трехметровую формулу из кафедрального собора.
Это, конечно, просто формулировка теоремы, а не ее доказательство. Но и доказательство на удивление простое. Мы можем проиллюстрировать его на примере из медицинской диагностики, одной из «приманок» байесовского вывода. Представьте, что вы врач и за последний месяц поставили диагноз сотне пациентов. Четырнадцать из них болели гриппом, у 20 была высокая температура, а у 11 — и то и другое. Условная вероятность температуры при гриппе, таким образом, составляет одиннадцать из четырнадцати, или 1114. Обусловленность уменьшает размеры рассматриваемой нами вселенной, в данном случае от всех пациентов только до пациентов с гриппом. Во вселенной всех пациентов вероятность высокой температуры составляет 20100, а во вселенной пациентов, больных гриппом, — 1114. Вероятность того, что у пациента грипп и высокая температура, равна доле пациентов, больных гриппом, умноженной на долю пациентов с высокой температурой: P(грипп, температура) = P(грипп) P(температура | грипп) = 14100 1114 = 11100. Но верно и следующее: P(грипп, температура) = P(температура) P(грипп | температура). Таким образом, поскольку и то, и другое равно P(грипп, температура), то P(температура) P(грипп | температура) = P(грипп) P(температура | грипп). Разделите обе стороны на P(температура), и вы получите P(грипп | температура) = P(грипп) P(температура | грипп) / P(температура).
Вот и все! Это теорема Байеса, где грипп — это причина, а высокая температура — следствие.
Люди, оказывается, не очень хорошо владеют байесовским выводом, по крайней мере в устных рассуждениях. Проблема в том, что мы склонны пренебрегать априорной вероятностью причины. Если анализ показал наличие ВИЧ и этот тест дает только один процент ложных положительных результатов, стоит ли паниковать? На первый взгляд может показаться, что, увы, шанс наличия СПИДа — 99 процентов. Но давайте сохраним хладнокровие и последовательно применим теорему Байеса: P(ВИЧ | положительный) = P(ВИЧ) P(положительный | ВИЧ) / P(положительный). P(ВИЧ) — это распространенность данного вируса в общей популяции, которая в США составляет 0,3 процента. P(положительный) — это вероятность, что тест даст положительный результат независимо от того, есть у человека СПИД или нет. Скажем, это 1 процент. Поэтому P(ВИЧ | положительный) = 0,003 0,99 / 0,01 = 0,297. Это далеко не 0,99! Причина в том, что ВИЧ в общей популяции встречается редко. Положительный результат теста на два порядка увеличивает вероятность, что человек болен СПИДом, но она все еще меньше 12. Так что, если анализы дали положительный результат, разумнее будет сохранить спокойствие и провести еще один, боле доказательный тест. Есть шанс, что все будет хорошо.
Теорема Байеса полезна, потому что обычно известна вероятность следствий при данных причинах, а узнать хотим вероятность причин при данных следствиях. Например, мы знаем процент пациентов с гриппом, у которых повышена температура, но на самом деле нам нужно определить вероятность, что пациент с температурой болен гриппом. Теорема Байеса позволяет нам перейти от одного к другому. Ее значимость, однако, этим далеко не ограничивается. Для байесовцев эта невинно выглядящая формула — настоящее F = ma машинного обучения, основа, из которой вытекает множество результатов и практических применений. Каков бы ни был Верховный алгоритм, он должен быть «всего лишь» вычислительным воплощением теоремы Байеса. Я пишу «всего лишь» в кавычках, потому что применение теоремы Байеса в компьютерах оказалось дьявольски непростой задачей для всех проблем, кроме простейших. Скоро мы увидим почему.
Теорема Байеса как основа статистики и машинного обучения страдает не только от вычислительной сложности, но и от крайней противоречивости. Вы можете удивиться: разве она не прямое следствие идеи условной вероятности, как мы видели на примере гриппа? Действительно, с формулой как таковой ни у кого проблем не возникает. Противоречие заключается в том, как именно байесовцы получают вероятности, которые в нее включены, и что эти вероятности означают. Для большинства статистиков единственный допустимый способ оценки вероятностей — вычисление частоты соответствующего события. Например, вероятность гриппа равна 0,2, потому что им болело 20 из 100 обследованных пациентов. Это «частотная» интерпретация вероятности, и она дала название господствующему учению в статистике. Но обратите внимание, что в принципе безразличия Лапласа и в примере с восходом солнца мы просто высасываем вероятность из пальца. Чем оправдано априорное предположение, что вероятность восхода солнца равна одной второй, двум третьим или еще какой-то величине? На это байесовцы отвечают, что вероятность — это не частота, а субъективная степень убежденности, поэтому вам решать, какая она будет, а байесовский вывод просто позволяет обновлять априорные убеждения после появления новых доказательств, чтобы получать апостериорные убеждения (это называется «провернуть ручку Байеса»). Поклонники теоремы Байеса верят в эту идею с почти религиозным рвением и 200 лет выдерживают нападки и возражения. С появлением на сцене достаточно мощных компьютеров и больших наборов данных байесовский вывод начал брать верх.
Все модели неверны, но некоторые полезны
Настоящие врачи не диагностируют грипп на основе высокой температуры, а учитывают целый комплекс симптомов, включая боль в горле, кашель, насморк, головную боль, озноб и так далее. Поэтому, когда нам действительно надо вычислить по теореме Байеса P(грипп | температура, кашель, больное горло, насморк, головная боль, озноб, …), мы знаем, что эта вероятность пропорциональна P(температура, кашель, больное горло, насморк, головная боль, озноб, … | грипп). Но здесь мы сталкиваемся с проблемой. Как оценить эту вероятность? Если каждый симптом — булева переменная (он либо есть, либо нет) и врач учитывает n симптомов, у пациента может быть 2n комбинаций симптомов. Если у нас, скажем, 20 симптомов и база данных из 10 тысяч пациентов, мы увидим лишь малую долю из примерно миллиона возможных комбинаций. Еще хуже то, что для точной оценки вероятности конкретного сочетания симптомов нужны как минимум десятки его наблюдений, а это значит, что база данных должна включать десятки миллионов пациентов. Добавьте еще десяток симптомов, и нам понадобится больше пациентов, чем людей на Земле. Если симптомов сто и мы каким-то чудом получим такие данные, не хватит места на всех жестких дисках в мире, чтобы сохранить все эти вероятности. А если в кабинет войдет пациент с не встречавшимся ранее сочетанием симптомов, будет непонятно, как поставить ему диагноз. То есть мы столкнемся с давним врагом: комбинаторным взрывом.
Поэтому мы поступим так, как всегда стоит поступать: пойдем на компромисс. Нужно сделать упрощающие допущения, которые срежут количество подлежащих оценке вероятностей до уровня, с которым под силу справиться. Одно из простых и очень популярных допущений заключается в том, что все следствия данной причины независимы. Это значит, например, что наличие высокой температуры не влияет на вероятность кашля, если уже известно, что у больного грипп. Математически это значит, что P(температура, кашель | грипп) — просто P(температура | грипп) P(кашель | грипп). Получается, что и то и другое легко оценить на основании небольшого количества наблюдений. В предыдущем разделе мы уже сделали это для высокой температуры, и для кашля или любого другого симптома все будет так же. Необходимое количество наблюдений больше не растет экспоненциально с количеством симптомов. На самом деле оно вообще не растет.
Обратите внимание: речь идет о том, что высокая температура и кашель независимы не в принципе, а только при условии, что у больного грипп. Если неизвестно, есть грипп или нет, температура и кашель будут очень сильно коррелировать, поскольку вероятность кашля при высокой температуре намного выше. P(температура, кашель) не равно P(температура) P(кашель). Смысл в том, что если уже известно, что у больного грипп, то информация о высокой температуре не даст никакой дополнительной информации о том, есть ли у него кашель. Аналогично, если вы видите, что звезды гаснут, но не знаете, должно ли взойти солнце, ваши ожидания, что небо прояснится, должны возрасти. Но если вы уже знаете, что восход неизбежен, гаснущие звезды не важны.
Следует отметить, что такой фокус можно проделать только благодаря теореме Байеса. Если бы мы хотели прямо оценить P(грипп | температура, кашель и так далее) без предварительного преобразования с помощью теоремы в P(температура, кашель и так далее | грипп), по-прежнему требовалось бы экспоненциальное число вероятностей, по одной для каждого сочетания «симптомы — грипп / не грипп».
Алгоритм машинного обучения, который применяет теорему Байеса и исходит из того, что следствия данной причины независимы, называется наивный байесовский классификатор. Дело в том, что такое допущение, прямо скажем, довольно наивное: в реальности температура увеличивает вероятность кашля, даже если уже известно, что у больного грипп, потому что она, например, повышает вероятность тяжелого гриппа. Однако машинное обучение — это искусство безнаказанно делать ложные допущения, а как заметил статистик Джордж Бокс, «все модели неверны, но некоторые полезны». Чрезмерно упрощенная модель, для оценки которой у вас есть достаточно данных, лучше, чем идеальная, для которой данных нет. Просто поразительно, насколько ошибочны и одновременно полезны бывают некоторые модели. Экономист Милтон Фридман в одном очень влиятельном эссе даже утверждал, что чрезмерно упрощенные теории — лучшие, при условии, что они дают точные предсказания: они объясняют больше с наименьшими усилиями. По-моему, это перебор, однако это хорошая иллюстрация того, что, вопреки Эйнштейну, наука часто развивается по принципу «упрощай до тех пор, пока это возможно, а потом упрости еще немного».
Точно неизвестно, кто изобрел наивный байесовский алгоритм. Он был упомянут без автора в 1973 году в учебнике по распознаванию паттернов, но распространение получил лишь в 1990-е, когда исследователи заметили, что, как ни странно, он часто бывает точнее, чем намного более сложные обучающиеся алгоритмы. В то время я был старшекурсником. Запоздало решил включить наивный байесовский алгоритм в свои эксперименты и был шокирован, потому что оказалось, что он работает лучше, чем все другие, которые я сравнивал. К счастью, было одно исключение — алгоритм, который я разрабатывал для дипломной работы, — иначе, наверное, я не писал бы эти строки.
Наивный байесовский алгоритм сейчас спользуется очень широко: на нем основаны, например, многие спам-фильтры. Это применение придумал Дэвид Хекерман, выдающийся ученый-байесовец, врач. Ему пришла в голову мысль, что к спаму надо относиться как к заболеванию, симптомы которого — слова в электронном письме. «Виагра» — это симптом, и «халява» тоже, а имя лучшего друга, вероятно, указывает, что письмо настоящее. Затем можно использовать наивный байесовский алгоритм для классификации писем на спам и не-спам, но только при условии, что спамеры генерируют свои письма путем произвольного выбора слова. Это, конечно, странное допущение, которое было бы верно, не будь у предложений ни синтаксиса, ни содержания. Но тем же летом Мехран Сахами[87], тогда еще студент Стэнфорда, попробовал применить этот подход во время стажировки в Microsoft Research, и все отлично сработало. Когда Билл Гейтс спросил Хекермана, как это может быть, тот ответил, что для выявления спама вникать в подробности сообщения не обязательно: достаточно просто уловить суть, посмотрев, какие слова оно содержит.
В простейших поисковых системах алгоритмы, довольно похожие на наивный байесовский, используются, чтобы определить, какие сайты выдавать в ответ на запрос. Основное различие в том, что вместо классификации на спам и не спам нужно определить, подходит сайт к запросу или не подходит. Список проблем прогнозирования, к которым был применен наивный байесовский алгоритм, можно продолжать бесконечно. Питер Норвиг, директор по исследованиям в Google, как-то рассказал, что у них этот подход используется шире всего, а ведь Google применяет машинное обучение везде где только можно. Несложно догадаться, почему наивный Байес приобрел в Google такую популярность. Даже не говоря о неожиданной точности, он позволяет легко увеличить масштаб. Обучение наивного байесовского классификатора сводится к простому подсчету, сколько раз каждый атрибут появляется с каждым классом, а это едва ли занимает больше времени, чем считывание данных с диска.
Наивный байесовский алгоритм в шутку можно использовать даже в большем масштабе, чем Google, и смоделировать с его помощью всю Вселенную. Действительно, если верить в существование всемогущего бога, можно создать модель Вселенной как обширного распределения, где все происходит независимо при условии божьей воли. Ловушка, конечно, в том, что божественный разум нам недоступен, но в главе 8 мы узнаем, как получать наивные байесовские модели, даже не зная классов примеров.
Поначалу может показаться, что это не так, но наивный байесовский алгоритм тесно связан с перцептронами. Перцептрон добавляет веса, а байесовский алгоритм умножает вероятности, но, если логарифмировать, последнее сведется к первому. И то и другое можно рассматривать как обобщение простых правил «Если…, то…», где каждый предшественник может вносить больший или меньший вклад в вывод, вместо подхода «все или ничего». Этот факт — еще один пример глубокой связи между алгоритмами машинного обучения и намек на существование Верховного алгоритма. Вы можете не знать теорему Байеса (хотя теперь уже знаете), но в какой-то степени каждый из десяти миллиардов нейронов в вашем мозге — это ее крохотный частный случай.
Наивный байесовский алгоритм — хорошая концептуальная модель обучающегося алгоритма для чтения прессы: улавливает попарные корреляции между каждым из входов и выходов. Но машинное обучение, конечно, не просто парные корреляции, не в большей степени, чем мозг — это нейрон. Настоящее действие начинается, если посмотреть на более сложные паттерны.
От «Евгения Онегина» до Siri
В преддверии Первой мировой войны русский математик Андрей Марков опубликовал статью, где вероятности применялись, помимо всего прочего, к поэзии. В своей работе он моделировал классику русской литературы — пушкинского «Евгения Онегина» — с помощью подхода, который мы сейчас называем цепью Маркова. Вместо того чтобы предположить, что каждая буква сгенерирована случайно, независимо от остальных, Марков ввел абсолютный минимум последовательной структуры: допустил, что вероятность появления той или иной буквы зависит от буквы, непосредственно ей предшествующей. Он показал, что, например, гласные и согласные обычно чередуются, поэтому, если вы видите согласную, следующая буква (если игнорировать знаки пунктуации и пробелы) с намного большей вероятностью будет гласной, чем если бы буквы друг от друга не зависели. Может показаться, что это невеликое достижение, но до появления компьютеров требовалось много часов вручную подсчитывать символы, и идея была довольно новой. Если гласнаяi — это булева переменная, которая верна, если i-я по счету буква «Евгения Онегина» — гласная, и неверна, если она согласная, можно представить модель Маркова как похожий на цепочку график со стрелками между узлами, указывающими на прямую зависимость между соответствующими переменными:
Марков сделал предположение (неверное, но полезное), что в каждом месте текста вероятности одинаковы. Таким образом нам нужно оценить только три вероятности: P(гласная1 = верно); P(гласнаяi+1 = верно | гласнаяi = верно) и P(гласнаяi+1 = верно | гласнаяi = верно). (Поскольку сумма вероятностей равна единице, из этого можно сразу получить P(гласная1 = ложно) и так далее.) Как и в случае наивного байесовского алгоритма, переменных можно взять сколько угодно, не опасаясь, что число вероятностей, которые надо оценить, пробьет потолок, однако теперь переменные зависят друг от друга.
Если измерять не только вероятность гласных в зависимости от согласных, но и вероятность следования друг за другом для всех букв алфавита, можно поиграть в генерирование новых текстов, имеющих ту же статистику, что и «Евгений Онегин»: выбирайте первую букву, потом вторую, исходя из первой, и так далее. Получится, конечно, полная чепуха, но, если мы поставим буквы в зависимость от нескольких предыдущих букв, а не от одной, текст начнет напоминать скорее бессвязную речь пьяного — местами разборчиво, хотя в целом бессмыслица. Все еще недостаточно, чтобы пройти тест Тьюринга, но модели вроде этой — ключевой компонент систем машинного перевода, например Google Translate, которые позволяют увидеть весь интернет на английском (или почти английском), независимо от того, на каком языке написана исходная страница.
PageRank — алгоритм, благодаря которому появился Google, — тоже представляет собой марковскую цепь. Идея Ларри Пейджа заключалась в том, что веб-страницы, к которым ведут много ссылок, вероятно, важнее, чем страницы, где их мало, а ссылки с важных страниц должны сами по себе считаться больше. Из-за этого возникает бесконечная регрессия, но и с ней можно справиться с помощью цепи Маркова. Представьте, что человек посещает один сайт за другим, случайно проходя по ссылкам. Состояния в этой цепи Маркова — это не символы, а веб-страницы, что увеличивает масштаб проблемы, однако математика все та же. Суммой баллов страницы тогда будет доля времени, которую человек на ней проводит, либо вероятность, что он окажется на этой странице после долгого блуждания вокруг нее.
Цепи Маркова появляются повсюду, это одна из самых активно изучаемых тем в математике, но это все еще сильно ограниченная разновидность вероятностных моделей. Сделать шаг вперед можно с помощью такой модели:
Состояния, как и ранее, образуют марковскую цепь, но мы их не видим, и надо вывести их из наблюдений. Это называется скрытой марковской моделью, сокращенно СММ (название немного неоднозначное, потому что скрыта не модель, а состояния). СММ — сердце систем распознавания речи, например Siri. В задачах такого рода скрытые состояния — это написанные слова, наблюдения — это звуки, которые слышит Siri, а цель — определить слова на основе звуков. В модели есть два элемента: вероятность следующего слова при известном текущем, как в цепи Маркова, и вероятность услышать различные звуки, когда произносят слово. (Как именно сделать такой вывод — интересная проблема, к которой мы обратимся после следующего раздела.)
Кроме Siri, вы используете СММ каждый раз, когда разговариваете по мобильному телефону. Дело в том, что ваши слова передаются по воздуху в виде потока битов, а биты при передаче искажаются. СММ определяет, какими они должны быть (скрытые состояния), на основе полученных данных (наблюдений), и, если испортилось не слишком много битов, у нее обычно все получается.
Скрытая марковская модель — любимый инструмент специалистов по вычислительной биологии. Белок представляет собой последовательность аминокислот, а ДНК — последовательность азотистых оснований. Если мы хотим предсказать, например, в какую трехмерную форму сложится белок, можно считать аминокислоты наблюдениями, а тип складывания в каждой точке — скрытым состоянием. Аналогично можно использовать СММ для определения мест в ДНК, где инициируется транскрипция генов, а также многих других свойств.
Если состояния и наблюдения — не дискретные, а непрерывные переменные, СММ превращается в так называемый фильтр Калмана[88]. Экономисты используют эти фильтры, чтобы убрать шум из временных рядов таких величин, как внутренний валовой продукт (ВВП), инфляция и безработица. «Истинные» значения ВВП — это скрытые состояния. На каждом временном отрезке истинное значение должно быть схоже и с наблюдаемым, и с предыдущим истинным значением, поскольку в экономике резкие скачки встречаются нечасто. Фильтр Калмана находит компромисс между этими условиями и позволяет получить более гладкую, но соответствующую наблюдениям кривую. Кроме того, фильтры Калмана не дают ракетам сбиться с курса, и без них человек не побывал бы на Луне.
Все связано, но не напрямую
Скрытые марковские модели хорошо подходят для моделирования последовательностей всех видов, но им все еще очень далеко до гибкости символистских правил типа «если…, то…», где условием может быть все, а вывод может стать условием в любом последующем правиле. Однако если допустить такую произвольную структуру на практике, это приведет к взрывному росту количества вероятностей, которые нам надо определить. Ученые долго не могли справиться с этой квадратурой круга и прибегали к ситуативным схемам, например приписывали правилам оценочную достоверность и кое-как их соединяли. Если из A с достоверностью 0,8 следует B, а из B с достоверностью 0,7 вытекает C, то, наверное, C следует из A с достоверностью 0,8 0,7.
Проблема таких схем в том, что они могут приводить к сильным искажениям. Из двух совершенно разумных правил «если ороситель включен, трава будет мокрая» и «если трава мокрая, значит шел дождь» я могу вывести бессмысленное правило «если ороситель включен, значит шел дождь». Еще более коварная проблема заключается в том, что при применении правил с оценками достоверности одни и те же доказательства могут засчитываться дважды. Представьте, что вы читаете в New York Times сообщение о приземлении инопланетян. Не исключено, что это розыгрыш, хотя сегодня не первое апреля. Потом вы видите подобные заголовки в Wall Street Journal, USA Today и Washington Post и начинаете паниковать, как слушатели печально известной передачи Орсона Уэллса, которые приняли радиоспектакль «Война миров» за чистую монету[89]. Если, однако, вы обратите внимание на мелкий шрифт и поймете, что все четыре газеты получили новость от Associated Press, можно снова заподозрить розыгрыш, на этот раз со стороны репортера новостного агентства. Системы правил неспособны справиться с этой проблемой, равно как и наивный байесовский алгоритм: если в качестве предикторов того, что новость правдива, используются такие свойства, как «сообщила New York Times», он может только добавить «сообщило агентство Associated Press», а это лишь испортит дело.
Прорыв был сделан в начале 1980-х годов, когда Джуда Перл, профессор информатики в Калифорнийском университете в Лос-Анджелесе, изобрел новое представление — байесовские сети. Перл — один из самых заслуженных авторитетов в компьютерных науках, и его методы оставили отпечаток в машинном обучении, искусственном интеллекте и многих других дисциплинах. В 2012 году ему была присуждена премия Тьюринга.
Перл понял, что вполне допустимо иметь сложную сеть зависимостей между случайными переменными при условии, что каждая переменная прямо зависит только от нескольких других. Эти зависимости можно представить в виде графика, аналогичного тому, который мы видели при обсуждении цепей Маркова и СММ, однако теперь он может иметь любую структуру, если только стрелки не образуют замкнутые петли. Один из любимых примеров Перла — охранная сигнализация. Она должна сработать, если в дом пытается влезть грабитель, но может включиться и при землетрясении. (В Лос-Анджелесе, где живет Перл, землетрясения почти так же часты, как кражи со взломом.) Представьте, что вы засиделись на работе и вам позвонил сосед Боб, чтобы предупредить, что у вас сработала сигнализация. Соседка Клэр не звонит. Надо ли звонить в полицию? Вот график зависимостей:
Если на этом графике есть стрелка от одного узла к другому, мы говорим, что первый узел — родительский для второго. Следовательно, родители узла «Сигнализация» — «Взлом» и «Землетрясение», а «Сигнализация» будет единственным родителем узлов «Звонок Боба» и «Звонок Клэр». Байесовская сеть — это аналогичный график зависимостей, но каждой переменной присвоена табличка с ее вероятностью при всех сочетаниях ее родителей. У узлов «Взлом» и «Землетрясение» родителей нет, поэтому вероятность у них будет только одна. У «Сигнализации» их будет уже четыре: вероятность срабатывания, если нет ни взлома, ни землетрясения; вероятность срабатывания при взломе, но без землетрясения, и так далее. У узла «Звонок Боба» будут две вероятности (при наличии и отсутствии срабатывания сигнализации), и то же самое для звонка Клэр.
Это ключевой момент. Звонок Боба зависит от узлов «Взлом» и «Землетрясение», но только посредством узла «Сигнализация», то есть условно независим от взлома и землетрясения при условии срабатывания сигнализации, и то же самое с Клэр. Если сигнализация не сработала, соседи будут крепко спать и грабитель спокойно cделает свое дело. Также при условии срабатывания сигнализации звонки Боба и Клэр будут независимы друг от друга. Если бы этой структуры независимости не было, пришлось бы определить 25 = 32 вероятности, по одной для каждого возможного состояния пяти переменных. (Или 31, если вы педант, поскольку последнюю можно оставить неявной.) Если ввести условную независимость, останется определить всего 1 + 1 + 4 + 2 + 2 = 10 вероятностей, то есть экономия составит 68 процентов. И это только в этом маленьком примере. Когда переменных сотни и тысячи, экономия может приближаться к 100 процентам.
Первый закон экологии, согласно биологу Барри Коммонеру, заключается в том, что все взаимосвязано. Может быть, это действительно так, но в таком случае мир был бы непостижим, если бы не спасительная условная независимость: все связано, но лишь косвенно. Если что-то происходит на расстоянии километра, повлиять на меня это может только посредством чего-нибудь в моем соседстве, пусть даже это будут световые лучи. Как заметил один шутник, благодаря пространству с нами происходит не все сразу. Иначе говоря, структура пространства — это частный случай условной независимости.
В примере с ограблением полная таблица из 32 вероятностей не представлена явно, но она содержится в наборе меньших таблиц и структуре графа. Чтобы получить P(взлом, землетрясение, сигнализация, звонок Боба, звонок Клэр), нужно только перемножить P(взлом), P(землетрясение), P(сигнализация | взлом, землетрясение), P(звонок Боба | сигнализация) и P(звонок Клэр | сигнализация). То же самое в любой байесовской ети: чтобы получить вероятность полного состояния, просто перемножьте вероятности соответствующих линий в таблицах отдельных переменных. Поэтому при условной независимости информация не теряется из-за перехода на более компактное представление, и можно легко вычислить вероятности крайне необычных состояний, включая те, что до этого никогда не наблюдались. Байесовские сети показывают ошибочность расхожего мнения, будто машинное обучение неспособно предсказывать очень редкие события — «черных лебедей», как их называет Нассим Талеб.
Оглядываясь назад, можно заметить, что наивный байесовский алгоритм, цепи Маркова и СММ — это частные случаи байесовских сетей. Вот структура наивного Байеса:
Цепи Маркова кодируют допущение, что будущее условно независимо от прошлого при известном настоящем, а СММ дополнительно предполагает, что каждое наблюдение зависит только от соответствующего состояния. Байесовские сети для байесовцев — то же самое, что логика для символистов: лингва франка[90], который позволяет элегантно кодировать головокружительное разнообразие ситуаций и придумывать алгоритмы, которые будут работать в каждой из них.
Байесовские сети можно воспринимать как «порождающую модель», рецепт вероятностного генерирования состояния мира: сначала надо независимо решить, что произошло — взлом и/или землетрясение, — затем, исходя из этого, понять, срабатывает ли сигнализация, а затем, на этой основе, звонят ли Боб и Клэр. Байесовская сеть как будто рассказывает историю: происходит A, которое ведет к B. Одновременно с B происходит C, и вместе они вызывают D. Чтобы вычислить вероятность конкретной истории, надо просто перемножить все вероятности в разных ее цепочках.
Одна из самых потрясающих областей применения байесовских сетей — моделирование взаимной регуляции генов в клетке. Попытки открыть парные корреляции между конкретными генами и заболеваниями стоили миллиарды долларов, но дали обидно скромные результаты. Теперь это не удивляет — ведь поведение клетки складывается из сложнейших взаимодействий между генами и средой, и единичный ген имеет ограниченную прогностическую силу. Однако благодаря байесовским сетям мы можем открыть эти взаимодействия при условии, что в нашем распоряжении имеются необходимые данные, а с распространением ДНК-микрочипов данных появляется все больше.
После новаторского применения машинного обучения для фильтрации спама Дэвид Хекерман решил попробовать использовать байесовские сети в борьбе со СПИДом. ВИЧ — сильный противник. Он очень быстро мутирует, поэтому к нему сложно подобрать вакцину и надолго сдержать его с помощью лекарств. Хекерман заметил, что это те же кошки-мышки, как между спамом и фильтрами, и решил применить аналогичный прием: атаковать самое слабое звено. В случае спама слабыми звеньями были в том числе URL, которые приходится использовать для приема платежа от клиента. В случае ВИЧ ими оказались небольшие участки вирусного белка, которые не могут меняться без ущерба для вируса. Если бы получилось натренировать иммунную систему узнавать такие области и атаковать содержащие их клетки, было бы несложно разработать вакцину от СПИДа. Хекерман и его коллеги использовали байесовскую сеть, чтобы выявить эти уязвимые области, и разработали механизм доставки вакцины, которая способна научить иммунную систему атаковать их. Система работает у мышей, и в настоящее время готовятся клинические исследования.
Часто бывает, что даже после того, как все условные независимости учтены, у некоторых узлов байесовской сети все равно остается слишком много родителей. В некоторых сетях так густо от стрелок, что, если их распечатать, страница будет черной (физик Марк Ньюман называет их «абсурдограммы»). Врачу нужно одновременно диагностировать все возможные у пациента заболевания, а не только одно, а каждая болезнь — это родительский узел многих симптомов. Высокая температура может быть вызвана не только гриппом, а любым количеством состояний, и совершенно безнадежно пытаться предсказать ее вероятность при каждом возможном их сочетании. Но не все потеряно. Вместо таблицы, в которой указаны условные вероятности узла для каждого состояния родителей, можно получить более простое распределение. Самый популярный вариант — это вероятностная версия операции «логическое ИЛИ»: любая причина сама по себе может вызвать высокую температуру, но каждая причина с определенной вероятностью этого не сделает, даже если обычно ее достаточно. Хекерман и другие обучили байесовские сети, которые диагностируют таким образом сотни инфекционных заболеваний, а Google применяет гигантские сети такого рода в AdSense — системе автоматического подбора рекламы для размещения на веб-страницах. Сети связывают миллионы относящихся к контенту переменных друг с другом и с 12 миллионами слов и фраз более чем 300 миллионами стрелок, каждая из которых получена на основе сотни миллиардов отрывков текстов и поисковых запросов.
Более веселый пример — сервис Microsoft Xbox Live, в котором байесовская сеть используется для оценки игроков и подбора игроков схожего уровня. Результат игры — вероятностная функция уровня навыков противника, и благодаря теореме Байеса можно сделать вывод о навыках игрока на основании его побед и поражений.
Проблема логического вывода
Во всем этом есть, к сожалению, большая загвоздка. Само то, что байесовская сеть позволяет компактно представлять вероятностное распределение, еще не означает, что с ее помощью можно эффективно рассуждать. Представьте, что вы хотите вычислить P(взлом | звонок Боба, нет звонка Клэр). Из теоремы Байеса вы знаете, что это просто P(взлом) P(звонок Боба, нет звонка Клэр | взлом) / P(звонок Боба, нет звонка Клэр), или, эквивалентно, P(взлом, звонок Боба, нет звонка Клэр) / P(звонок Боба, нет звонка Клэр). Если бы в нашем распоряжении была полная таблица вероятностей всех состояний, можно было бы вычислить обе эти вероятности, сложив соответствующие строки в таблице. Например, P(звонок Боба, нет звонка Клэр) — это сумма вероятностей во всех линейках, где Боб звонит, а Клэр не звонит. Но байесовская сеть не дает полной таблицы. Ее всегда можно построить на основе отдельных таблиц, но необходимое для этого время и пространство растет экспоненциально. На самом деле мы хотим вычислить P(взлом | звонок Боба, нет звонка Клэр) без построения полной таблицы. К этому, в сущности, сводится проблема логического вывода в байесовских сетях.
Во многих случаях удается это сделать и без экспоненциального взрыва. Представьте, что вы командир отряда, который колонной по одному глубокой ночью пробирается по вражеским тылам. Надо убедиться, что никто не отстал и не потерялся. Можно остановиться и всех пересчитать, но нет времени. Более разумное решение — спросить идущего за вами солдата, сколько за ним человек. Солдаты будут задавать тот же самый вопрос по цепочке друг другу, пока последний не скажет: «Никого нет». Теперь предпоследний солдат может сказать: «один», — и так далее обратно к голове колонны, и каждый солдат будет добавлять единицу к количеству за ним. Так вы узнаете, сколько солдат за вами идет, и останавливаться не придется.
В Siri та же самая идея используется, чтобы по звукам, которые она улавливает микрофоном, вычислить вероятность, что вы сказали, например, «позвони в полицию». Эту фразу можно считать отрядом слов, марширующих друг за другом по странице. Слово «полиция» хочет знать вероятность своего появления, но для этого ему надо определить вероятность «в», а предлог, в свою очередь, должен узнать вероятность слова «позвони». Поэтому «позвони» вычисляет собственную вероятность и передает ее предлогу «в», который делает то же самое и передает результат слову «полиция». Теперь «полиция» знает свою вероятность, на которую повлияли все слова в предложении, и при этом не надо составлять полную таблицу из восьми вероятностей (первое слово «позвони» или нет, второе слово «в» или нет, третье слово «полиция» или нет). В реальности Siri учитывает все слова, которые могли бы появиться в каждой позиции, а не просто стоит ли первым слово «позвони» и так далее, однако алгоритм тот же самый. Наверное, Siri слышит звуки и предполагает, что первое слово либо «позвони», либо «позови», второе либо «в», либо «к», а третье — либо «полицию», либо «позицию». Может быть, по отдельности самые вероятные слова — это «позови», «к» и «позицию». Но тогда получится бессмысленное предложение: «Позови к позицию». Поэтому, принимая во внимание другие слова, Siri делает вывод, что на самом деле предложение — «Позвони в полицию». Программа звонит, и, к счастью, полицейские успевают вовремя и ловят забравшегося к вам вора.
Та же идея работает и в случае, если граф[91] представляет собой не цепь, а дерево. Если вместо взвода вы командуете целой армией, то можете спросить каждого ротного, сколько солдат за ним идет, а потом сложить их ответы. Каждый командир роты, в свою очередь, спросит своих взводных и так далее. Но если граф образует петлю, у вас появятся проблемы. Допустим, какой-то офицер-связной входит сразу в два взвода. Тогда два раза посчитают не только его самого, но и всех идущих за ним солдат. Именно это произойдет в примере с высадкой инопланетян, если вы захотите вычислить, скажем, вероятность паники:
Одно из решений — соединить «Сообщение в New York Times» и «Сообщение в Wall Street Journal» в одну мегапеременную с четырьмя значениями: «ДаДа», если сообщают оба источника, «ДаНет», если о приземлении сообщает New York Times, но не Wall Street Journal, и так далее. Это превратит граф в цепочку из трех переменных, и все хорошо. Однако с добавлением каждого нового источника новости число значений в мегапеременной будет удваиваться. Если вместо двух источников у вас целых 50, мегапеременная получит 250 значений. Поэтому такой метод на большее не способен, а ничего лучше не придумали.
Проблема сложнее, чем может показаться на первый взгляд, потому что у байесовских сетей появляются «невидимые» стрелки, идущие вместе с видимыми. «Взлом» и «землетрясение» априорно независимы, но сработавшая сигнализация их связывает: она заставляет подозревать ограбление. Но если вы услышите по радио, что было землетрясение, то начнете предполагать, что оно и виновато. Землетрясение оправдывает срабатывание сигнализации и делает ограбление менее вероятным, а следовательно, между ними появляется зависимость. В байесовской сети все родители той же переменной таким образом оказываются взаимозависимы, что, в свою очередь, порождает еще больше зависимостей, и результирующий граф часто получается намного плотнее, чем исходный.
Критически важный вопрос для логического вывода: можно ли сделать заполненный график «похожим на дерево», чтобы ствол при этом был не слишком толстый. Если у мегапеременной в стволе слишком много возможных значений, дерево будет расти бесконтрольно, пока не заполонит всю планету, как баобабы в «Маленьком принце». В древе жизни каждый вид — это ветвь, но внутри каждой ветви есть граф, где у каждого создания имеются двое родителей, четыре внука, какое-то количество потомков и так далее. «Толщина» ветви — это размер популяции данного вида. Если ветви слишком толстые, единственный выбор — прибегнуть к приближенному выводу.
Одно из решений, приведенное Перлом в качестве упражнения в его книге о байесовских сетях, — делать вид, что в графе нет петель, и продолжать распространять вероятности туда-сюда, пока они не сойдутся. Такой алгоритм известен как циклическое распространение доверия. Вообще говоря, идея странная, но, как оказалось, во многих случаях она довольно хорошо работает. Например, это один из современных методов беспроводной связи, где случайные переменные — хитрым образом закодированные биты сообщения. Но циклическое распространение доверия может сходиться и к неправильным ответам или бесконечно изменяться (осциллировать). Еще одно решение проблемы возникло в физике, было импортировано в машинное обучение и значительно расширено Майклом Джорданом и другими учеными. Оно заключается в том, чтобы приблизить неразрешимое распределение с помощью разрешимого, оптимизировать параметры последнего и как можно ближе приблизить его к первому.
Но самый популярный вариант — утопить наши печали в вине и бродить всю ночь пьяным. По-научному это называется метод Монте-Карло в марковских цепях, или сокращенно MCMC. «Монте-Карло» потому, что в методе есть шансы, как в казино в одноименном городе, а марковские цепи упоминаются потому, что в этот метод входит последовательность шагов, каждый из которых зависит только от предыдущего. Идея MCMC заключается в том, чтобы совершать случайные прогулки, как упомянутый пьяница, перепрыгивая из одного состояния сети в другое таким образом, чтобы в долгосрочной перспективе число посещений каждого состояния было пропорционально вероятности этого состояния. Затем мы можем оценить вероятность взлома, скажем, как долю посещений состояния, в котором происходит ограбление. Удобная для анализа цепь Маркова сводится к стабильному распределению и через какое-то время начинает давать приблизительно те же ответы. Например, если вы тасуете колоду карт, через какое-то время все порядки карт станут одинаково вероятными, независимо от исходного порядка, поэтому вы будете знать, что при n возможных вариантов вероятность каждого из них будет равна 1n. Весь фокус в MCMC заключается в том, чтобы разработать цепь Маркова, которая сходится к распределению нашей байесовской сети. Простой вариант — многократно циклически проходить через переменные, делая выборку каждой в соответствии с ее условной вероятностью, исходя из состояния соседей. Люди часто говорят об MCMC как о своего рода симуляции, но это не так: цепь Маркова не имитирует какой-то реальный процесс — скорее, она придумана для того, чтобы эффективно генерировать примеры из байесовской сети, которая сама по себе не является последовательной моделью.
Истоки MCMC восходят к Манхэттенскому проекту, в котором физики оценивали вероятность столкновения нейтронов с атомами, вызывающего цепную реакцию. В последующие десятилетия метод произвел такую революцию, что его часто называют одним из самых важных алгоритмов всех времен. MCMC хорош не только для вычисления вероятностей, но и для интегрирования любых функций. Без него ученые были бы ограничены функциями, которые можно интегрировать аналитически, или низкоразмерными, удобными для анализа интегралами, которые можно приблизить методом трапеций. MCMC позволяет свободно строить сложные модели, делая всю трудную работу за вас. Байесовцы, со своей стороны, обязаны MCMC растущей популярностью своих методов, вероятно, больше, чем чему-то другому.
Отрицательный момент — то, что MCMC зачастую мучительно медленно сходится или начинает обманывать, потому что кажется, что он сошелся, а на самом деле нет. В реальных распределениях обычно очень много пиков, которые, как Эвересты, взлетают над широкой равниной крохотных вероятностей. Цепь Маркова, следовательно, будет сходиться к ближайшему пику и останется там, а оценка вероятности окажется очень пристрастной: как если бы пьяница учуял запах спиртного и завис на всю ночь в ближайшей забегаловке, вместо того чтобы бесцельно слоняться по городу, как нам нужно. С другой стороны, если вместо цепи Маркова сгенерировать независимые пробы, как в более простых методах Монте-Карло, никакого запаха не будет и, вероятно, наш пьяница даже не найдет первый кабак. Это все равно что бросать дротики в карту города, надеясь, что они попадут прямиком в паб.
Логический вывод в байесовских сетях не ограничен вычислением вероятностей. К нему относится и нахождение наиболее вероятного объяснения признаков, например заболевания, которое лучше всего объясняет симптомы, или слов, которые лучше всего объясняют звуки, услышанные Siri. Это не то же самое, что просто выбрать на каждом этапе самое вероятное слово, потому что слова, которые схожи по отдельности исходя из звуков, могут реже встречаться вместе, как в примере «Позови к позицю». Однако и в таких задачах срабатывают аналогичные виды алгоритмов (именно их использует большинство распознавателей речи). Самое главное, что вывод предусматривает принятие наилучших решений не только на основе вероятности разных исходов, но и с учетом соответствующих затрат (или, говоря научным языком, полезности). Затраты, связанные с проигнорированным письмом от начальника, который просит что-то сделать завтра, будут намного выше, чем затраты на ознакомление с ненужным рекламным письмом, поэтому часто целесообразно пропустить письма через фильтр, даже если они довольно сильно напоминают спам.
Беспилотные автомобили и другие роботы — показательный пример работы вероятностного вывода. Машина ездит туда-сюда, создает карту территории и все увереннее определяет свое положение. Согласно недавнему исследованию, у лондонских таксистов увеличиваются размеры задней части гиппокампа — области мозга, участвующей в создании карт и запоминании, — когда они учатся ориентироваться в городе. Наверное, здесь действуют аналогичные алгоритмы вероятностного вывода с той лишь важной разницей, что людям алкоголь, по-видимому, не помогает.
Учимся по-байесовски
Теперь, когда мы знаем, как (более-менее) решать проблему логического вывода, можно приступать к обучению байесовских сетей на основе данных, ведь для байесовцев обучение — это всего лишь очередная разновидность вероятностного вывода. Все что нужно — применить теорему Байеса, где гипотезы будут возможными причинами, а данные — наблюдаемым следствием:
P(гипотеза | данные) = P(гипотеза) P(данные | гипотеза) / P(данные).
Гипотеза может быть сложна, как целая байесовская сеть, или проста, как вероятность, что монетка упадет орлом вверх. В последнем случае данные — это просто результат серии подбрасываний. Если, скажем, мы получили 70 орлов в сотне подбрасываний, сторонник частотного подхода оценит, что вероятность выпадения орла составляет 0,7. Это оправдано так называемым принципом наибольшего правдоподобия: из всех возможных вероятностей орлов 0,7 — то значение, при котором вероятность увидеть 70 орлов при 100 подбрасываниях максимальна. Эта вероятность — P(данные | гипотеза), и принцип гласит, что нужно выбирать гипотезу, которая ее максимизирует. Байесовцы, однако, поступают разумнее. Они говорят, что никогда точно не известно, какая из гипотез верна, и поэтому нельзя просто выбирать одну гипотезу, например значение 0,7 для вероятности выпадения орла. Надо скорее вычислить апостериорную вероятность каждой возможной гипотезы и при прогнозировании учесть все. Сумма вероятностей должна равняться единице, поэтому, если какая-то гипотеза становится вероятнее, вероятность других уменьшается. Для байесовца на самом деле не существует такого понятия, как истина: есть априорное распределение гипотез, и после появления данных оно становится апостериорным распределением по теореме Байеса. Вот и все.
Это радикальный отход от традиционных научных методов. Все равно что сказать: «Вообще, ни Коперник, ни Птолемей не правы. Давайте лучше предскажем будущие траектории планет исходя из того, что Земля вращается вокруг Солнца, а потом — что Солнце вращается вокруг Земли, а результаты усредним».
Конечно, здесь речь идет о взвешенном среднем, где вес гипотезы — это ее апостериорная вероятность, поэтому гипотеза, которая лучше объясняет данные, будет иметь большее значение. Тем не менее ученые шутят, что быть байесовцем — значит никогда не говорить, что ты хоть в чем-то уверен.
Не стоит упоминать, что постоянно таскать за собой множество гипотез вместо одной тяжело. При обучении байесовской сети приходится делать предсказания путем усреднения всех возможных сетей, включая все возможные структуры графов и все возможные параметры значений для каждой структуры. В некоторых случаях можно вычислить среднее по параметрам в замкнутой форме, но с варьирующимися структурами такого везения ждать не приходится. Остается, например, применить MCMC в пространстве сетей, перепрыгивая из одной возможной сети к другой по ходу цепи Маркова. Соедините эту сложность и вычислительные затраты с неоднозначностью байесовской идеи о том, что объективной реальности вообще не существует, и вы поймете, почему в науке последние 100 лет доминирует частотный подход.
У байесовского метода есть, однако, спасительное свойство и ряд серьезных плюсов. В большинстве случаев апостериорная вероятность практически всех гипотез чрезвычайно мала и их можно спокойно проигнорировать: даже рассмотрение одной, наиболее вероятной гипотезы обычно дает очень хорошее приближение. Представьте, что наше априорное распределение для проблемы броска монетки заключается в том, что все вероятности орлов одинаково правдоподобны. После появления результатов последовательных подбрасываний распределение будет все больше и больше концентрироваться на гипотезе, которая лучше всего согласуется с данными. Например, если h пробегает по возможным вероятностям орлов, а монета падает орлом вверх в 70 процентах случаев, получится что-то вроде:
Апостериорная вероятность броска становится априорной для следующего броска, и, бросок за броском, мы все больше убеждаемся, что h = 0,7. Если просто взять одну наиболее вероятную гипотезу (в данном случае h = 0,7), байесовский подход станет довольно похож на частотный, но с одним очень важным отличием: байесовцы учитывают априорную P(гипотеза), а не просто вероятность P(данные | гипотеза). (Данные до P(данные) можно проигнорировать, потому что они одинаковы для всех гипотез и, следовательно, не влияют на выбор победителя.) Если мы хотим сделать допущение, что все гипотезы априори одинаково вероятны, байесовский подход сведется к принципу наибольшего правдоподобия. Поэтому байесовцы могут заявить сторонникам частотного подхода: «Смотрите, то, что вы делаете, — частный случай того, что делаем мы, но наши допущения хотя бы явные». А если гипотезы не одинаково правдоподобны априори, неявное допущение наибольшей правдоподобности заключается в том, что они ведут к неправильным ответам.
Это может показаться чисто теоретической дискуссией, но на самом деле ее практические последствия огромны. Если мы видели, что монету подбросили только один раз и выпал орел, принцип наибольшего правдоподобия подскажет, что вероятность выпадения орла должна быть равна единице. Это будет крайне неточно, и мы окажемся совершенно неподготовлены, если монетка упадет решкой. После многократных подбрасываний оценка станет надежнее, но во многих проблемах подбрасываний никогда не будет достаточно, как бы ни был велик объем данных. Представьте, что в наших обучающих данных слово «суперархиэкстраультрамегаграндиозно» никогда не появляется в спаме, но однажды встречается в письме про Мэри Поппинс. Спам-фильтр, основанный на наивном байесовском алгоритме с оценкой вероятности наибольшего правдоподобия, решит, что такое письмо не может быть спамом, пусть даже все остальные слова вопиют: «Спам! Спам!» Напротив, сторонник байесовского подхода дал бы этому слову низкую, но не нулевую вероятность появления в спаме, и в таком случае другие слова бы его перевесили.
Проблема лишь усугубится, если попытаться узнать и структуру байесовской сети, и ее параметры. Мы можем сделать это путем восхождения по выпуклой поверхности, начиная с пустой сети (без стрелок) и добавляя стрелки, которые больше всего увеличивают вероятность, пока ни одна из них не будет приводить к улучшению. К сожалению, это быстро вызовет очень сильное переобучение, и получится сеть, приписывающая нулевую вероятность всем состояниям, которые не появляются в данных. Байесовцы могут сделать нечто гораздо более интересное: использовать априорное распределение, чтобы закодировать экспертное знание о проблеме. Это их ответ на вопрос Юма. Например, можно разработать исходную байесовскую сеть для медицинской диагностики, опросив врачей, какие заболевания, по их мнению, вызывают те или иные симптомы, и добавить соответствующие срелки. Это «априорная сеть», и априорное распределение может штрафовать альтернативные сети по числу стрелок, которые они в нее добавляют или убирают. Тем не менее врачам свойственно ошибаться, и данным разрешено перевесить их мнение: если рост правдоподобия в результате добавления стрелки перевешивает штраф, она будет добавлена.
Конечно, сторонникам частотного подхода известно об этой проблеме, и у них есть свои решения: например, умножить правдоподобие на фактор, который штрафует более сложные сети. Но в этот момент частотный и байесовский подходы становятся неразличимыми, и как вы назовете функцию, подсчитывающую очки: «оштрафованным правдоподобием» или «апостериорной вероятностью», — просто дело вкуса.
Несмотря на то что частотный и байесовский типы мышления по некоторым вопросам сходятся, между ними остается философское различие в отношении значения вероятности. Многим ученым неприятно рассматривать его как нечто субъективное, хотя благодаря этому становятся возможными многие применения, которые в противном случае запрещены. Если вы сторонник частотного подхода, можно оценивать вероятности только тех событий, которые происходят более одного раза, и вопросы вроде «Какова вероятность, что Хиллари Клинтон победит Джеба Буша на следующих президентских выборах?» не имеют ответа, потому что еще не было выборов, в которых сошлись бы эти кандидаты. Для байесовца же вероятность — субъективная степень веры, поэтому он волен выдвигать обоснованные предположения, и анализ суждений делает все его предположения состоятельными.
Байесовский метод применим не только к обучению байесовских сетей и их частных случаев. (Наоборот, вопреки названию, байесовские сети не обязательно байесовские: сторонники частотного подхода тоже могут их обучать, как мы только что видели.) Можно применить априорное распределение к любому классу гипотез — наборам правил, нейронным сетям, программам, — а затем обновлять правдоподобие гипотез при получении данных. Байесовская точка зрения заключается в том, что вы можете выбирать представление, но затем его надо обучать с помощью теоремы Байеса. В 1990-х годах байесовцы произвели эффектный захват Конференции по системам обработки нейронной информации (Neural Information Processing Systems, NIPS) — главного мероприятия для коннекционистских исследований. Зачинщиками были Дэвид Маккей, Редфорд Нил и Майкл Джордан. Маккей, британец и студент Джона Хопфилда в Калифорнийском техническом университете, позднее ставший главным научным консультантом Департамента энергетики Великобритании, показал, как обучать по-байесовски многослойные перцептроны, Нил познакомил коннекционистов с MCMC, а Джордан — с вариационным выводом. Наконец, они указали, что в пределе можно «проинтегрировать» нейроны многослойного перцептрона, оставляя тип байесовской модели, которая на них не ссылается. Вскоре после этого слово «нейронный» в заголовках статей, поданных на конференцию по системам обработки нейронной информации, стало резко уменьшать шансы на публикацию. Некоторые шутили, что надо переименовать NIPS в BIPS — «Байесовские системы обработки информации».
Марков взвешивает доказательства
Байесовцы шли к мировому господству, но тут произошло нечто забавное. Ученые, пользующиеся байесовскими моделями, стали постоянно замечать, что результат получается лучше, если манипулировать вероятностями недозволенными методами. Например, возведение P(слова) в определенную степень улучшало точность распознавания речи, но тогда это переставало быть теоремой Байеса. Что произошло? Как оказалось, виновата ложная независимость допущений, которые делают порождающие модели. Благодаря упрощенной структуре графа модели становятся обучающимися и стоящими сохранения, но тогда больше даст простое получение наилучших параметров для имеющейся задачи, независимо от того, представляют ли они собой вероятности. Настоящая сила, скажем, наивного байесовского алгоритма заключается в том, что он дает небольшой информативный набор свойств, на основании которого можно предсказать класс, а также быстрый надежный способ узнать соответствующие параметры. В спам-фильтре каждое свойство — это частота определенного слова в спаме, а соответствующий параметр — то, как часто оно встречается. То же самое для не-спама. Если смотреть с этой точки зрения, наивный байесовский алгоритм может оказаться оптимальным в том смысле, что он делает лучшие возможные предсказания, причем зачастую там, где независимость допущений сильно нарушена. Когда я это понял и в 1996 году опубликовал статью на эту тему, подозрение к наивному Байесу уменьшилось и его популярность выросла. Но это стало шагом на пути к модели другого рода, которая в последние два десятилетия все больше вытесняет байесовские сети из машинного обучения, — к сетям Маркова.
Сеть Маркова — это набор свойств и соответствующих весов, которые вместе определяют распределение вероятности. Свойство может быть простое, например «это медленная песня», или сложное, например «это медленный хип-хоп с саксофонной импровизацией и нисходящим аккордовым пассажем». В сервисе Pandora используется большой набор свойств, который создатели называют Music Genome Project. Он помогает отобрать песни, которые вам стоит послушать. Представьте, что мы подключили ее к сети Маркова. Если вы любите медленные песни, веса соответствующих свойств пойдут вверх и вы с большей вероятностью будете слышать такую музыку, если включите Pandora. Если вы при этом любите исполнителей хип-хопа, вес этого свойства тоже вырастет. Песни, которые вы, скорее всего, услышите, теперь объединят обе черты: это будут медленные композиции в исполнении хип-хоперов. Если вы не любите медленные песни или хип-хоперов как таковых и вам нравится только их сочетание, понадобится более сложная черта — «медленная песня в исполнении хип-хопера». Свойства Pandora созданы вручную, но в сетях Маркова их можно получить путем восхождения на выпуклые поверхности, аналогично выведению правил. В любом случае хороший способ узнать веса — градиентный спуск.
Как и байесовские сети, сети Маркова можно представить в виде графов, но вместо стрелок будут ненаправленные дуги. Когда две переменные соединены, это значит, что они прямо зависят друг от друга, если появляются вместе в каком-то свойстве, как «медленная песня» и «песня в исполнении хип-хопера» в свойстве «медленная песня в исполнении хип-хопера».
Сети Маркова — базовая методика во многих областях, например компьютерном зрении. В частности, беспилотный автомобиль должен разделить любое увиденное изображение на дорогу, небо и окружающую местность. Один из вариантов — присвоить каждому пикселю, в зависимости от цвета, один из трех ярлыков, но этого совершенно недостаточно. Изображения очень зашумлены и разнообразны, поэтому у машины постоянно будут галлюцинации: разбросанные по всей дороге камни, куски дороги в небе. В то же время известно, что соседние пиксели на изображении обычно входят в один и тот же объект, и можно ввести соответствующий набор свойств: для каждой пары соседних пикселей свойство верно, если пиксели относятся к тому же самому объекту, и ложно, если это не так. Теперь изображения с крупными, сплошными блоками дороги и неба становятся намного более вероятными, чем изображения без них, и машина начинает ехать прямо, вместо того чтобы вилять то влево, то вправо, уворачиваясь от привидевшихся булыжников.
Сети Маркова можно обучить максимизировать либо правдоподобие всех данных, либо условную функцию правдоподобия того, что мы хотим предсказать, исходя из имеющихся знаний. Для Siri вероятность всех данных — это P(слова, звуки), а условное правдоподобие того, что нас интересует, — P(слова | звуки). Оптимизируя последнее, можно проигнорировать P(звуки), потому что оно только отвлекает от цели, и, если его не проигнорировать, оно может быть произвольно сложным. Это намного лучше, чем нереалистичное допущение СММ, что звуки зависят исключительно от соответствующих слов без какого-либо влияния среды. На самом деле Siri важно только понять, какие слова вы произнесли, и, наверное, даже не стоит беспокоиться о вероятностях: достаточно просто убедиться, что при подсчете весов свойств у правильных слов сумма пунктов будет больше, чем у неправильных. В идеале намного больше, просто для безопасности.
Как мы увидим в следующей главе, аналогизаторы довели эту линию рассуждения до логического завершения и в первом десятилетии нового тысячелетия завоевали конференцию NIPS. Коннекционисты еще раз взяли верх, теперь уже под знаменем глубокого обучения. Некоторые говорят, что наука развивается циклами, но она больше похожа на спираль вокруг вектора прогресса. Спираль машинного обучения сходится в Верховном алгоритме.
Логика и вероятность: несчастная любовь
Вы ошибаетесь, если думаете, что байесовцы и символисты отлично поладят, потому что и те и другие верят в теоретический, а не естественно-научный подход к обучению. Символисты не любят вероятностей и рассказывают анекдоты вроде «Сколько байесовцев нужно, чтобы поменять лампочку? Они сами точно не знают. Если подумать, они даже не уверены, перегорела ли лампочка». А если серьезно, символисты показывают, какую высокую цену приходится платить за вероятность. Логический вывод внезапно становится намного затратнее, все эти числа сложно понять, надо что-то делать с априорной информацией и постоянно убегать от полчищ гипотез-зомби. Пропадает столь милая сердцу символистов способность на лету складывать элементы знаний. Хуже всего то, что неизвестно, как применить распределение вероятностей ко многим проблемам, которые нам надо решить. Байесовская сеть — это распределение по вектору переменных. А что с распределениями по сетям, базам данных, базам знаний, языкам, планам, компьютерным программам и многому другому? Со всем этим легко справляется логика, и, раз алгоритм на это неспособен, это явно не Верховный алгоритм.
Байесовцы, в свою очередь, указывают на хрупкость логики. Если у меня есть правило вроде «Птицы летают», мир даже с одной нелетающей птицей невозможен. Если попытаться залатать все дыры исключениями, например «Птицы летают, если они не пингвины», их получится бесконечно много. (Что со страусами? С птицами в клетке? Мертвыми птицами? Птицами со сломанными крыльями? С промокшими крыльями?) Врач диагностирует рак, и больной решает проконсультироваться еще у одного специалиста. Если второй доктор не согласен с первым, ситуация заходит в тупик. Мнения нельзя взвесить, приходится просто верить обоим. В результате происходит катастрофа: свиньи летают, вечный двигатель возможен, а Земли не существует — потому что в логике из противоречий можно вывести что угодно. Более того, если знание получено из данных, никогда нельзя быть уверенным, что оно истинно. Почему символисты делают вид, что это не так? Юм, несомненно, не одобрил бы такую беззаботность.
Байесовцы и символисты соглашаются, что априорные допущения неизбежны, но расходятся в том, какое априорное знание разрешено. Для байесовцев знание выражается в априорном распределении по структуре и параметрам модели. Априорными параметрами в принципе может быть все что угодно, но, по иронии, байесовцы, как правило, выбирают неинформативные (например, приписывают всем гипотезам одну и ту же вероятность), потому что им так удобнее делать расчеты. И в любом случае люди не очень хорошо умеют оценивать вероятности. Что касается структуры, байесовские сети предполагают интуитивное инкорпорирование знаний: нарисуй стрелку из A в B, если думаешь, что A прямо вызывает B. Символисты намного гибче: можно дать алгоритму машинного обучения в качестве априорного знания все, что можно закодировать путем логики, а логикой можно закодировать практически все при условии, что это «все» — черно-белое.
Очевидно, что нужны и логика, и вероятности. Хороший пример — лечение рака. Байесовская сеть может моделировать отдельный аспект функционирования клеток, например регуляцию генов или фолдинг белка, но только логика может сложить фрагменты в связную картину. С другой стороны, логика не может работать с неполной или зашумленной информацией, которой очень много в экспериментальной биологии, а байесовские сети прекрасно с этим справляются.
Байесовское обучение работает на одной таблице данных, где столбцы представляют переменные (например, уровень экспрессии гена), а строки — случаи (например, наблюдаемый в отдельных экспериментах с микрочипом уровень экспрессии каждого гена). Ничего страшного, если в таблице есть «дыры» и ошибочные измерения, потому что можно применить вероятностный вывод, чтобы заполнить пробелы и сгладить ошибки путем усреднения. Но когда таблиц больше, байесовское обучение заходит в тупик. Оно не знает, например, как соединить данные об экспрессии генов с данными о том, какой сегмент ДНК кодирует белки, и как, в свою очередь, трехмерная форма этих белков заставляет их прикрепляться к разным частям молекулы ДНК, влияя на экспрессию других генов. В случае логики мы легко можем составить правила, связывающие все эти аспекты, и получить соответствующие комбинации таблиц, но только при условии, что в таблицах нет ошибок и белых пятен.
Соединить коннекционизм и эволюционизм довольно легко: просто эволюционируйте структуру сети и получите параметры путем обратного распространения ошибки. Объединить логику и вероятностный подход намного сложнее. Попытки решить эту проблему предпринимал еще Лейбниц, который был пионером в обеих областях, а после него — лучшие философы и математики XIX и XX века, например Джордж Буль и Рудольф Карнап. Несмотря на все усилия, результаты были очень скромными. Позднее в бой вступили информатики и исследователи искусственного интеллекта, но к началу нового тысячелетия они достигли лишь частичных успехов, например, к байесовским сетям добавили логические конструкты. Большинство экспертов были убеждены, что объединить логику и вероятности вообще невозможно. Перспективы создания Верховного алгоритма выглядели неважно, особенно потому, что существовавшие тогда эволюционистские и коннекционистские алгоритмы тоже не могли справиться с неполной информацией и множественными наборами данных.
К счастью, с тех пор мы продвинулись вперед на пути к решению проблемы, и сегодня Верховный алгоритм кажется намного ближе. Решение мы увидим в главе 9, но сначала надо подобрать все еще недостающую очень важную часть мозаики: как учиться, если данных очень мало. Здесь вступает в игру одна из самых важных идей в машинном обучении: аналогия. У всех «племен», которые мы до сих пор встретили, есть одна общая черта: они получают явную модель рассматриваемого явления, будь то набор правил, многослойный перцептрон, генетическая программа или байесовская сеть. Если у них для этого недостаточно данных, они заходят в тупик. А аналогизаторам для обучения достаточно всего одного примера, потому что они модели не формируют. Давайте посмотрим, чем они вместо этого занимаются.
ГЛАВА 7
ТЫ — ТО, НА ЧТО ТЫ ПОХОЖ
Фрэнк Абигнейл-младший — один из самых знаменитых мошенников в истории, Леонардо Ди Каприо сыграл его в фильме Спилберга «Поймай меня, если сможешь». Абигнейл подделывал чеки на миллионы долларов, прикидывался адвокатом и преподавателем колледжа, путешествовал по миру, выдавая себя за пилота Pan Am, и все это когда ему еще не исполнился 21 год. Но, наверное, самая сногсшибательная его проделка — это когда он в конце 1960-х почти год успешно изображал врача в Атланте. Казалось бы, чтобы заниматься медициной, нужно много лет учиться в медицинском институте, пройти ординатуру, получить лицензию и так далее, но Абигнейлу удалось обойти эти мелочи, и все были довольны.
Представьте на секунду, что вам предстоит провернуть нечто подобное. Вы тайком пробираетесь в пустой медицинский кабинет. Вскоре появляется пациент и рассказывает вам о своих симптомах. Надо поставить ему диагноз, только вот в медицине вы ничего не смыслите. В вашем распоряжении — шкаф с историями болезней: симптомы, диагнозы, назначенное лечение и так далее. Как вы поступите? Самое простое — это заглянуть в документы, поискать пациента с самыми похожими симптомами и поставить такой же диагноз. Если вы умеете вести себя с больным и убедительно говорить, как Абигнейл, этого может оказаться достаточно для успеха. Та же идея успешно применяется и за пределами медицины. Если вы молодой президент и столкнулись с мировым кризисом, как в свое время Кеннеди, когда самолет-разведчик обнаружил на Кубе советские ядерные ракеты, вполне вероятно, что готового сценария у вас не окажется. Вместо этого можно поискать похожие примеры в истории и попытаться сделать из них выводы. Объединенный комитет начальников штабов подталкивал президента напасть на Кубу, но Кеннеди только что прочитал The Guns of August[92] — бестселлер о начале Первой мировой войны — и хорошо осознавал, что такой шаг легко может вылиться в тотальную войну. Кеннеди предпочел морскую блокаду — и, может быть, спас мир от ядерной катастрофы.
Читать бесплатно другие книги:
