Что может угадать, кто? Научите нас машинному обучению?
«Ваш человек носит шляпу?»
Угадай, кто? — классическая настольная игра, впервые представленная Милтоном Брэдли в 1979 году. Эта вневременная игра до сих пор встречается в детских шкафах с настольными играми... и не зря!
Хотя мы, возможно, не знали этого в то время, выигрышная стратегия игры имеет ту же интуицию, что и наши любимые алгоритмы машинного обучения, включая случайный лес и XGBoost.
Итак, в следующий раз, когда вы окажетесь (крайне) отчаянным на собеседовании, подумайте о том, чтобы отказаться от того, что к 10 годам вы «использовали алгоритм бинарного поиска для построения прогностической модели на основе дерева решений».
Давайте посмотрим, почему это правда!
Правила прежде всего
Игра для двух игроков проводится на красных и синих лотках, на каждом из которых находится 24 разных карты персонажей.
В начале игры игроки случайным образом тянут карту загадочного персонажа, которую их противник пытается угадать, задавая вопросы «да» или «нет» о внешности персонажа.
Каждый игрок по очереди задает вопрос (например, «Ваш человек лысый?»), на который его оппонент отвечает либо «да», либо «нет».
Информация, полученная в результате ответа каждого оппонента, позволяет игрокам исключать карты персонажей, которые не соответствуют ответу оппонента, переворачивая их вниз.
Игроки ходят по очереди до тех пор, пока они правильно не угадают характер своего противника или их противник неправильно не угадает их загадочную карту.
Само собой разумеется, что ложь против правил (если только вы не моя старшая сестра).
Выигрышная стратегия
Если вы играете в игру более нескольких раз, появляется выигрышная стратегия: Каждый ход вы хотите задавать своему противнику вопросы, которые разделят персонажей примерно пополам.
Эта тактика максимизирует количество персонажей, которых можно уничтожить за каждый ход.
Прежде чем вводить технические термины, давайте рассмотрим интуицию, стоящую за этой стратегией, на примере игры Угадай, кто? с 8 смайликами на рис. 1.
Наша цель — определить таинственный смайлик нашего оппонента (ученый в белом лабораторном халате с красной пробиркой), задав наименьшее количество вопросов «да» или «нет».
Первый вопрос, который мы задаем, — «Есть ли у вашего персонажа очки?», потому что мы знаем, что сможем исключить 4 персонажей на основе ответа нашего противника, независимо от того, носят они очки или нет.
Наш оппонент отвечает, что его загадочный персонаж носит очки, поэтому мы исключаем из рассмотрения четыре смайлика без очков.
Мы повторяем процесс еще два раза, пока не придем к персонажу, который соответствует всей предоставленной информации, и мы уверены, что это загадочный игрок нашего оппонента. (Высокое доверие к Угадай, кто? важно, потому что неправильное предположение автоматически проигрывает игру.)
Терминология дерева решений
Вы можете быть удивлены, узнав, что одна и та же стратегия лежит в основе целой группы моделей регрессии и классификации, называемых деревьями решений.
Модели дерева решений используют аналогичные вопросы, чтобы минимизировать энтропию и/или максимизировать прирост информации в наборе данных.
Давайте воспользуемся примером Угадай, кто?, чтобы познакомить вас с не такой уж пугающей терминологией.
В начале игры наш игровой лоток содержит 24 символа или образца, которые считаются корневым узлом нашего дерева решений Угадай, кто?.
Каждый вопрос, который мы задаем оппоненту, считается узлом принятия решения, который разбивает наши данные на две ветви на основе бинарного файла. > (да/нет) ответ.
Мы используем функции, содержащиеся в изображении персонажа, для построения узлов принятия решений. Обычно «хорошая» функция для узла принятия решения может задавать вопрос о наличии или отсутствии у персонажа растительности на лице, очков или шляпы.
«Лучшая» функция для формирования узла решения (вопроса) в любой момент — это та, которая разделит оставшиеся символы пополам, чтобы безопасно исключить большинство символов.
Наконец, мы удаляем ненужные символы с помощью техники сокращения. Мы делаем это, игнорируя все остальные ответвления (отбрасывая нерелевантные символы вниз) и сосредотачиваясь только на ответвлении, которое позволяет нам предсказать загадочного персонажа противника и выиграть игру!
Во время собеседования вы хотели звучать как можно сложнее, поэтому сказали: «использовали алгоритм рекурсивного бинарного поиска для построения прогностической модели на основе дерева решений». Распаковываем, что это значит:
Рекурсивный(прилагательное) — относящийся к правилу или процедуре, которые могут применяться повторно или использующие их.
Двоичный(прилагательное) — состоит из, указывает или включает два
Разделение(существительное) – разделение, разделение или разделение каким-либо образом.
Алгоритм(существительное) — процесс или набор правил, которым необходимо следовать при вычислениях или других операциях по решению проблем.
Из Угадай Кто? например, мы можем видеть, что рекурсивная стратегия бинарного разделения на самом деле просто причудливый способ сказать повторяющееся разделение на две группы!
Еще несколько мыслей об обучающихся на основе деревьев!
Деревья решений являются основополагающей концепцией машинного обучения и составляют основу некоторых из наших любимых алгоритмов, включая случайный лес и XGBoost.
На практике одиночное дерево решений почти никогда не используется для классификации или прогнозирования.
Отдельные деревья страдают как высоким смещением (неточностью), так и дисперсией (несогласованностью). (Дерево не знает!)
К счастью для нас, наш компьютер более чем способен строить тысячи деревьев решений и собирать или комбинировать их вместе для создания модели с высокой точностью. В результате получается высокоэффективный «лес», который усиливает мудрость толпы для прогнозирования или классификации («Деревья сильны вместе!»).
Способ объединения деревьев решений может повысить производительность. В этих методах используются сотни или тысячи деревьев и умные методы их объединения, такие как бэгинг и бустинг.
«Случайный» в случайном лесу просто означает удержание определенных прогностических функций вне случайного выбора — «Угадай, кто?» эквивалент правила, указывающего, что «в этом ходу никто не может использовать цвет в своем вопросе!»
Эта небольшая доля случайности заставляет модель не слишком сильно зависеть от какой-либо одной функции для своих прогнозов.
Как только вы освоитесь с концепцией случайного леса, волшебство XGBoost будет в нескольких шагах от вас, включая несколько дополнительных наворотов, которые позволят ему учиться на своих предыдущих ошибках.
Я надеюсь, что эта статья поможет демистифицировать некоторые концепции и терминологию машинного обучения в вашем стремлении к знаниям!
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
* Игра «Угадай, кто» была сильно решена Михаем Никой в 2016 году, который доказал, что оптимальная игра и первый ход увеличивают шансы на победу при идеальной игре обеих сторон. Эта работа показала, что строгий бинарный поиск (50/50) не всегда был оптимальной стратегией. На самом деле отстающему игроку выгодно задавать «смелые» (70/30) вопросы, чтобы наверстать упущенное!
Если вам понравилась эта статья, ознакомьтесь также с темой Чему линкор может научить нас в машинном обучении?
