Суперэкспоненциальное пространство концептов и простые слова

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

В действительности, поскольку я «определил» пространство вещей так, что в нём есть размерности для всех возможных свойств — включая связанные друг с другом свойства, например, плотность, объём и массу — для пространства вещей крайне сложно определить что-то, что можно назвать «размером». Однако, важно уметь представлять пространство вещей хоть как-нибудь. Уверен, совершенно никто не в состоянии понять стаю воробьёв, если он видит лишь облако машущих крыльями чирикающих существ вместо кластера точек в пространстве вещей.

Но пространство вещей всё равно не сравнится с пространством концептов.

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

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

Облачность: {Ясно, Пасмурно, Дождевые облака}
Температура воздуха: {Тепло, Холодно}
Влажность: {Нормальная, Высокая}
Ветер: {Сильный, Слабый}


Теперь предположим, что у нас есть следующие данные, где «+» означает, что набор удовлетворяет правилу, а «-» — что не удовлетворяет.

+ Облачность: Ясно; Температура воздуха: Тепло; Влажность: Высокая; Ветер: Сильный.
- Облачность: Дождевые облака; Температура воздуха: Холодно; Влажность: Высокая; Ветер: Сильный.
+ Облачность: Ясно; Температура воздуха: Тепло; Влажность: Высокая; Ветер: Слабый.


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

Обучающаяся машина может сформировать свой соответствующий данным концепт следующим образом:

{Облачность: ?; Температура воздуха: Тепло; Влажность: Высокая; Ветер: ?}.


Чтобы определить подходит ли какой-то пример данных или нет, мы сравниваем последовательно все элементы. ? означает, что подходит любое значение, но если какое-то конкретное значение задано, то подходит только оно.

То есть концепт выше примет только тот День, в котором Температура воздуха = Тепло и Влажность = Высокая. Переменные Облачность и Ветер могут принимать любые значения. Пока это согласуется со всеми данными, которые у нас есть. Хотя это далеко не единственный концепт, который подошёл бы нам .

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

{?, Тепло, Высокая, ?}


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

• Поддерживать набор наиболее общих гипотез, соответствующих данным. Эти гипотезы должны положительно классифицировать как можно больше исходов, при этом не противореча фактам.
• Поддерживать другой набор как можно более конкретных гипотез, соответствующих данным. Гипотезы в этом наборе должны отрицательно классифицировать как можно больше исходов, при этом не противореча фактам.
• Каждый раз, когда мы наблюдаем отрицательный исход, мы усиливаем наиболее общие гипотезы как можно меньше, чтобы новый набор оставался как можно более общим и при этом не противоречил фактам.
• Каждый раз, когда мы наблюдаем положительный исход, мы ослабляем наиболее конкретные гипотезы как можно меньше, чтобы новый набор оставался как можно более конкретным и при этом не противоречил фактам.
• Продолжаем до тех пор, пока не останется одна гипотеза. Это и будет правильным решением — при условии, что правильное решение вообще попало в наше пространство гипотез.

В нашем примере набор наиболее общих гипотез выглядит так:

{{?, Тепло, ?, ?}, {Ясно, ?, ?, ?}},


при этом множество наиболее конкретных гипотез содержит единственный вариант {Ясно, Тепло, Высокая, ?}.

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

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

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

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

Каждый день описывается четырьмя переменными. У одной из них три возможных значения, у трёх — два возможных значения. Итого у нас 3 × 2 × 2 × 2 = 24 возможных варианта дня.

Формат для представления концептов выше требует, чтобы мы указывали одно из значений переменной или оставляли его неизвестным. Таким образом мы можем описать 4 × 3 × 3 × 3 = 108 концептов. Чтобы работал алгоритм «наиболее-общий/наиболее-конкретный», необходимо начать с максимально конкретной гипотезы «ни один исход никогда не окажется положительным». Итого мы получаем 109 концептов.

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

Таким образом, пространство всех возможных концептов классификации дней содержит в себе множество всех возможных множеств дней и его размер $2^{24} = 16 777 216$.

Указанное пространство включает в себя все концепты, которые мы обсуждали до сих пор. Однако оно содержит и такие концепты как «положительно классифицировать только случаи {Ясно, Тепло, Высокая, Сильный} {Ясно, Тепло, Высокая, Слабый} и отвергать все остальные» или «отрицательно классифицировать только случаи {Дождевые облака, Холодно, Высокая, Сильный} и принимать все остальные». Также в это пространство входят концепты без компактного описания, то есть списки допустимых и недопустимых случаев.

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

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

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

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

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

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

И это, напоминаю, сорок двоичных свойств. Сорок бит или пять байт с вариантами «Да» или «Нет». Сорок бит это $2^{40}$ возможных случаев и $2^{2^{40}}$ возможных концептов, согласно которым можно классифицировать каждый случай как положительный или отрицательный.

В повседневной жизни, чтобы описать объект, зачастую требуется больше 5 байт. Кроме того, у нас нет триллиона примеров для обучения, а в данных присутствует шум. О довольно привычных понятиях в таких условиях сложно даже подумать. Человеческий разум — и даже вся наблюдаемая Вселенная — недостаточно велики, чтобы рассмотреть все гипотезы.

С этих позиций, обучение не просто опирается на индуктивные эвристики отбора2, оно по сути целиком и полностью из них состоит. Сравните количество концептов, отброшенных априори и количество концептов, отброшенных на основании наличия свидетельств.

«Но какое это имеет отношение к использованию слов?», — спросите вы.

Смысл в том, что у слов есть как интенсионалы, так и экстенсионалы.

В прошлом эссе я подвел следующий итог:

Разрезать реальность по месту естественного соединения частей — проводить границы вокруг необычно плотно сконцентрированных вероятностей.

В это (немного отредактированное) утверждение я специально не вставил важное уточнение, потому что до настоящего момента я не мог его объяснить. Правильнее было бы сформулировать так:

Разрезать реальность по месту естественного соединения частей — проводить простые границы вокруг необычайно плотно сконцентрированных вероятностей в пространстве вещей.

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

В реальном мире ничего выше уровня молекул не повторяется в точности. Сократ очень похож на всех уязвимых к болиголову людей, но не идентичен им. Поэтому предположение, что Сократ — «человек» основано на простых границах вокруг кластера людей в пространстве вещей. Мы не используем утверждения вида: «Вещи полностью соответствующие [спецификация 1 на пять мегабайт] с [описание множества характеристик] или полностью соответствующие [спецификация 2 на пять мегабайт] с [описание множества других характеристик] … — являются людьми».

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

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

А отсюда вытекает ещё одна — да, ещё одна — причина сомневаться в утверждении «можно определить слово как угодно». Учитывая суперэкспоненциальные размеры пространства концептов, очевидно, что выделение любого отдельного концепта и отбрасывание всех остальных — это акт немалой наглости. И не только для нас, но и для любого разума с ограниченными вычислительными способностями.

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

• 1. Tom M. Mitchell, Machine Learning (McGraw-Hill Science/Engineering/Math, 1997).
• 2. В оригинале используется термин inductive bias. — Прим.перев.