Текст книги "Верховный алгоритм: как машинное обучение изменит наш мир"

Точность, которой можно доверять

На практике анализ по Вэлианту обычно дает очень пессимистичные результаты и требует больше данных, чем есть в наличии. Как же решить, верить ли обучающемуся алгоритму? Все просто: не верьте, пока не проверите результаты на данных, которые обучающийся алгоритм не видел. Если схемы, выдвинутые им в качестве гипотезы, окажутся верны и для новых данных, можно быть уверенным, что они реальные. В противном случае вы будете знать, что имело место переобучение. Это просто применение научного метода к машинному обучению: новой теории мало объяснить прошлый опыт (такую состряпать несложно) – она должна также делать новые предсказания, а принимают ее только после того, как предсказания были экспериментально подтверждены. (И даже тогда лишь предварительно, потому что будущие данные по-прежнему могут ее фальсифицировать.)

Общая теория относительности Эйнштейна стала общепринятой, только когда Артур Эддингтон эмпирически подтвердил, что Солнце отклоняет свет далеких звезд. Но вам не надо ждать, пока поступят новые данные, чтобы решить, можно ли доверять алгоритму машинного обучения. Лучше взять все данные, которые у вас есть, и произвольно разделить их на обучающее множество, которое вы дадите алгоритму, и тестовое множество, которое надо cпрятать от него и использовать для верификации точности. Точность на скрытых данных – золотой стандарт в машинном обучении. Можно написать статью о том, какой прекрасный новый обучающийся алгоритм вы придумали, но, если на скрытых данных он значительно не превосходит уже имеющиеся, статью никто не опубликует.

Точность на данных, которые алгоритм еще не видел, – настолько строгий критерий, что многие научные теории его не проходят. От этого они не становятся бесполезными, ведь наука – это не только предсказания, но и объяснение и понимание, однако в итоге, если модели не делают точных прогнозов на новых данных, нельзя быть уверенным, что лежащие в основе явления по-настоящему поняты и объяснены. А для машинного обучения тестирование на скрытых данных незаменимо, потому что это единственный способ определить, случилось ли с обучающимся алгоритмом переобучение.

Но и точность на тестовой выборке не гарантия от ошибок. Согласно легенде, один из ранних простых обучающихся алгоритмов со стопроцентной точностью отличал танки и в обучающей, и в тестовой выборке, каждая из которых состояла из 100 изображений. Удивительно или подозрительно? Оказалось, что все картинки с танками были светлее, и это все, что увидел обучающийся алгоритм. В наши дни выборки данных крупнее, но качество сбора данных не обязательно лучше, поэтому нельзя терять бдительность. Реалистичная эмпирическая оценка сыграла важную роль в превращении машинного обучения из молодой дисциплины в зрелую науку. До конца 1980‑х исследователи каждого из «племен» в основном верили собственным аргументам, исходили из того, что их парадигма фундаментально лучше, и мало общались с другими лагерями. Затем символисты, например Рэй Муни и Джуд Шавлик, начали систематически сравнивать разные алгоритмы на тех же наборах данных, и – вот сюрприз! – оказалось, что однозначного победителя нет. Сегодня соперничество продолжается, но перекрестное опыление встречается гораздо чаще. Общие экспериментальные стандарты и большой банк наборов данных, поддерживаемый группой машинного обучения в Калифорнийском университете в Ирвайне, творят чудеса и толкают науку вперед. Как мы увидим, лучшие шансы создать универсальный обучающийся алгоритм – у синтеза идей из разных парадигм.

