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

Теорема «Бесплатных обедов не бывает»

Через 250 лет после того, как Юм подбросил нам свою гранату, ей придал элегантную математическую форму Дэвид Уолперт, физик, ставший специалистом по машинному обучению. Его результаты, известные как уже упомянутая выше теорема «Бесплатных обедов не бывает», ставят ограничения на то, как хорош может быть обучающийся алгоритм. Ограничения довольно серьезные: никакой обучающийся алгоритм не может быть лучше случайного угадывания! Вот и приехали: Верховный алгоритм, оказывается, – это просто подбрасывание монетки. Но если серьезно, как может быть, что никакой обучающийся алгоритм не в состоянии победить угадывание с помощью орла или решки? И почему тогда мир полон очень успешных алгоритмов, от спам-фильтров до самоуправляющихся машин (они вот-вот появятся)?

Теорема «Бесплатных обедов не бывает» очень сильно напоминает причину, по которой в свое время Паскаль проиграл бы пари. В своей книге «Мысли», опубликованной в 1669 году, он заявил, что нам надо верить в христианского Бога, потому что, если он существует, это дарует нам вечную жизнь, а если нет – мы мало что теряем. Это был замечательно утонченный аргумент для того времени, но, как заметил на это Дидро, имам может привести точно такой же довод в пользу веры в Аллаха, а если выбрать неправильного бога, придется расплачиваться вечными муками в аду. В целом, учитывая огромное количество мыслимых богов, вы ничего не выиграете, выбрав в качестве объекта своей веры одного из них в пользу любого другого, потому что на любого бога, который говорит «делай то-то», найдется еще один, который потребует нечто противоположное. С тем же успехом можно просто забыть о богах и наслаждаться жизнью без религиозных предрассудков.

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

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

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

Машинное обучение с точки зрения математики относится к категории некорректно поставленных задач, так как единственного решения не существует. Вот простой пример: сумма каких двух чисел равна 1000? Если исходить из того, что числа положительные, у этой задачи 500 возможных ответов: 1 и 999, 2 и 998 и так далее. Чтобы решить некорректно поставленную задачу, придется ввести дополнительные условия. Если я скажу, что второе число в три раза больше первого, – все станет просто! Ответ – 250 и 750.

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

Аристотель говорил, что в разуме нет ничего такого, чего не было бы в органах чувств. Лейбниц добавил: «Кроме самого разума». Человеческий мозг – это не tabula rasa, потому что это совсем не доска: доска пассивна, на ней пишут, а мозг активно обрабатывает получаемую информацию. Доска, на которой он пишет, – это память, и она и впрямь сначала чиста. С другой стороны, компьютер – действительно чистая доска, до тех пор пока его не запрограммируют: активный процесс надо заложить в память, прежде чем что-нибудь произойдет. Наша цель – найти простейшую программу, какую мы только можем написать, чтобы она продолжала писать саму себя путем неограниченного чтения данных, пока не узнает все, что можно узнать.

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

Подготовка насоса знаний

В «Математических началах натуральной философии» наряду с законами движения Ньютон формулирует четыре правила индукции. Они далеко не так известны, как физические законы, но, пожалуй, не менее важны. Ключевое правило – третье, которое можно перефразировать так:

Принцип Ньютона: то, что верно для всего, что мы видели, верно для всего во Вселенной.

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

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

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

Если все сочетания двух факторов проигрышные, можно попробовать все сочетания любого числа факторов. Специалисты по машинному обучению и психологи называют это «конъюнктивными понятиями». К таким понятиям относятся словарные определения: «У стула есть сиденье, и спинка, и некоторое число ножек». Уберите любое из этих условий, и это уже будет не стул. Конъюнктивное понятие можно найти у Толстого в первой строке «Анны Карениной»: «Все счастливые семьи похожи друг на друга, каждая несчастливая семья несчастлива по-своему». То же верно и для отдельных людей. Чтобы быть счастливым, нужны здоровье, любовь, друзья, деньги, любимая работа и так далее. Уберите что-то из этого списка, и человек будет несчастлив.

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

