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

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

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

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

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

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

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

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

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

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

Или:

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

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

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

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

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

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

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

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

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

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

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