Конечно, мало уметь выявить переобучение: прежде всего надо научиться его избегать. Это означает вовремя остановить даже потенциально превосходную подгонку под данные. Один из методов – применение тестов статистической значимости для проверки того, что схемы, которые мы видим, действительно существуют. Например, и правило, включающее 300 положительных примеров против 100 отрицательных, и правило, включающее три положительных примера против одного отрицательного, на обучающих данных точны в 75 процентах, однако первое правило почти наверняка лучше, чем бросок монетки, в то время как второе – нет, поскольку четыре броска «правильной» монетки легко могут дать три орла. Если в какой-то момент при составлении правила не получается найти условия, которые значительно улучшили бы его точность, нужно просто остановиться, даже если оно все еще охватывает некоторые отрицательные примеры. Точность правила на обучающей выборке окажется меньше, но, вероятно, оно будет более точным обобщением, а именно это нас на самом деле интересует.

Но и это еще не все. Если я попробую одно правило и оно окажется в 75 процентах точным на 400 примерах, я, вероятно, ему поверю. Но если я перепробую миллион правил и лучшее будет точным в 75 процентах из 400 примеров, я, вероятно, ему не поверю, потому что это вполне могло произойти случайно. Это та же проблема, с которой вы сталкиваетесь при выборе паевого фонда. Фонд «Ясновидец» десять лет подряд был лидером рынка. Ух ты! Наверное, у них гениальный управляющий! Или нет? Если у вас есть возможность выбирать из тысячи фондов, велик шанс, что десять лет лидером будет даже такой фонд, которым тайно управляют бросающие дротики мартышки. Научная литература тоже страдает от этой проблемы. Тесты статистической значимости – золотой стандарт при допуске результатов исследований к публикации, но, если эффект ищет несколько коллективов, а находит его только один, есть вероятность, что произошла ошибка, хотя по солидной на вид статье этого никак не определить. Одним из решений была бы публикация и положительных, и отрицательных результатов, чтобы читатель знал обо всех неудачных попытках, но такой подход не прижился. В машинном обучении можно отслеживать, сколько правил было испробовано, и соответствующим образом подбирать тесты значимости, однако тогда появляется тенденция выбрасывать много хороших правил, а не только плохих. Метод немного лучше – признать, что некоторые ложные гипотезы неизбежно прокрадутся, и держать их количество под контролем, отбрасывая гипотезы с низкой значимостью и тестируя оставленные на дальнейших данных.

Еще один популярный подход – отдавать предпочтение более простым гипотезам. Алгоритм «разделяй и властвуй» косвенно предпочитает простые правила, потому что условия перестают прибавляться к правилу, как только оно охватывает только положительные примеры, и перестает добавлять правила, как только все положительные примеры охвачены. Тем не менее для борьбы с переобучением нужно более сильное предпочтение простым правилам, которое остановит добавление условий еще до того, как будут охвачены все негативные примеры. Например, можно вычитать из точности штрафные очки, пропорциональные длине правила, и использовать это как средство оценки.

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


[Закрыть], однако в контексте машинного обучения этот принцип немного обманчив. «Не множить сущее без необходимости», как часто перефразируют бритву, означает только то, что нужно выбирать самую простую теорию, которая подходит к данным. Оккам, наверное, пришел бы в недоумение от мысли, что нам надо отдавать предпочтение теории, которая не идеально подходит к доказательствам, только на том основании, что она более качественно обобщает. Простые теории предпочтительнее не потому, что они обязательно точнее, а потому, что они означают меньшую когнитивную нагрузку (для нас) и меньшие вычислительные затраты (для наших алгоритмов). Более того, даже самые замысловатые модели – обычно лишь существенное упрощение реальности. Из теоремы о бесплатных обедах мы знаем, что даже в случае теорий, идеально подходящих к данным, нет гарантии, что простейшая обобщает лучше всего, а на практике одни из лучших обучающихся алгоритмов – например, бустинг и метод опорных векторов – извлекают на первый взгляд необоснованно сложные модели. (Мы посмотрим, почему они работают, в главах 7 и 9.)

