Про "Проклятие размерности" (Curse of dimensionality)

В статье "When U.S. air force discovered the flaw of averages" описывается катастрофическая ситуация сложившаяся с безопасностью полётов в 1940-х годах в американской армии. В день разбивалось до 17 пилотов. При этом проблем с оборудованием самолётов не было, а возможные ошибки пилотов не могли объяснить такое количество аварий. Лётчики плохо контролировали самолёты, несмотря на большой опыт.

Причина крылась в дизайне кабины пилота. В 1926 году инженеры измерили физические параметры нескольких сотен пилотов (рост, вес, длина рук и ног, и т.д.), усреднили их и использовали эти данные для дизайна некой 'стандартной' кабины, которая в теории должна была быть удобна большинству.

Сначала возникла мысль, что возможно пилоты стали больше с 1926 года и измерения повторили уже для 4063 пилотов, сняв по 140 измерений с каждого. Но и это не помогло - кабина всё равно оставалась неудобна почти всем.

Как вы уже поняли, всё объясняется явлением известным как "проклятие размерности". Оно заключается в том, что с ростом размерности пространства плотность наблюдений (точек) в этом пространстве очень быстро уменьшается.

Допустим мы измерили первый параметр (рост) и установили такой интервал значений (например от 165 до 185 см), что половина всех лётчиков попадает в этот интервал. Значит, если мы берём случайного пилота, то с вероятностью \(p_1=0.5\) кресло ему подойдёт. Теперь добавляем второй параметр (длина рук), ищем соответствующий интервал значений и получаем, что с вероятностью \(p_2=0.35\) кабина сконструированная с соответствующим расстоянием до штурвала будет удобна случайному пилоту.

Теперь вопрос - с какой вероятностью случайному пилоту будут удобны и кресло и расстояние до штурвала в данной кабине? Предполагая что эти события независимы (что не совсем так, но это скорее всего будет верно для других пар параметров), вероятность равна произведению \(p_1 * p_2 = 0.175\).

Соответственно, для \(N\) параметров вероятность будет меньше \(p^N\), где \(p\) - наибольшая вероятность среди \((p_1,p_2,...,p_N)\). Если параметров всего 15, то все параметры кабины подойдут примерно никому из 4000 пилотов: \[ (0.5^{15} * 4063) = 0.12 \]
А в оригинальной статье было отмечено, что общее количество параметров больше сотни. Вывод получается такой, что нет никакого среднего пилота (и вообще человека). И кресло и другое оборудование должно настраиваться индивидуально под каждого.

Скоринг в банке

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

В самом деле, давайте рассмотрим куб размерности \(N\) единичного объёма \(1\). Допустим наблюдения в пространстве распределены равномерно и нам нужно выбрать подпространство содержащее примерно  \(0.1\) всех из них.  Если \(N = 1\), тогда искомое подпростанство будет задано ребром длины \(0.1\). Если \(N = 2\), то нам уже нужно ребро длины \(0.1 ^{\frac{1}{2}} = 0.32\). Ну и в общем случае длина будет \(d = 0.1^{\frac{1}{N}}\). Давайте построим график

Из графика видно, что с увеличением размерносности, нам нужно брать экспоненциально увеличивающуюся долю от всего интервала значений переменных, описывающих наблюдения (клиентов). В итоге, для того чтобы найти \(10\%\) клиентов похожих по всем рассматриваемым признакам на какого-то "среднего" клиента, нам понадобится почти вся база данных.

Ссылки

1. When U.S. air force discovered the flaw of averages
2. Discussion on HN