Для машинного обучения типично начинать с ограничивающих условий и постепенно ослаблять их, если они не объясняют данных. Этот процесс обычно выполняется обучающимся алгоритмом автоматически, без какой-либо помощи со стороны человека. Сначала алгоритм тестирует все отдельные факторы, затем все сочетания двух факторов, потом все сочетания трех и так далее. Однако здесь мы опять сталкиваемся с проблемой: конъюнктивных понятий очень много, а времени, чтобы все перепробовать, недостаточно.

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

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

Как править миром

Тем не менее на конъюнктивных понятиях далеко не уедешь. Проблема, как выразился Редьярд Киплинг, в том, что «путей в искусстве есть семь и десять раз по шесть, и любой из них для песни – лучше всех». В реальной жизни понятия дизъюнктивны. У стульев может быть и четыре ножки, и одна, а иногда они вообще без ножек. В шахматы можно выиграть бесчисленным количеством способов. Электронные письма со словом «виагра», скорее всего, спам, но то же самое можно сказать о письмах со словом «БЕСПЛАТНО!!!». Кроме того, у всех правил бывают исключения. Некоторые неблагополучные семьи умудряются быть счастливыми. Все птицы летают, только если это не пингвины, страусы, казуары и киви (а также если у них не сломано крыло, они не сидят в клетке и так далее).

Так что нам нужно находить концепции, которые заданы целым набором правил, а не одним, например:

Если вам нравятся IV–VI эпизоды «Звездных войн», значит, вам понравится «Аватар».

Если вам нравятся «Звездный путь: Следующее поколение» и «Титаник», вам понравится «Аватар».

Если вы член экологической организации Sierra Club и любите научную фантастику, вам понравится «Аватар».

Или:

Если вашей кредитной карточкой вчера пользовались в Китае, Канаде и Нигерии, значит, ее украли.

Если вашей кредитной карточкой пользовались два раза после 11 вечера в будний день, значит, ее украли.

Если с вашей кредитной карточки купили бензин на один доллар, значит, ее украли.

(Если вы не поняли последнее правило, небольшое пояснение: раньше воры обычно покупали бензин на доллар, чтобы убедиться, что украденная карточка работает. Потом специалисты по добыче данных раскусили этот прием.)

С помощью алгоритма для нахождения конъюнктивных понятий, с которым мы познакомились выше, можно составлять подобные наборы по одному правило за правилом. Когда мы нашли правило, можно отбросить положительные примеры, которые оно включает, поэтому следующее правило будет пытаться охватить как можно больше оставшихся положительных примеров и так далее, пока все не будет включено. Это применение принципа «разделяй и властвуй», древнейшей стратегии в научном арсенале. Кроме того, мы можем улучшить алгоритм поиска отдельных правил, если будем иметь в запасе не одну, а n гипотез и на каждом этапе расширять их всеми возможными способами, сохраняя n лучших результатов.

Открытием такого способа поиска правил мы обязаны польскому информатику Рышарду Михальскому. Его родной город Калуш в разное время входил в состав Польши, СССР, Германии и Украины, и, возможно, именно это повлияло на его склонность к дизъюнктивным понятиям. Эмигрировав в 1970 году в США, он вместе с Томом Митчеллом и Джейми Карбонеллом основал символистскую школу машинного обучения. У Михальского был весьма деспотичный характер. Выступавшие на конференциях по машинному обучению не были застрахованы от того, что в конце он не поднимет руку и не заявит, что только что услышал повторение одной из своих старых идей.

Наборы правил популярны в торговых сетях: с их помощью определяют, какие товары надо закупать. Как правило, ретейлеры используют более всесторонний подход, чем «разделяй и властвуй», и ищут все правила, которые с большой вероятностью прогнозируют спрос. Пионер в этой области – Walmart. Еще на заре применения этого метода они открыли, что с подгузниками часто покупают пиво. Звучит странно? Одна из интерпретаций такая: молодые матери посылают мужей в супермаркет за подгузниками, а те в качестве компенсации за моральный ущерб покупают себе ящик пива. Зная это, супермаркеты теперь могут продавать больше пенного напитка, выставляя его на полках по соседству с подгузниками. К такому выводу никогда не придешь без поиска правил: «закон пива и подгузников» стал легендой среди специалистов по добыче данных (некоторые, правда, утверждают, что это скорее городская легенда). Как бы то ни было, все это довольно далеко от проблем разработки цифровых схем, которые были на уме у Михальского, когда он в 1960‑х впервые начал задумываться о логическом поиске правил. Изобретая новый алгоритм машинного обучения, нельзя даже представить себе все области, в которых он может найти применение.