Если точность обучающегося алгоритма в тестовой выборке разочаровывает, надо диагностировать проблему: дело в слепоте или галлюцинациях? В машинном обучении для этих проблем существуют специальные термины: смещение и дисперсия. Часы, которые постоянно опаздывают на час, имеют большое смещение, но низкую дисперсию. Если часы беспорядочно идут то быстро, то медленно, но в среднем показывают правильное время, дисперсия высокая, но смещение низкое. Представьте, что вы сидите в баре с друзьями, выпиваете и играете в дартс. Вы втайне от них годами тренируетесь, добились мастерства, и все дротики попадают прямо в яблочко. У вас низкое смещение и низкая дисперсия, что показано в нижнем левом углу этой диаграммы:

Ваш друг Бен тоже очень хорош, но сегодня вечером немного перебрал. Его дротиками утыкана вся мишень, но тем не менее он громко заявляет, что в среднем попал в десятку. (Может быть, ему надо было посвятить себя статистике.) Это случай низкого смещения и высокой дисперсии, показанный в правом нижнем углу. Подруга Бена Эшли попадает стабильно, но у нее есть склонность метить слишком высоко и вправо. Дисперсия у нее низкая, а смещение высокое (левый верхний угол). Коди никогда до этого не играл в дартс. Он попадает куда угодно, только не в центр. У него и высокое смещение, и высокая дисперсия (вверху справа).

Вы можете оценить смещение и дисперсию обучающегося алгоритма, сравнив его прогнозы после обучения на случайных вариациях обучающей выборки. Если он продолжает повторять те же самые ошибки, проблема в смещении и нужно сделать его эластичнее (или просто взять другой). Если в ошибках алгоритма нет никакой схемы, проблема в дисперсии и надо либо попробовать менее гибкий, либо получить больше данных. У большинства обучающихся алгоритмов есть «ручка», с помощью которой можно отрегулировать гибкость: это, например, порог значимости и штрафы за размер модели. Подстройка – первое, что нужно попробовать.

Индукция – противоположность дедукции

Более глубокая проблема, однако, заключается в том, что большинство обучающихся алгоритмов начинают с очень скромного объема знаний, и никакая подстройка не сможет вывести их к финишной черте. Без руководства знаниями, равными по объему содержимому мозга взрослого человека, они легко сбиваются с курса. Простое допущение, что вы знаете форму правды (например, что это маленький набор правил), – совсем немного, хотя из этого исходит большинство алгоритмов. Строгий эмпирик заметил бы, что это все, что закодировано в архитектуре головного мозга новорожденного. И действительно, дети подвержены переобучению чаще, чем взрослые, однако мы хотели бы учиться быстрее, чем младенцы (даже если не считать колледж, 18 лет – это все равно долго). Верховный алгоритм должен уметь начинать с большого объема знаний, заложенных людьми или выученных в предыдущие заходы, и использовать его для извлечения из данных новых обобщений. Этот подход практикуют ученые, и это далеко не «чистая доска». Индукционный алгоритм, основанный на правиле «разделяй и властвуй», на это не способен, но это может сделать другой способ формулировки правил.

Главное – понять, что индукция – просто обратный дедукции процесс, точно так же как вычитание – это противоположность деления, а интегрирование – противоположность дифференцирования. Идея была впервые предложена Уильямом Стэнли Джевонсом[49]49
  Уильям Стэнли Джевонс (William Stanley Jevons, 1835–1882) – английский экономист, статистик и философ-логик.


[Закрыть] в конце первого десятилетия XIX века. В 1988 году англичанин Стив Магглтон и австралиец Рэй Бантайн разработали первый практический алгоритм, основанный на этом принципе. Стратегия брать хорошо известную операцию и выводить ее противоположность имеет в математике долгую историю. Применение этого принципа к сложению привело к изобретению целых чисел, потому что без отрицательных чисел сложение не всегда имеет противоположность (3–4 = –1). Аналогично применение его к умножению привело к открытию рациональных чисел, а возведение в квадрат дало комплексные числа. Давайте посмотрим, можно ли применить этот принцип к дедукции. Вот классический пример дедуктивного рассуждения:

