Содержание к диссертации
Введение
1 Восстановление зависимостей по эмпирическим данным 15
1.1 Задачи восстановления зависимостей 15
1.1.1 Классификация 17
1.1.2 Регрессия 17
1.1.3 Оценка плотности распределения 18
1.1.4 Контрастирование распределений 19
1.2 Методы отбора признаков 20
1.2.1 Определения понятия «значимый признак» 22
1.2.2 Классификация методов отбора значимых признаков 24
1.3 Обзор методов оценки среднего риска по эмпирическим данным 27
1.3.1 Теория Вапника-Червоненкиса 28
1.3.2 Оценки среднего риска по эмпирическому риску, адаптированные к данным 31
1.4 Основные выводы 34
2 Разработка метода выбора контрастирующих признаков 35
2.1 Средний риск 35
2.2 Эмпирический риск 37
2.3 Равномерная оценка Вапника-Червоненкиса уклонения эмпирического риска от среднего в задаче контрастирования 38
2.4 Оценки среднего риска, основанные на Радемахеровской сложности 2.4.1 Штраф Радемахера 41
2.4.2 Оценка среднего риска
2.5 Алгоритм выбора контрастирующих признаков 48
2.6 Основные выводы 50
3 Применение метода выбора контрастирующих принаков для поиска классов заболеваний, влияющих на возникновение злокачественных новообразований 52
3.1 Статистические данные о причинах смерти и сопутствующих заболеваниях 53
3.2 Применение метода контрастирования распределений при поиске связи между причинами смерти и сопутствующими заболеваниями
3.2.1 Рак органов пищеварения и брюшины 59
3.2.2 Рак органов дыхания и грудной клетки 64
3.2.3 Рак мочеполовых органов 67
3.3 Основные выводы 70
4 Применение метода выбора контрастирующих признаков для контроля производственного процесса 73
4.1 Выбор параметров для классификации состояний производственного процесса 73
4.2 Применение метода выбора контрастирующих признаков для контроля производственного процесса 74
4.3 Проверка результатов применения метода выбора контрастирующих признаков 78
4.4 Основные выводы 81
Заключение 82
Список основных обозначений 84
Список литературы 85
Список иллюстраций 93
- Оценка плотности распределения
- Оценки среднего риска по эмпирическому риску, адаптированные к данным
- Применение метода контрастирования распределений при поиске связи между причинами смерти и сопутствующими заболеваниями
- Применение метода выбора контрастирующих признаков для контроля производственного процесса
Оценка плотности распределения
Восстановление зависимостей по эмпирическим данным является одной из центральных областей теории статистического обучения, которая включает в себя задачу обучения по прецедентам, отбор значимых признаков, оценку качества и обобщающей способности построенной зависимости.
В части 1.1 данной главы представлен обзор задач восстановления зависимостей по эмпирическим данным. Задачи классификации, регрессионного анализа, восстановления плотностей распределений сформулированы в общем виде как частные случаи задачи восстановления функциональных зависимостей. В части 1.1 также приводятся основные идеи метода выбора контрастирующих признаков, разработанного в диссертации. Подробному изложению этого метода посвящена вторая глава.
В части 1.2 рассмотрена проблема отбора признаков. Приведены различные определения понятия «значимый признак», дан обзор и классификация существующих методов, обсуждается проблема оценки обобщающей способности метода при отборе признаков.
В части 1.3 описана задача оценки качества обучения, дан обзор оценок обобщающей способности, начиная с равномерных по классу решающих функций оценок, полученных Вапником В.Н и Червоненкисом А.Я. в 70-х годах XX века и положивших начало развитию этой теории, и заканчивая недавними работами, в которых получены оценки, адаптированные к данным.
Данная глава является обзорной. В ней вводится используемая терминология, необходимые определения и обозначения.
Методы решения задачи восстановления зависимостей по эмпирическим данным называются «методами машинного обучения». Этот обширный термин включает методы построения регрессионных зависимостей, классификацию, кластеризацию и многие другие. Рассмотрим множество объектов X Є Rn и множество ответов Y Є R Пусть на декартовом произведении X X Y задано неизвестное вероятностное распределение Р. Обозначим (х,у) случайную пару из распределения Р. Дана обучающая выборка - последовательность пар (х1,у1), (х2,у2),..., (хг,уг), состоящая из / независимых наблюдений случайной пары (х,у). Величины (х1, ...,хг) называют также входными значениями, а (у1, ...,Уг) - выходами, соответствующими входным значениям. Задача заключается в нахождении такой зависимости у = р(х), чтобы предсказанные значения у = р(х) как можно точнее аппроксимировали фактическое выходное значение у, соответствующее входу X.
Чтобы оценить насколько хорошо выбранная исследователем функция у = р(х) подходит для описания наблюдаемой связи между входом и выходом вводится так называемая штрафная функция L(y,y ), характеризующая отклонение предсказания выходного значения у от истинного значения у. Цель обучения формально может быт сформулирована как нахождение такой функции (решения), на которой минимизируется математическое ожидание функции штрафа, называемое истинным (средним) риском:
В задачах восстановления зависимостей в качестве штрафной функции часто используют квадрат разности (у —у )2. В этом случае эмпирический риск интерпретируется как средний квадрат уклонения построенной зависимости от эмпирических данных. В задачах классификации значение штрафной функции L(y,y ) равно нулю при правильной классификации объекта и 1 иначе, тогда эмпирический риск равен среднему числу ошибок на обучении, а средний риск равен вероятности ошибочной классификации при использовании данного решающего правила.
Далее в данном разделе будут рассмотрены классические задачи восстановления зависимостей, будут выписаны функционалы среднего и эмпирического риска для них.
Задачи классификации являются частным случаем восстановления функциональных зависимостей. Вектор х является набором непрерывных или дискретных признаков, выход у в задаче классификации - скалярная величина, принимающая дискретные значения из конечного множества и имеющая смысл номера или метки класса, F - класс функций, определенных на множестве значений признаков х и принимающих значения из множества значений переменной у. Штрафная функция, определенная через индикатор L(y, p(y)) = 1{у р(х)1 р(х) Є F и принимает значение 1, если с помощью функции (р(х) вектор х классифицируется правильно, т.е. выполнено у = (р(х), или значение 0 иначе.
Оценки среднего риска по эмпирическому риску, адаптированные к данным
Наиболее известной оценкой среднего риска, зависящей от данных, является оценка, предложенная В. Колчинским [50-53]. В [52] предложено оценивать эмпирический процесс путем его замены на радемахеровский процесс где независимые одинаково распределенные радемахеровские случайные величины, принимающие значения +1 и -1 с вероятностью и независимые от выборки. Процесс зависит от данных, и его значение может быть вычислено на наборе сгенерированных радемахеровских случайных величин . Для каждой функции , ( ) имеет смысл ковариации между значениями функции на выборке и независимым радемахеровским шумом. Большое значение величины sup) означает, что существует такая что, функция штрафа близка к радемахеровскому шуму, т.е. семейство функций слишком сложное, и функция, полученная минимизацией эмпирического риска над таким семействам скорее всего будет обладать плохой обобщающей способностью. Величина Радемахеровской сложности или, как ее ещё называют, штрафа Радемахера, определяется выражением l
В работе [52] оценки скорости равномерной сходимости эмпирического риска к среднему через Радемахеровсую сложность получены с помощью неравенств концентрации и симметризации.
Неравенство симметризации, связывающее математическое ожидание отклонения эмпирического риска от среднего с математическим ожиданием штрафа Радемахера имеет вид [52], [58]:
Математические ожидания в правой и левой части неравенства симметризации (1.9) берутся над различными пространствами случайных величин. В левой части неравенства математическое ожидание берется над выборкой (х1( ...,хг), а в правой части над радемахеровскими случайными величинами (51;..., 8г).
В [52] доказано, что значения величин suP p6FM( p) - Ме((р)\ и R(F) сконцентрированы вокруг их математических ожиданий. Для функции потерь, равномерно ограниченной константой U, и для любого t 0 выполнено неравенство концентрации
Аналогичное неравенство концентрации справедливо и для радемахеровского процесса. Комбинация неравенства симметризации (1.9) и неравенств концентрации позволило оценить скорость равномерной сходимости эмпирического риска к среднему через штраф Радемахера.
Пусть функция потерь равномерно ограниченна константой U, тогда для любого t 0
Неравенство (1.11) дает формулу для оценки уклонения эмпирического риска от среднего через штраф Радемахера и константу U, ограничивающую используемый класс функций. Для вычисления значения штрафа Радемахера необходимо найти супремум по классу функций, который в некоторых случаях можно вычислить аналитически.
Выразив параметр t через наперед заданную надежность т\ и раскрыв модуль в неравенстве (1.11), получим, что с вероятностью не менее 1 — 77 одновременно для всех (р(х) Є F справедлива оценка среднего риска
Выбор оптимальной функции так же, как в теории Вапника-Червоненкиса, может производиться методом структурной минимизации. Выбирается подсемейство функций, доставляющее минимум оценки среднего риска (1.12).
Задача восстановления зависимостей по эмпирическим данным сводится к задаче нахождения экстремума функционала среднего риска. Такой постановке удовлетворяют не только задачи классификации, восстановления регрессионных зависимостей или оценки плотности распределения вероятностей, но и задачи отбора признаков, которые часто являются предварительным этапом обучения.
Функционал среднего риска вычисляется с учётом закона распределения изучаемых объектов, который в общем случае неизвестен. Для оценки функционала среднего риска по эмпирическим данным используется средний риск. Величина отклонения среднего риска от эмпирического может оцениваться различными способами, связывающими вероятность отклонения с длиной выборки и сложностью класса функций. Среди этих способов лидирующее место занимают оценки, основанные на вычислении комбинаторной размерности Вапника и Червоненкиса, Fat-размерности (Кернс и Шапиро), мощности покрытия (Мендельсон), а также оценки, основанные на Радемахеровской сложности. 2 Разработка метода выбора контрастирующих признаков
Задача контрастирования распределений возникает при отборе факторов и признаков распределения которых в наибольшей степени различаются при сравнении двух классов. Примером является выбор симптомов и сопутствующих заболеваний при выяснении условий развития конкретной патологии, например, возникновения онкологического заболевания. Также такой подход может применяться при выделении набора параметров, связанных с интересующим состоянием технического объекта, например, с исправным функционированием отдельных узлов.
В второй главе описывается постановка задачи выбора контрастирующих признаков как задачи максимизации среднего риска и рассматриваются методы максимизации среднего через эмпирический с применением равномерной оценки Вапника-Червоненкиса и адаптированной к данным оценки, использующей штрафную функцию Радемахера.
Многие задачи анализа данных могут быть поставлены как задачи минимизации среднего риска. Такими задачами являются задача классификации, восстановления регрессионной зависимости, восстановления плотности распределения. Задача выбора контрастирующих признаков может быть сформулирована аналогичным образом.
Пусть X Є Rn - множество объектов, Y = {0,1} - множество классов, Р -неизвестное вероятностное распределение на X X Y. Обозначим (х, у) случайную пару из распределения Р. Объект х = (х(1), ...,х(п)) - п-мерный вектор, координаты вектора имеют смысл признаков.
Применение метода контрастирования распределений при поиске связи между причинами смерти и сопутствующими заболеваниями
Для оценки уклонения эмпирического риска от среднего можно использовать равномерную оценку уклонения математического ожидания от среднего значения [7]. Пользуясь этой оценкой, средний риск выражается через неравенства, включающие величину эмпирического риска, длину выборки и сложность класса функций, в котором оценивается средний риск. Следуя [7], введем понятие сложности класса функций F.
Рассмотрим выборку хг, ...,хг. Выборка длины /, вообще говоря, может быть разделена на два класса 21 способами. Однако нас будут интересовать только те способы разделения выборки, которые могут быть реализованы с помощью функций из класса F. Число таких разделений зависит как от класса функций, так и от состава обучающей выборки. Максимизируя число разбиений по всевозможным выборкам длины /, получим величину, независимую от состава выборки, а зависящую только от длины выборки и свойств класса функций F. Эту величину принято называть функцией роста класса функций F и обозначать mF(l). В [7] приведены свойства функции роста, способы ее вычисления и оценки.
Чтобы использовать результат Вапника-Червоненкиса о сходимости средних к математическим ожиданиям, заметим, что средний риск (2.2) является математическим ожиданием, эмпирический риск (2.6) можно интерпретировать как средневыборочное значение функции штрафа (2.1).
Функции 1п р$, для которых вычисляются значения функционалов среднего и эмпирического рисков, равномерно ограничены, поскольку для байесовских оценок справедливо неравенство (2.4), из которого следует равномерная ограниченность функций In еру:
Оценку для функции роста системы множеств S получим, учитывая, что байесовские оценки плотностей (рь(х) и (рь(х) являются гистограммами, построенными на многомерных сетках, состоящих из к ячеек. Утверждение 1. Пусть h{x) - гистограмма, построенная для к фиксированных интервалов, Н - множество таких гистограмм. Для функции роста системы множеств S = {х: h(x) c,hEH] справедлива оценка ms(2l) (21)к. Доказательство. В [7] доказано, что функция роста ms(l) любой системы S либо равна 21, либо оценивается сверху выражением Р-1, где п - минимальное число элементов, при котором никакую выборку, состоящую из п элементов, нельзя разбить на две подвыборки 2П способами с помощью элементов системы S. Ясно, что множество гистограмм, построенных для к фиксированных интервалов, порождает не более, чем 2к разбиений любой выборки, и, значит, выборка, состоящая из к + 1 элементов, не может быть разбита на две 2к+1 способами. Следовательно, для множества гистограмм, построенных для к элементов, справедлива оценка что и требовалось доказать.
Используя равномерную оценку Вапника-Червоненкиса уклонения среднего риска от эмпирического получим нижнюю оценку функционала среднего риска (2.3).
Для надежной максимизации среднего риска необходимо максимизировать эмпирический риск с учетом штрафного члена, величина которого растет с увеличением числа интервалов, для которых строятся гистограммы.
Результаты, полученные Вапником и Червоненкисом, являются универсальными, охватывают общий случай и дают оценку уклонения среднего риска от эмпирического, справедливую для всех функций из заданного класса. Отсюда следует и основная проблема оценок Вапника-Червоненкиса -завышенность полученных оценок вероятности. Современные тенденции исследований направлены на повышение точности оценок с учётом особенностей эмпирических данных [52].
В 1999 году В. Колчинский ввел в теорию статистического обучения понятие радемахеровской сложности и штрафа Радемахера. Радемахеровская сложность - мера сложности класса вещественных функций. Она интерпретируется как максимальная ковариация функций из данного класса со случайным (радемахеровским) шумом [52]. Чем сложнее множество функций, тем выше шансы найти в нём функцию, похожую на произвольный случайный шум, тем больше величина штрафа Радемахера. Выведем вид штрафа Радемахера в терминах рассматриваемой нами задачи.
Применение метода выбора контрастирующих признаков для контроля производственного процесса
В главе 3 описан статистический алгоритм поиска заболеваний, связанных с возникновением рака трех различных локализаций, на основании информации о заболеваниях, которыми страдал человек перед смертью. Этот алгоритм основан на методе контрастирования распределений, развитом в главе 2 диссертационной работы. Рассмотрены две модификации метода, использующие оценку Вапника-Червоненкиса равномерной сходимости эмпирического риска к среднему и оценки, основанные на адаптируемой к данным Радемахеровской сложности. Результаты расчетов показали, что оба подхода дают согласованные результаты, определяя, в основном, одинаковые наборы сопутствующих заболеваний. Сравнение полученных оценок функционала среднего риска показывает, что при использовании Радемахеровской сложности, уклонение среднего риска от эмпирического меньше, чем при использовании оценок Вапника-Червоненкиса, что свидетельствует об адаптации Радемахеровской сложности к данным.
В полученный список попадают заболевания, провоцирующие, либо защищающие от возникновения рака. Анализ полученных результатов среди лиц в возрастной группе 65+, умерших в 1980 году, показал, что в качестве заболеваний, «защищающих от возникновения рака», выделяются заболевания с высокой летальностью, выступающие как конкурирующие риски смерти. К таким заболеваниям были отнесены, например, ишемическая болезнь сердца, гипертония, цереброваскулярные заболевания. Исключение из рассмотрения лиц, страдающих этими заболеваниями, резко сокращает число исследуемых случаев, что не позволяет делать статистически надёжные выводы о связи оставшихся заболеваний с раком.
В диссертации приводятся результаты исследования заболеваемости раком трех наиболее распространенных форм: раком органов пищеварения и брюшины, раком органов дыхания и грудной клетки, раком мочеполовых органов. Предложенный метод устойчиво выделяет сердечно-сосудистые заболевания в качестве заболеваний, характеризующих нераковую группу при анализе всех трех рассматриваемых форм злокачественных новообразований. Сердечно-сосудистые заболевания наиболее часто приводят к летальному исходу и являются конкурирующей причиной смерти по отношению к раку.
Среди сопутствующих были выделены заболевания, выступающие в роли факторов риска возникновения рака. Для рака органов пищеварения и брюшины такими факторами являются «другие заболевания пищеварительной системы», для рака органов дыхания – « другие болезни органов дыхания», для рака мочеполовых органов – «другие болезни мочевыделительной системы». Сравнительные исследования смертности по причинам с учётом сочетанной заболеваемости позволяют составить общую структуру заболеваемости в старшем возрасте, выделить заболевания, имеющие высокую летальность и являющиеся конкурирующими причинами смерти, указать сопутствующие заболевания, провоцирующие развитие более тяжелых патологий, нередко приводящих к смерти. 4 Применение метода выбора контрастирующих признаков для контроля производственного процесса
Метод выбора контрастирующих признаков был применен для выделения значимых параметров, позволяющих наиболее точно отделить одно состояние производственного процесса от другого. Работа технической системы характеризуется множеством параметров, измеренных во времени. Существует два режима работы: один можно интерпретировать как нормальный, штатный режим, другой как режим экономичного потребления ресурсов или выход на высокий производительный уровень. Задача состоит в выявлении скрытых закономерностей в эмпирических данных и выделении параметров, связанных со сменой состояния системы.
Подобные задачи отбора признаков нередко встречаются в технологической сфере, они обычно характеризуются большим количеством измерений состояния системы во времени, высокой размерностью – десятками или даже сотнями признаков. Это затрудняет или делает невозможным ручной экспертный анализ данных, что повышает актуальность разработанного метода.
Выбор параметров для классификации состояний производственного процесса В диссертационной работе метод выбора контрастирующих признаков применялся для сокращения числа параметров при классификации одного из двух состояний производственного процесса. Такое сокращение необходимо при создании экономичной системы контроля, оперирующей лишь необходимыми параметрами с целью упрощения работы оператора и повышения надёжности автоматического принятий решения о возникновении аварийной ситуации. Выбор признаков производился по записям рядов значений 10 параметров, характеризующих работу системы, измеренных в различные моменты времени. Периоды работы системы экпертно были разделены на два класса, характеризующие два различных состояния системы. В первый класс вошли 562 измерения десяти параметров, во второй класс – 258 измерений десяти параметров. Параметры для краткости номерами от 1 до 10, расшифровка кодов приведена в Таблице 4.
Задача состоит в выборе такого подмножества параметров, на котором распределения параметров в двух представленных классах максимально различны. В диссертационной работе эта задача сводится к поиску подмножества признаков, доставляющих максимум функционалу среднего риска, и решается методом контрастирования распределений. При этом значения каждого параметра, измеренные в различные моменты времени, считаются независимыми, но значения параметров, измеренные в один момент зависимы.
Применение метода выбора контрастирующих признаков для контроля производственного процесса
Для применения метода выбора контрастирующих признаков при выделении значимых параметров для классификации состояния производственного процесса строятся многомерные гистограммы распределений признаков в каждом из классов. Гистограммы строятся согласно упорядочиванию признаков, описанному ниже. При построении гистограмм области значений признаков делятся на равные интервалы. Наилучшее число интервалов определяется перебором в процессе применения метода контрастирования из условия достижения максимума нижней оценки среднего риска.
На первом шаге метода контрастирования признаки рассматриваются по одному и строятся одномерные гистограммы распределения признаков в двух классах. Среди признаков выбирается признак, доставляющий максимум эмпирическому риску. Далее рассматриваются все возможные пары сочетаний оставшихся признаков с признаком, зафиксированном на предыдущем шаге. Для каждой пары строятся двумерные гистограммы распределения в каждом классе, вычисляются значения эмпирического риска и выбирается такая пара признаков, для которой значение эмпирического риска максимально. На следующем шаге к уже найденной паре добавляется третий признак из оставшихся, строятся трехмерные гистограммы. На втором этапе метода контрастирования вычисляется оценка среднего риска через эмпирический риск, учитывающая число признаков, участвующих в вычислениях. В главе 2 диссертационной работы рассмотрены две оценки среднего риска по эмпирическим данным: первая основана на результатах теории Вапника-Червоненкиса, вторая учитывает особенность данных и использует штрафную функцию Радемахера.