Первый практический урок в области обучения правилам я получил, когда только переехал в США, чтобы поступить в аспирантуру, и подал заявку на получение кредитной карточки. Банк прислал мне письмо, в котором говорилось: «К сожалению, ваше заявление отклонено по следующим причинам: НЕДОСТАТОЧНО ДОЛГОЕ ПРОЖИВАНИЕ ПО ТЕКУЩЕМУ АДРЕСУ И ОТСУТСТВИЕ КРЕДИТНОЙ ИСТОРИИ» (или еще что-то в том же духе заглавными буквами). Тогда я понял, что в области машинного обучения предстоит еще немало работы.

Между слепотой и галлюцинациями

Наборы правил намного мощнее, чем конъюнктивные понятия. Вообще говоря, они настолько сильны, что с их помощью можно выразить любое понятие. Почему – понять несложно: если вы дадите мне полный список всех примеров какого-то понятия, я могу просто превратить каждый из них в правило, которое описывает все его атрибуты, и набор таких правил станет определением понятия. Если вернуться к нашей проблеме свидания, одним из правил будет такое: Если сегодня выходной, на улице тепло, по телевизору не показывают ничего хорошего и я предложу сходить в клуб, она скажет «да». В таблице содержится лишь несколько примеров, но, если в нее внести все 2 × 2 × 2 × 2 = 16 возможных и каждому присвоить ярлык «Есть свидание» или «Нет свидания», превращение каждого положительного примера в правило решит проблему.

Наборы правил – мощный, но обоюдоострый меч. Их достоинство в том, что всегда можно найти набор правил, который идеально подойдет к имеющимся данным. Однако не спешите радоваться, что поймали удачу за хвост. Не забывайте: есть серьезнейший риск столкнуться с совершенно бессмысленным правилом. Помните теорему о бесплатных обедах? Учиться без знаний нельзя. Предположение, что понятие можно определить набором правил, – пустое предположение.

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

В рассказе «Фунес памятливый» Хорхе Луис Борхес повествует о встрече с молодым человеком с идеальной памятью. Сначала такой дар может показаться редким везением, но на самом деле это ужасное проклятье. Фунес может вспомнить точную форму туч в небе в произвольный момент времени в прошлом, но ему сложно понять, что собака, которую он видел сбоку в 15:14, – та же самая собака, которую он видел спереди в 15:15, и он каждый раз удивляется собственному отражению в зеркале. Фунес неспособен обобщать, поэтому для него две вещи одинаковы, только если они выглядят идентично, вплоть до мелочей. Неограниченное обучение правилам похоже на Фунеса и совершенно неработоспособно. Учиться – значит забывать о подробностях в той же степени, как помнить о важных элементах. Компьютеры – высшее проявление синдрома саванта[45]45
  Синдром саванта, иногда сокращенно называемый савантизм (от фр. savant – «ученый»), – редкое состояние, при котором лица с отклонением в развитии (в том числе аутистического спектра) имеют «остров гениальности» – выдающиеся способности в одной или нескольких областях знаний, контрастирующие с общей ограниченностью личности.


[Закрыть]: они без малейших проблем запоминают все, но хотим мы от них не этого.

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

Люди тоже не застрахованы от переобучения. Можно даже сказать, что это корень многих наших бед. Представьте себе ситуацию: маленькая белая девочка видит в торговом центре девочку-мексиканку и кричит: «Мама, смотри, ребенок-служанка!» (это реальный случай). Дело не в прирожденном расизме. Скорее, она слишком обобщила представление о тех немногих латиноамериканках, которых успела увидеть за свою короткую пока жизнь, – в мире полно представительниц этой этнической группы, не работающих прислугой, но девочка их пока не встретила. Наши убеждения основаны на опыте, а опыт дает очень неполную картину мира, поэтому перепрыгнуть к ложным выводам несложно. Ум и эрудиция тоже не панацея. Именно переобучением было утверждение Аристотеля, что для того, чтобы объект продолжал двигаться, к нему должна быть приложена сила. Лишь гениальный Галилей интуитивно почувствовал, что невозмущенные тела тоже продолжают двигаться, хотя не был в открытом космосе и собственными глазами этого не видел.