Сократ – человек.

Все люди смертны.

Следовательно…

Первое утверждение – факт о Сократе, а второе – общее правило о людях. Что из этого следует? Конечно, что Сократ смертен, если применить это правило к Сократу. При индуктивном рассуждении мы вместо этого начинаем с исходного факта следствия и ищем правило, которое позволило бы вывести второе из первого:

Сократ – человек.

………

Следовательно, Сократ смертен.

Одним из таких правил будет: если Сократ – человек, значит, он смертен. Это правило соответствует условиям задачи, но не очень полезно, потому что не специфично для Сократа. Однако теперь мы применим принцип Ньютона и обобщим правило до всех сущностей: если сущность – человек, значит, она смертна. Или, более сжато: все люди смертны. Конечно, было бы опрометчиво выводить это правило на примере одного только Сократа, однако нам известны аналогичные факты о других людях:

Платон – человек. Платон смертен.

Аристотель – человек. Аристотель смертен.

И так далее.

Для каждой пары фактов мы формулируем правило, которое позволяет нам вывести второй факт из первого и обобщить его благодаря принципу Ньютона. Если одно и то же общее правило выводится снова и снова, можно с определенной уверенностью сказать, что оно верно.

Пока что мы еще не сделали ничего такого, чего бы не умел алгоритм «разделяй и властвуй». Однако предположим, что вместо информации, что Сократ, Платон и Аристотель – люди, мы знаем только, что они философы. Мы по-прежнему хотим сделать вывод, что они смертны, и до этого сделали вывод или нам сказали, что все люди смертны. Чего не хватает теперь? Другого правила: все философы – люди. Это тоже вполне обоснованное обобщение (как минимум пока мы не решим проблему искусственного интеллекта и роботы не начнут философствовать), и оно заполняет пробел в наших рассуждениях:

Сократ – философ.

Все философы – люди.

Все люди смертны.

Следовательно, Сократ смертен.

Кроме того, мы можем выводить правила исключительно на основе других правил. Если мы знаем, что все философы – люди и все философы смертны, то можем индуцировать, что все люди смертны. (Мы не можем, однако, сделать вывод, что все смертные – люди, потому что нам известны другие смертные существа, например кошки и собаки. С другой стороны, ученые, люди искусства и так далее – тоже люди и тоже смертны, а это укрепляет правило.) В целом чем больше правил и фактов у нас есть изначально, тем больше возможностей индуцировать новые правила путем обратной дедукции. А чем больше правил мы индуцируем, тем больше можем индуцировать. Это положительная спираль создания знаний, которая ограничена только риском переобучения и вычислительной сложностью. Но от этих проблем исходные знания тоже помогают: если вместо одной большой дыры надо заполнить много маленьких, этапы индукции будут менее рискованными и, следовательно, менее подверженными переобучению. (Например, при том же количестве примеров выведение путем индукции правила, что все философы – люди, менее рискованно, чем вывод, что все люди смертны.)

Обратить операцию часто бывает сложно, потому у нее может быть несколько противоположностей: например, у положительного числа есть два квадратных корня – положительный и отрицательный (22 = (–2)2 = 4). Самый знаменитый пример – то, что интеграл производной функции воссоздает эту функцию лишь до постоянной. Производная функции говорит нам, насколько она идет вверх и вниз в данной точке. Сложение всех этих изменений возвращает нам эту функцию, за исключением того, что мы не знаем, где она началась. Мы можем «проматывать» интеграл функции вверх или вниз без изменения производной. Чтобы упростить проблему, функцию можно «сжать», предположив, что аддитивная постоянная равна нулю. У обратной дедукции схожая проблема, и одно из ее решений – принцип Ньютона. Например, из правил «Все греческие философы – люди» и «Все греческие философы смертны» можно сделать вывод «Все люди смертны» или просто «Все греки смертны». Однако зачем довольствоваться более скромным обобщением? Вместо этого лучше предположить, что все люди смертны, пока не появится исключение. (Которое, по мнению Рэя Курцвейла, скоро появится.)

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

