Верховный алгоритм - Педро Домингос

Для аналогистов ключ к обучению — находить сходства между разными ситуациями и тем самым логически выводить другие сходства. Если у двух пациентов схожие симптомы, вероятно, у них одинаковое заболевание. Ключевая проблема — оценить, насколько похожи два случая. Верховный алгоритм аналогистов — это метод опорных векторов, который определяет, какой опыт надо запомнить и как соединить опыт, чтобы делать новые прогнозы.

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

В этой книге мы создадим единый алгоритм со всеми этими воз­можностями.

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

Алгоритм, к которому мы придем, пока не будет Верховным (мы увидим почему), но так далеко еще никто не заходил. А в пути нас ждет столько сокровищ, что позавидовал бы сам Крез41. Тем не менее эта книга — лишь первая часть саги о Верховном алгоритме. Героем второй части станете вы, дорогой читатель. Ваша миссия, если вы решитесь взять ее на себя, — пройти остаток пути и вернуться с наградой. Я буду вашим скромным проводником по первой части, отсюда и до границы известного мира. Что? Вы говорите, что знаете слишком мало и не сильны в алгоритмах? Не пугайтесь. Информатика еще молода, и здесь, в отличие от физики или биологии, вам не надо быть доктором наук, чтобы совершить в ней революцию. (Не верите — спросите Билла Гейтса, а еще Сергея Брина, Ларри Пейджа и Марка Цукерберга42.) Важны идеи и упорство.

Итак, вы готовы? Наш путь начнется с визита к символистам, «племени» с самой солидной родословной.

ГЛАВА 3

ПРОБЛЕМА ИНДУКЦИИ ЮМА

Вы рационалист или эмпирик?

Рационалисты считают, что чувства обманчивы и единственный верный путь к знанию — логическое рассуждение. Эмпирики уверены, что рассуждения подвержены ошибкам и знание должно быть получено из наблюдений и экспериментов. Французы — рационалисты. Англосаксы (как их называют французы) — эмпирики. Мыслители, юристы и математики — рационалисты. Журналисты, врачи и ученые — эмпирики. «Она написала убийство» — рационалистический криминальный телесериал. «C.S.I.: Место преступления» — эмпирический. В мире информатики теоретики и инже­неры знаний — рационалисты. Хакеры и специалисты по машинному обучению — эмпирики.

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

Рационалисты и эмпирики, наверное, существовали с самого зарождения Homo sapiens. Перед тем как выйти на охоту, Пещерный Бобби долго сидел у костра и размышлял, где его поджидает добыча. Тем временем Пещерная Алиса систематически прочесывала территорию. Поскольку оба вида дошли до наших дней, наверное, будет правильно сказать, что ни один подход не лучше другого. Вы можете подумать, что машинное обучение — это окончательный триумф эмпириков, но скоро мы увидим, что все не так однозначно.

«Рационализм или эмпиризм?» — любимый вопрос философов. Платон был ранним рационалистом, а Аристотель — ранним эмпириком. Но по-настоящему дебаты разгорелись в эпоху Просвещения, когда по каждую сторону встали по три великих мыслителя: Декарт, Спиноза и Лейбниц были ведущими рационалистами; Локк, Беркли и Юм — их соперниками-эмпириками. Доверяя своей силе рассуждения, рационалисты сочиняли теории Вселенной, которые, мягко говоря, не прошли проверку временем, но помимо этого они изобрели фундаментальные математические методики, например математический анализ и аналитическую геометрию. Эмпирики были гораздо практичнее, и их влияние прослеживается везде, начиная с научного метода и заканчивая Конституцией США.

Выдающимся эмпириком и величайшим англоязычным философом всех времен был Дэвид Юм. О его серьезнейшем влиянии говорили такие ученые, как Адам Смит и Чарльз Дарвин, а еще его можно назвать святым покровителем символистов. Юм родился в Шотландии в 1711 году и большую часть своей жизни провел в Эдинбурге, который в XVIII веке процветал и бурлил интеллектуальной жизнью. Юм был человеком добродушным, но при этом строгим скептиком и много времени посвящал разрушению мифов своего времени. Он довел начатые Локком рассуждения об эмпирике до логического завершения и задал вопрос, который с тех пор, как дамоклов меч, висит над любым знанием, от самого банального до самого сложного: как в принципе можно оправдать экстраполяцию того, что мы видели, на то, чего мы не видели? Каждый обучающийся алгоритм в каком-то смысле — попытка ответить на этот вопрос.

Вопрос Юма — отправная точка нашего путешествия. Начнем с того, что проиллюстрируем его примером из повседневной жизни и встретим ее современное воплощение в знаменитой теореме No free lunch — «Бесплатных обедов не бывает»43. Затем мы посмотрим, что отвечают Юму символисты. Это подведет нас к самой важной проблеме машинного обучения: проблеме переобучения, то есть выделения фантомных закономерностей, которых на самом деле нет. Мы посмотрим, как ее решают символисты и почему машинное обучение — сердце своего рода алхимии, философский камень превращения данных в знания. Для символистов этот камень — само знание. В следующих четырех главах мы увидим решения алхимиков из других «племен».

Быть или не быть свиданию?

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