Математическая теория KXEN

Новые подходы к предсказательному моделированию с очень большим числом переменных


Мишель Бера (Michel Bera)

Мишель Бера – признанный в мире специалист по алгоритмам машинного обучения, доктор наук, сотрудник Международного Института Статистики, член Французской Королевской Ассоциации Статистиков, один из основателей и главный научный руководитель KXEN Inc.

Работа российского математика Владимира Вапника (AT&T Labs) заставляет нас обратиться к истокам теоретической статистики - общим подходам параметрической теории Фишера, работам Гливенко, Кантелли и Колмогорова, начавшимся еще в 1930-х годах. Сегодня стало возможным в приемлемые для практики сроки моделировать миллионы событий, описываемых тысячами переменных. Это открывает большие перспективы в различных областях деятельности – страховании и банковском деле, медицине и телекоммуникациях - там, где хранилища данных содержат большие объёмы информации.

 

 

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

Основная деятельность Владимира Вапника приходится на 1970-е годы, когда он опубликовал две крупные работы ([1][2]), заложившие методологическую основу «Статистической теории обучения». На этот новый подход к анализу данных мы и хотели обратить Ваше внимание.

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


Теория познания концепции «простой модели»: от Аристотеля к учению Оккама

В соответствии с подходом Канта, все научные теории должны состоять из трех элементов:

  • Описание проблемы;
  • Решение;
  • Доказательство.

Задолго до него Аристотель ([3][4]) утверждал, что лучше представлять природу самым простым и кратким образом, используя при этом равноценные по сложности модели. Уильям Оккам (1285-1349) со своей знаменитой «бритвой» установил следующий принцип: если две теории описывают проблему одинаково хорошо, то предпочтительнее та из них, которая делает это проще.

В 1930-х годах два основных подхода, один из них -  Гливенко – Кантелли, а второй – Фишера, привели к появлению совершенно разных направлений в работе с данными.

Гливенко и Кантелли исследовали равномерную сходимость эмпирической функции распределения Femp с выборкой L случайных независимых переменных, равномерно распределенных внутри R, (X1,.., XL), для каждой переменной Х:

Femp (x) = 1/L{Card{Xi|Xi<x},

стремящуюся к функции распределения

F(x)=P(X < x).

Они установили, что существует сходимость к 0 с вероятностью supx |F(x) – Femp(x)| для выборки объема L. Продолжив эту работу, Колмогоров и Смирнов установили знаменитое ограничительное правило для данного статистического значения.

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

Уникальность подхода Фишера и его выдающиеся результаты позволили добиться очень высокой достоверности в прикладной статистике, отделив её от статистики теоретической. Однако уже в 1960-х годах, с появлением первых больших файлов данных, содержащих многочисленные сильно коррелированные переменные, стало ясно, что «традиционные прикладные» методы не справятся с построением моделей приемлемого качества для наборов данных с большим числом переменных. Так появилось «проклятие размерности». При этом те методы, которые все-таки давали результативные решения, но в то же время были бездоказательными (к примеру, PCA или первые поколения нейронных сетей), воспринимались сообществами статистиков как дилетантские.

Прошло еще 25 лет, и с появлением первых ощутимых результатов применения нейронных сетей (1990 г.) зародилась надежда, что «проклятие размерности» может быть преодолено. Основной целью Статистической теории обучения (SLT, Statistical Learning Theory), предложенной Вапником в 1995 году, было создание новой системы для решения задач предсказательного моделирования. В отличие от предыдущих подходов, новый метод основывался на строго доказанной статистической теории.

Возьмем характерный пример, отражающий преимущества этого нового научного подхода. Может не укладываться в голове, как можно выполнить расчет по модели, содержащей 3000 описывающих переменных, но построенной на данных всего 100 наблюдений, что, кстати, характерно для задач современной генетики. В мире Интернета систематическая регистрация в реальном времени шаблонов поведения посетителей сайта часто порождает огромные объемы информации, обусловленные его посещением десятками миллионов людей. Каждое из таких посещений содержит тысячи переменных. Раньше не было возможности обработать всю эту информацию. Такая необходимость породила новое поколение моделей, которые акцентируют внимание на надежности, другими словами, на стабильности поведения модели на новом наборе данных, отобранном из той же самой совокупности данных, что и данные для построения, и при той же скорости расчетов. Высокая скорость расчетов необходима, когда, например, мы должны всего за несколько секунд дать разрешение на выдачу кредита или страхового полиса, когда используются модели с сотнями или тысячами переменных.


Главная проблема обучения (построение модели на существующих данных)

Мы имеем набор данных, состоящий из рядов (событий), каждый из которых включает в себя значения n переменных и результирующую колонку («бизнес-вопрос»). Таким образом, мы можем представить каждый ряд в виде [x1,…,xn |y], где y – «бизнес-вопрос».

Пусть X - вектор  Rn : X = (x1,…,xn). Теперь попытаемся построить модель  Rn для  R (регрессия) или Rn в  [0.1] (классификация). Чтобы сделать это, мы будем использовать модель для вычисления функции f(X,w), результатом вычисления которой является y, где:

  • w - параметр Rp, который определяет модель;
  • Zi = (Xi,y) - возможные значения данных;
  • Q (z,w) - частота ошибок модели, когда f(X,w) равно y;
  • P(z) - неизвестный закон распределения данных Z.

Наша цель - минимизировать вероятность риска w: R(w)=∫Q(z,w)dP(z). Чтобы сделать это, мы имеем только обучающие данные L (z1,…,zL), которые, как мы считаем, имеют неизвестный нам закон распределения P(z). В данном случае мы стараемся минимизировать эмпирический риск:

E(w)=(1/L)∑{Q(zi,w)|I = 1,…,L}.

Достоинство теории Вапника заключается в том, что риск R увеличивается на сумму эмпирического риска, определяемого в течение всего периода обучения определенное число раз.

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

Пусть из семейства J - функция, описывающая модель: Y=f(X,w). Теория Вапника присваивает целое число h множеству функций J из  Rn в  R, называемое размерностью Вапника-Червоненкиса (VC) множества J. Для множества J это число характеризует его способность разделять точки пространства Rn: множество J функций Rn в R разбивает множество точек (x1,…,xL)  из Rn. Если (см. рис.) L точек разделить на m белых и L–m черных точек (2L возможных вариантов), получим функцию f из J, принимающую положительные значения в «белых» и отрицательные значения в «черных» точках. Множество J функций  Rn в  R, таким образом, имеет VC–размерность h если: существует группа из h точек  Rn, которая может быть разделена, и не существует группы h+1 векторов, которыми можно их разделить. Мы показали на примере, если J - группа прямых линий на плоскости, то h=3.

Таким образом, основная теорема Вапника заключается в следующем:

  • обучение модели (X,w) возможно, тогда и только тогда, когда множество моделей имеет конечное значение размерности h;
  • с вероятностью 1-q,

R(w) < E(w) + √ [h(ln(2L/h) + 1) – ln(q)]/L.

Вышеприведенное уравнение является основополагающим:

  • Вероятность ошибки модели, применяемой к реальным данным, возрастает с вероятностью 1-q (предельный риск, т.е. q=1% или 0.01) за счет суммарного эмпирического риска, определяемого в течение всего периода обучения определенное число раз.
  • Количество переменных в задаче не оговаривается: теорема подразумевает, что интеллектуальный подход к статистическому моделированию должен быть пересмотрен.
  • Также не оговаривается неизвестный закон распределения P(z), о виде которого не выдвигается никаких гипотез.
  • Выражение справа от Е (w) стремится к нулю, при стремлении к нулю h/L.

Это уравнение показывает, что частота ошибок обычной модели может быть контролируемой, когда модель применяется к реальным данным, даже если параметров достаточно много, при том условии, что модель f(X,w) выбирается из множества функций J, где VC-размерность h мала по сравнению с L. Кроме того, даже когда модель включает миллионы переменных, если отношение h/L остается низким (1/20 на практике считается хорошей величиной), модель считается пригодной и достоверной, поскольку она будет выдавать результаты, сравнимые с теми, которые были получены при построении модели (на обучающем наборе данных).


Основные положения SRM (Structured Risk Minimization - Минимизации Структурного Риска)

В основе SRM лежит следующий подход: искомая модель f(X,w) выбирается из некоторого  класса моделей Jm, исходя из оценки точности модели (соответствует, E(w)) и априорной оценки ее надежности (оценивается по обратной величине выражения  √ [h(ln(2L/h) + 1) – ln(q)]/L). Чтобы сделать это, выделяется набор упорядоченных по сложности вложенных классов моделей J1, J2,...,Jp, то есть таких, для которых выполняется условие h<h2< ….<hp. При этом лучшая модель множества Jq будет более точной, чем лучшая модель множества Jp, если p меньше q. Однако, раз hp<hq , модель будет менее достоверной.

Концепция вложенных множеств функций Jm может быть воплощена несколькими способами:

  • архитектурой нейронных сетей (h возрастает с ростом числа слоев);
  • степенями полинома (h возрастает с ростом степени);
  • управлением весами в нейронных сетях (h изменяется с изменением диапазона допустимых значений весов);
  • уровнем сглаживания при фильтрации данных и другими.

SRM-подход (который присутствует на каждом этапе работы каждого из компонентов KXEN) означает замещение традиционной схемы поиска модели:

  1. выдвижение гипотезы о (неизвестном) статистическом распределении данных;
  2. согласие с «проклятием размерности» (большая размерность задачи приводит чрезмерно большому времени вычислений) и отказ от поиска закономерности, либо априорный выбор  небольшого подмножества переменных для анализа;
  3. поиск лучшей статистической модели всеми известными методами и проверка нулевых гипотез;

на новую:

  1. изучение и поиск оптимального с точки зрения SRM множества J и контроля его VC-размерности h;
  2. учет всех независимых переменных;
  3. поиск наилучшей модели с точки зрения качества и надежности.


Методы анализа, основанные на концепции SRM

Простейшим примером множества J является полином первого порядка с n переменными:

Y=P(X1,…,Xn)

В своей теории Вапник вывел уравнения оптимальной непротиворечивости для моделей вида Y= (w.X) + b, где w - параметры, искомые при построении модели, а (w.X) - скалярное произведение вектора параметров w и вектора переменных X. В результате получились уравнения Лагранжа и модель оптимизации второго порядка с линейными граничными условиями. Эти выводы составили ядро широко известного сейчас Метода опорных векторов (Support Vector Machines, SVM). Этот метод предполагает изменение VC-размерности моделей в основном с помощью изменения набора характеристик. Рассмотрение SVM лежит за рамками данного документа. Отметим лишь, что данный метод получил широкое использование при решении задач с «широкими» наборами данных (когда столбцов-переменных в таблице заметно больше, чем записей).

На базе своей теории Вапник сформулировал еще один аналитический метод, получивший название по названию теории - «SRM-подход». В нем управление VC-размерностью полинома осуществляется в соответствии с теорией решения задач со слабым схождением. Другими словами, задач с крайне малодостоверным численным решением, обусловленным наличием шума в данных (что типично для данных, относящихся к людям и их поведению). Путем искусственного добавления шума в данные изменяется h и, следовательно, достоверность модели. Завышенное зашумление данных приводит к построению некачественной модели, но эта модель будет очень стабильной, если ее применить к новым данным. Полное отсутствие шума приводит к модели, с высокой точностью описывающей обучающие данные, но которая будет крайне недостоверной при расчетах на новых данных, то есть будет нестабильна. SRM-подход обеспечивает наиболее сбалансированное решение.

Этот метод был разработан Вапником уже после формулировки SVM. Он лучше, чем SVM приспособлен к работе с очень большими наборами данных (миллионы строк, тысячи переменных). Таким образом, мы можем строить модели на больших наборах данных (производя необходимые преобразования строк данных в ходе процесса) экстремально быстро: к примеру, построение модели в задаче с 250 описывающих переменных (символьные, непрерывные и целые величины) и миллионом наблюдений (строк) требует всего около 100 минут для обычного ПК, по сравнению с 3-мя неделями работы традиционными статистическими методами (когда все данные обрабатываются столбец за столбцом).

Приведем только один пример: подход SRM (механизмы К2С для преобразования переменных и K2R для робастной регрессии) позволил KXEN построить (для одной крупной страховой компании во Франции) скоринговую модель страхования жилых автоприцепов. При этом было обработано огромное количество разнородной информации всего за 85 секунд. На построение аналогичных моделей у самых лучших специалистов-статистиков компании уходило около 2-х недель. Более того, по сочетанию характеристик надежности и качества построенная модель заметно превзошла все модели построенные статистиками ранее.


Приложения для страхования

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

Метод SRM может преимущественно заменить методы обеспечения надежности, применяемые при оценках монообъемных автомобилей. Фактически, исторические данные по заключенным договорам представляют собой огромный объем информации для анализа (xi), например, марка и модель автомобиля, дата контракта, номерной знак, цвет, адрес держателя страхового полиса. Добавление к этому массиву информации данных по страховым выплатам для каждого контракта (yi) позволяет последовательно оценить размер страховой премии для каждой пары (владелец, автомобиль) и существенно снизить степень риска. В данном случае способность модели уменьшить масштабы задачи является определяющим фактором.

Применение SRM к базе данных по страховым требованиям обеспечит надежную оценку открытых требований и, таким образом, минимизирует разногласия в требуемом обеспечении для неудовлетворенных исков. Влияние, которое это может оказывать на компанию, гораздо больше, чем может показаться на первый взгляд, т.к. резервы для неудовлетворенных исков является объектом высокого налогообложения. В данном случае информация (xi) складывается из многих компонентов, уже известных на момент подачи требования, т.к. эта информация находится в БД компании. Переменная yi может обозначать полную стоимость требования и время, необходимое на его исполнение. Таким образом, с помощью KXEN компания может регулировать издержки по требованиям самым оптимальным способом, избегая методов усредненных оценок, результаты которых очень часто оказываются неудовлетворительными. В действительности, поскольку распределение требований основано на отношении «размер последствий / уровень риска», исключительные требования могут сильно исказить расчеты и простое определение пикового значения иногда приводит к неубедительным результатам. В таких случаях способность модели распознавать только существенно-влияющие переменные является серьезным преимуществом.

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


Заключение

Подход Владимира Вапника, лежащий в основе концепции предсказательного моделирования, позволяет решить задачу обработки больших объемов информации. Набор теорем, основанных на концепции размерности Вапника-Червоненкиса для множества функций, и SRM-стратегия (Structured Risk Minimization) составляют общую теорию, на основе которой многие ранее существовавшие методы были заново переосмыслены, поняты и обоснованы, такие, как например, методы гребневой регрессии и временные ряды. Это означает конструктивный вызов традиционной статистике, как уже это произошло в решении проблем, связанных с использованием информации из CRM-систем.

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


Литература:

  1. V. Vapnik – The Nature of Statistical Learning Theory, Springer-Verlag, 1999 (2nd  edition)
  2. V. Vapnik - Statistical Learning Theory – Wiley,1998.
  3. Nello Cristianini – John Shawe Taylor; Support Vector Machines and other kernel-based learning methods, Cambridge University Press, 2000.
  4. Alexander Smola, Peter Bartlett et al., Advances in Large Classifiers, MIT Press, 2000.
  5. Bernard Scholkopf, Cristopher Burges et al., Advances in Kernel Methods, MIT Press, 1999.


Материалы в Интернете:

  1. http://www.cscs.umich.edu/~crshalizi/reviews/vapnik-nature/ - обзор книги Вапника "The Nature of Statistical Learning Theory"
  2. http://www.clrc.rhul.ac.uk/people/vlad/ - страничка Владимира Вапника, со списком изданных работ, в том числе, перечисляются книги по SLT.
  3. http://www.learning-with-kernels.org/sections - 5-й  раздел "Elements of Statistical Learning Theory"