Как научиться лечить рак

В целом обратная дедукция – прекрасный путь к новым знаниям в биологии, а это первый шаг к лечению рака. Центральная догма гласит, что все, что происходит в живой клетке, в итоге контролируется генами посредством белков, синтез которых гены инициируют. В результате клетка похожа на крохотный компьютер, а ДНК – на действующую в нем программу: измените ДНК, и клетка кожи может стать нейроном, а мышиная клетка – превратиться в человеческую. В компьютерной программе все ошибки на совести программиста, но в клетке сбои происходят спонтанно, например под действием радиации или из-за ошибок при копировании: гены могут меняться, удваиваться и так далее. В большинстве случаев такие мутации приводят к тихой смерти клетки, но иногда она начинает расти, бесконтрольно делиться, и человек заболевает раком.

Чтобы вылечить рак, нужно остановить воспроизведение больных клеток, не повредив при этом здоровые. Для этого необходимо знать, чем они отличаются и, в частности, чем отличаются их геномы, поскольку все остальное – следствие. К счастью, секвенирование генов становится рутинной и доступной процедурой, а с его помощью можно научиться предсказывать, какие лекарства будут работать против конкретных генов рака: это совсем не похоже на традиционную химиотерапию, при которой уничтожаются все клетки без разбора. Чтобы узнать, какие лекарства сработают против определенных мутаций, требуется база данных пациентов, геномов их опухолей, проверенных лекарств и исходов. Простейшие правила кодируют прямые соответствия между генами и лекарствами. Когда секвенирование геномов опухолей и сопоставление исходов лечения станет стандартной практикой, будет открыто много подобных правил.

Однако это только начало. Большинство видов рака представляют собой комбинацию мутаций, и лекарства для их лечения пока еще не изобретены. Поэтому следующий шаг – сформулировать правила с более сложными условиями, учитывающими геном рака, геном пациента, историю болезни, известные побочные эффекты препаратов и так далее. Однако важнейшая цель – составить полную модель функционирования клетки. Это позволит нам симулировать на компьютере результаты последствия мутаций у конкретного пациента, а также действие различных комбинаций лекарств, уже существующих и потенциально возможных. Главные источники информации для построения таких моделей – это секвенсоры ДНК, микрочипы для анализа экспрессии генов и биологическая литература. Соединить эту информацию – очень подходящее задание для обратной дедукции.

Адам, робот-ученый, с которым мы уже знакомы, дает представление о том, как это может выглядеть. Его задача – разобраться, как работает дрожжевая клетка. Все начинается с базовых знаний о генетике и метаболизме дрожжей и уже собранных данных об экспрессии генов в дрожжевых клетках. Затем Адам с помощью обратной дедукции выдвигает гипотезы о том, какие гены кодируют какие белки, проектирует эксперименты с ДНК-микрочипами, чтобы проверить гипотезы, затем корректирует их и переходит к следующему циклу. Будет ли происходить экспрессия данного гена, зависит от других генов и средовых факторов, и итоговую сеть взаимодействий можно представить в виде набора правил, например:

Если температура высокая, ген A активен.

Если ген A активен, а ген B – нет, происходит экспрессия гена C.

Если ген C активен, экспрессии гена D не будет.

Если бы мы знали первое и третье правила, но не знали второго и у нас были бы данные с ДНК-микрочипа, где при высокой температуре экспрессии B и D не наблюдается, то могли бы вывести второе правило путем обратной дедукции. Когда у нас будет это правило и, возможно, мы подтвердим его путем эксперимента с микрочипом, его можно будет использовать как основу для дальнейших выводов путем индукции. Аналогичным путем можно собрать воедино цепочки химических реакций, благодаря которым белки выполняют свою функцию.

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