Читать книгу - "Рациональность: от ИИ до зомби - Элиезер Шломо Юдковски"

«Концепт» в машинном обучении — это правило, которое включает или исключает примеры. Если вы видите набор данных {2:+, 3:-, 14:+, 23:-, 8:+, 9:-}, то можете предположить, что этот концепт — «четные числа». На тему того, как выводить концепты из данных, написана огромная литература (как и следовало ожидать): как делать это при наличии случайных примеров, при наличии специально подобранных примеров... при возможных ошибках классификации... и, что самое важное, при различных пространствах возможных правил.

Предположим, к примеру, что мы хотим определить концепт «дни, подходящие для игры в теннис». Возможные признаки Дня:

Sky: {Sunny, Cloudy, Rainy}

AirTemp: {Warm, Cold}

Humidity: {Normal, High}

Wind: {Strong, Weak}.

Затем нам предоставляют следующие данные, где плюс (+) означает положительный пример концепта, а минус (-) — отрицательный:

+ Sky: Sunny; AirTemp: Warm; Humidity: High; Wind: Strong.

- Sky: Rainy; AirTemp: Cold; Humidity: High; Wind: Strong.

+ Sky: Sunny; AirTemp: Warm; Humidity: High; Wind: Weak.

Какой вывод должен сделать из этого алгоритм?

Алгоритм машинного обучения может представить один из концептов, соответствующих этим данным, следующим образом:

{Sky: ?; AirTemp: Warm; Humidity: High; Wind: ?}.

В таком формате, чтобы определить, подходит ли пример под концепт или нет, мы сравниваем параметры поэлементно: знак «?» допускает любое значение, тогда как конкретное значение допускает только это конкретное значение.

Таким образом, приведенный выше концепт примет только те Дни, где AirTemp = Warm и Humidity = High, тогда как Sky и Wind могут принимать любые значения. Это соответствует и отрицательным, и положительным примерам в имеющихся на данный момент данных — хотя это и не единственный подходящий концепт.

Мы также можем упростить приведенное выше представление концепта до

{?, Warm, High, ?}.

Не вдаваясь в подробности, классический алгоритм работает так:

Мы поддерживаем множество наиболее общих гипотез, соответствующих данным — тех, которые классифицируют максимально возможное число примеров как положительные, но при этом не противоречат фактам.

Мы также поддерживаем множество наиболее специфичных гипотез, соответствующих данным — тех, которые классифицируют максимально возможное число примеров как отрицательные, но при этом всё ещё не противоречат фактам.

Каждый раз, когда мы видим новый отрицательный пример, мы сужаем все наиболее общие гипотезы в минимально возможной степени, чтобы новое множество оставалось настолько общим, насколько это возможно без противоречия фактам.

Каждый раз, когда мы видим новый положительный пример, мы расширяем все наиболее специфичные гипотезы в минимально возможной степени, чтобы новое множество оставалось настолько специфичным, насколько это возможно без противоречия фактам.

Мы продолжаем этот процесс, пока у нас не останется ровно одна гипотеза. Она и будет ответом — если целевой концепт вообще присутствовал в нашем пространстве гипотез.

В описанном выше случае множество наиболее общих гипотез будет состоять из:

{{?, Warm, ?, ?},{Sunny, ?, ?, ?}},

в то время как множество наиболее специфичных гипотез содержит единственный элемент {Sunny, Warm, High, ?}.

Любой другой соответствующий данным концепт, который вы сможете найти, будет строго более специфичным, чем одна из наиболее общих гипотез, и строго более общим, чем самая специфичная гипотеза.

(Подробнее об этом можно почитать в книге Тома Митчелла «Машинное обучение», откуда и был адаптирован этот пример.1)

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

Очевидно, что наша модель машинного обучения весьма ограничена. Почему бы не позволить ей выражать абсолютно любые концепты, чтобы она могла обучаться с максимальной гибкостью?

Дни описываются четырьмя переменными: одна принимает три значения, а три другие — по два значения. Таким образом, всего мы можем столкнуться с 3 × 2 × 2 × 2 = 24 вариантами Дней.

Принятый формат представления концептов позволяет нам либо требовать конкретное значение для переменной, либо оставлять её открытой. Значит, в такой системе координат возможны 4 × 3 × 3 × 3 = 108 концептов. Чтобы работал алгоритм поиска наиболее общих и наиболее специфичных гипотез, нам нужно начать с максимально специфичной гипотезы: «ни один пример никогда не классифицируется как положительный». Если добавить её, получится в общей сложности 109 концептов.

Подозрительно ли то, что возможных концептов больше, чем самих Дней? Разумеется, нет: в конце концов, концепт можно рассматривать как совокупность Дней. Любой концепт — это просто множество дней, которые классифицируются им как положительные (или, что изоморфно, множество дней, классифицируемых как отрицательные).

Следовательно, пространство абсолютно всех возможных концептов, классифицирующих Дни, представляет собой множество всех возможных множеств Дней, размер которого равен 224 = 16 777 216.

Это полное пространство включает в себя все концепты, которые мы обсуждали ранее. Но в него также входят и такие правила, как «Считать положительными только примеры {Sunny, Warm, High, Strong} и {Sunny, Warm, High, Weak}, а всё остальное отвергать» или «Считать отрицательным только пример {Rainy, Cold, High, Strong}, а всё остальное принимать». Сюда входят концепты, не имеющие компактного описания — просто сплошной список того, что разрешено, а что запрещено.

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

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

Допустим, мы добавим к Дням признак Вода: {Теплая, Холодная}, что даст 48 возможных Дней и 325 возможных концептов. Допустим, каждый наблюдаемый День обычно классифицируется как положительный примерно половиной текущих правдоподобных концептов, а другой половиной — как отрицательный. Тогда, когда мы узнаем фактическую классификацию примера, это сократит пространство совместимых концептов наполовину. Таким образом, может потребоваться всего 9 примеров (29 = 512), чтобы сузить 325 возможных концептов до одного.

Даже если бы у Дней было сорок бинарных признаков, всё равно потребовался бы вполне обозримый объем данных, чтобы сузить число возможных концептов до одного. Шестьдесят четыре примера, если каждый пример классифицируется как положительный половиной оставшихся концептов. При условии, конечно, что реальное правило мы вообще в состоянии выразить!

Если вы хотите перебрать в уме все возможности