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

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

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

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

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

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

Или:

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

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

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

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

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

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

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

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