Однако обучающиеся алгоритмы, с их почти неограниченной способностью находить закономерности в данных, особенно уязвимы для переобучения. За время, пока человек будет искать одну закономерность, компьютер найдет миллионы. В машинном обучении величайшая сила компьютера – способность обрабатывать огромное количество данных и бесконечно, без устали повторять одно и то же – одновременно становится его ахиллесовой пятой. Просто удивительно, сколько всего можно найти, если хорошенько поискать. В бестселлере 1998 года The Bible Code[46]46
  Речь идет о книге Майкла Дроснина: Дроснин М. Библейский код. М.: Вагриус, 2000.


[Закрыть] утверждается, что Библия содержит предсказания будущих событий, которые можно прочитать, если брать буквы через определенные интервалы и составлять из них слова. К сожалению, есть столько способов это сделать, что «предсказания» обязательно найдутся в любом достаточно длинном тексте. Скептики ответили автору пророчествами из «Моби Дика» и постановлений Верховного суда, а также нашли в Книге Бытия упоминания о Розуэлле и летающих тарелках[47]47
  Имеется в виду так называемый Розуэлльский инцидент – предполагаемое крушение неопознанного летающего объекта около города Розуэлл в штате Нью-Мексико в июле 1947 года.


[Закрыть]. Джон фон Нейман, один из основоположников информатики, как-то точно заметил: «С четырьмя параметрами я могу подогнать слона, а с пятью заставлю его махать хоботом». Сегодня мы каждый день учим модели с миллионами параметров. Этого достаточно, чтобы каждый слон в мире махал хоботом по-своему. Кто-то даже сказал, что «добывать данные – значит пытать их до тех пор, пока они не признаются».

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

Переобучение возникает, когда у вас слишком много гипотез и недостаточно данных, чтобы их различить. Проблема в том, что даже в простых конъюнктивных обучающихся алгоритмах число гипотез растет экспоненциально с числом атрибутов. Экспоненциальный рост – страшная сила. Бактерия E. coli может делиться надвое примерно каждые 15 минут. Если бы у нее было достаточно питательных веществ, она бы за день разрослась в бактериальную массу размером с нашу планету. Когда количество элементов, необходимых алгоритму для работы, растет в геометрической прогрессии с увеличением размера вводных данных, информатики называют это комбинаторным взрывом и бегут в укрытие. В машинном обучении количество возможных частных случаев какого-либо понятия – экспоненциальная функция числа атрибутов: если атрибуты булевы, с каждым новым атрибутом число возможных частных случаев удваивается, каждый случай расширяется для «да» или «нет» этого атрибута. В свою очередь, число возможных понятий – это экспоненциальная функция числа возможных частных случаев: поскольку понятие отмечает каждый случай как положительный или отрицательный, добавление частного случая удваивает число возможных понятий. В результате число понятий – это экспоненциальная функция экспоненциальной функции числа атрибутов! Другими словами, машинное обучение – комбинаторный взрыв комбинаторных взрывов. Может, лучше просто сдаться и не тратить времени на такую безнадежную проблему?

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

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

Итого: обучение – гонка между количеством данных, имеющихся в вашем распоряжении, и количеством рассматриваемых вами гипотез. Увеличение объема данных экспоненциально уменьшает количество прошедших проверку гипотез, но, если гипотез изначально много, в конце все равно может остаться некоторое количество плохих. Есть золотое правило: если обучающийся алгоритм учитывает только экспоненциальное число гипотез (например, все возможные конъюнктивные понятия), то экспоненциальный выигрыш от данных решает проблему, и все в порядке, при условии, что у вас множество примеров и не очень много атрибутов. С другой стороны, если алгоритм рассматривает дважды экспоненциальное число (например, все возможные наборы правил), тогда данные отменяют только одну из экспонент, и трудности остаются. Можно даже заранее решить, сколько примеров понадобится, чтобы быть достаточно уверенным, что выбранная обучающимся алгоритмом гипотеза очень близка к истинной, при условии, что к ней подходят все данные. Другими словами, чтобы гипотеза была, вероятно, приблизительно правильной. За изобретение этого типа анализа гарвардский ученый Лесли Вэлиант получил премию Тьюринга – Нобелевскую премию по информатике. Его книга на эту тему называется Probably Approximately Correct («Возможно, приблизительно верно»).