WWW.NET.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Интернет ресурсы
 

«УДК 519.7 ОЦЕНКА НАДЕЖНОСТИ АЛГОРИТМА КЛАССИФИКАЦИИ НА ОСНОВЕ НОВОЙ ИНФОРМАЦИОННОЙ МОДЕЛИ1) © 2013 г. С. И. Гуров (Москва 119992, Ленинские горы, МГУ, ВМиК) e ...»

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2013, том 53, № 5, с. 808–815

УДК 519.7

ОЦЕНКА НАДЕЖНОСТИ АЛГОРИТМА КЛАССИФИКАЦИИ

НА ОСНОВЕ НОВОЙ ИНФОРМАЦИОННОЙ МОДЕЛИ1)

© 2013 г. С. И. Гуров

(Москва 119992, Ленинские горы, МГУ, ВМиК)

e mail: sgur@cs.msu.su

Поступила в редакцию 26.04.2011 г.

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

В основе подхода – нетрадиционная информационная модель таких алгоритмов. Приведены примеры новых оценок в сравнении с обычными статистическими. Библ. 12. Фиг. 1. Табл. 2.

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

DOI: 10.7868/S0044466913050050

1. ВВЕДЕНИЕ. ПОСТАНОВКА ЗАДАЧИ

Проблема оценки надежности алгоритмов классификации является одной из основных в тео рии обучения по прецедентам. Данной проблеме посвящено большое количество работ (обзор см. в [1]). При этом в основном потоке публикаций рассматривается постановка задачи в рамках того или иного развития известной теории Вапника–Червоненкиса (VC теория).

В данной работе, являющейся развитием [2], представлены результаты в решении указанной задачи, полученные с использованием новой информационной (в терминах формальной зависи мости “вектор параметров–класс”) модели алгоритма классификации, свободной от положений VC теории и классического статистического подхода к оценке вероятности случайных событий.



Рассматривается классифицирующий алгоритм A – произвольный алгоритм детерминирован ной классификации без отказов на два класса объектов из некоторого пространства. Считает ся, что создание алгоритма A проводилось (возможно, исключительно) на основе обучающей по следовательности прецедентов (элементов из с известной классификацией) так, чтобы макси мизировать надежность алгоритма A. Необходимо оценить вероятность P правильной классификации алгоритмом A произвольного объекта из. Оценка осуществляется тестирова нием алгоритма A на конечной контрольной выборке прецедентов. При этом единственными данными для оценки вероятности P является информация о том, что на контрольной выборке длины n алгоритм A совершил m ошибок.

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

Результатом принятия указанного требования, назовем его Гипотезой 2 (гипотеза 1 встретится ниже), становится необходимость решать непростые, а подчас и неразрешимые вопросы опреде ления различных характеристик класса таких, как емкость, функция роста, коэффициент раз нообразия и др. (о данных трудностях и возможных путях их преодоления см., например, в [1], [3], [4]). Кроме того, указанная гипотеза часто не соответствует реальному процессу построения классифицирующих алгоритмов. Наконец, одна и та же дискриминантная функция на может быть получена реализацией различных алгоритмов, принадлежащих разным классам, что приве дет, вообще говоря, к разным оценкам надежности осуществляемой ею классификации.

1) Работа выполнена при частичной финансовой поддержке РФФИ (код проекта 10 01 00131 а) и компании ЗАО “Интел А/О”.

ОЦЕНКА НАДЕЖНОСТИ АЛГОРИТМА КЛАССИФИКАЦИИ 809

Возможно, что VC теория, являющаяся, по сути, теорией равномерной сходимости частот к вероятностям по классу событий, несмотря на указанные теоретические трудности обоснования ее применения к задаче оценки надежности классификации, приводит к результатам, адекватно описывающим практику. Но и это не имеет места: общеизвестно, что она дает чрезвычайно за ниженные оценки надежности, и этот факт является причиной постоянных попыток ее модифи кации с целью приблизить получаемые оценки к реально наблюдающимся при решении практи ческих задач. (VC теория может успешно применяться в распознавании образов при адекватно сти гипотезы 2 процессу построения и/или оценки надежности классификаторов, например, когда классификатор действительно выбирается из ранее фиксированного семейства F или оценка P определяется по обучающей выборке (скользящий контроль) и т.д.) В данной работе оценки надежности алгоритма A получены на основе новой информацион ной модели алгоритмов классификации. Напомним, что информационная модель, в отличие от математической, предполагает описание поведения объекта не с помощью уравнений, соотно шений, закономерностей и т.д., моделирующих реальные физические процессы, а представляет его в терминах формальных зависимостей “вход выход”, обычно никак не связанных с указан ными процессами и обеспечивающих только, по возможности – максимально, правильное на хождение реакции объекта на данный входной сигнал (“черный ящик” в кибернетике).

2. КЛАССИЧЕСКИЙ ПОДХОД

В различных подходах к решению указанной выше задачи часто принимается ряд предполо жений (например, о типах распределений), в результате чего для оценки P требуются трудно определимые или даже ненаблюдаемые параметры (см. [3]). Различного типа оценки вероятно сти P, полученные в рамках классических статистических моделей и без привлечения дополни тельных предположений, приведены в [5].

Во всех упомянутых выше подходах используется Гипотеза 1. На пространстве образов задано (может быть неизвестное) распределение веро ятностей P(X), X, и любой рассматриваемый набор образов x1, x2, …, xn из считается (если явно не указано иначе) реализацией независимой выборки n случайных величин из генеральной сово купности с распределением P(X).

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

1. Получение описания объекта x.

2. Получение значения r случайной величины, равномерно распределенной на отрезке [0, 1].

3. Сравнение r с внутренним параметром P [0, 1] алгоритма.

4. Выдача правильного ответа о принадлежности x, если r P, и неправильного – в противном случае.

Можно считать, что описание x содержит скрытый двузначный параметр z, кодирующий при надлежность x к данным классам, а классификация осуществляется, опираясь на “подсмотрен ное” алгоритмом значение z. Статистическая модель, соответствующая данной информацион ной – классическая урновая схема Бернулли.

Представляется, однако, что, именно в силу своей универсальности, схема Бернулли является слишком грубой формализацией процесса классификации, осуществляемой алгоритмом A.

Она, например, не учитывает факт построения (настройки) A по обучающейся последовательно сти, в силу чего большие значения искомого параметра P более вероятны, чем малые, и, более то го, P 1/2.

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

3. НОВАЯ ИНФОРМАЦИОННАЯ МОДЕЛЬ КЛАССИФИЦИРУЮЩЕГО АЛГОРИТМА

Предлагаемая информационная модель IM2 алгоритма классификации базируется на следу ющих предположениях.

(А) Информация о значениях n (длина тестовой последовательности прецедентов) и m (число ошибок классификации) является достаточной и адекватной для оценки вероятности P.

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ том 53 №5 2013 810 ГУРОВ (Б) Каждый классифицирующий алгоритм характеризуется значением некоторого скрытого не случайного, но неизвестного параметра t [0, 1], который определяет его степень “необучен ности”.

Условие (А) будет выполняться, например, когда экзаменационная выборка независима от обучающей, т.е. при справедливости гипотезы 1. Понятно, что заведомо m n/2, поскольку ина че можно вернуться к этапу построения алгоритма и инвертировать решающее правило.

Условие (Б) описывает предлагаемую информационную модель функционирования алгорит ма классификации как процесс из 4 х шагов. Первые два из них совпадают с соответствующими описанными для классической модели в предыдущем разделе.

Далее осуществляются следую щие шаги:

3) сравнение r с внутренним параметром t [0, 1] алгоритма;

4) в случае t r (выдача правильного ответа о принадлежности x, в противном случае) выдача правильного ответа с вероятностью p.





Можно, как и ранее, считать, что описание x содержит скрытый параметр z, и алгоритм на ша ге 4) в первом из указанных случаев – всегда, а во втором – с вероятностью p выдает “подсмот ренное” значение z и с вероятностью 1 – p – ему противоположное. Статистическая модель, со ответствующая данной информационной, очевидно, описывается как двухуровневое испытание по урновой схеме Бернулли.

Вследствие обучения алгоритма A, на последнем шаге работы модели IM2 значение вероятно сти p правильного ответа будет не менее 1/2 и этот минимум реализуется при условии равнове роятного появления объектов из каждого класса. Таким образом, 1/2 p. Точное значение p, оче видно, неопределимо. Однако в рамках предлагаемой модели IM2 всегда можно положить p = 1/2, корректируя соответствующим образом параметр t. При этом p 1/2 не дает возможности осуще ствить приведенное выше рассуждение, что явно проявляется в случае t = 1, рассмотренном ни же. Поэтому далее мы будем полагать p = 1/2, получая, в крайнем случае, загрубленные оценки соответствующих параметров.

В данных предположениях вероятность P правильной классификации произвольного объекта оценивается как t m P = 1 – t + tp 1–, 0 t 1. (1) 2 n Теперь наша задача – оценить значение t. Это можно сделать, построив на основе приведен ной информационной модели IM2 алгоритма две его статистические модели: дискретную и не прерывную.

Дискретная статистическая модель (SM2D). Считаем, что [(1 – t)n] элементов контрольной выборки алгоритм отклассифицировал правильно, “подсмотрев” значение параметра z, а клас сификация остальных объектов – результат случайного угадывания с вероятностью успеха p.

Непрерывная статистическая модель (SM2C). Считаем, что классификация каждого объекта происходит по модели IM2, описанной выше.

SM2D может более соответствовать реальному процессу классификации в случае, когда на вход алгоритма подаются совокупности описаний образов, а SM2C – когда такие описания по даются последовательно по одному. В отсутствие какой либо информации о характере процесса классификации предпочтительнее использование SM2C. Заметим, что данные модели соответ ствуют осреднению “по времени” и “по совокупности” соответственно в рамках эргодической теории случайных процессов.

В IM2 граничные значения t означают, что: при t = 0 удалось построить алгоритм, всегда пра вильно осуществляющий классификацию любого предъявляемого объекта; при t = 1 построен ный алгоритм выдает случайный (с вероятностью P = p – правильный) ответ о принадлежности объекта (для чего не требуется даже обращения к его описанию).

В рамках предлагаемой модели мы описываем реальный алгоритм некоторым значением t, ле жащим между этими крайними идеальными случаями. Таким образом, правильная классифика ция в предлагаемой модели обеспечивается либо построенным безошибочным решающим пра вилом, либо является результатом случайного угадывания. (Ср. с двойственным подходом в [6], где ошибка прогнозирования разлагается на ошибку оптимального прогноза и шум.) Общепринятыми являются следующие возможности определить параметр t: 1) из условия максимума правдоподобия и 2) по апостериорному распределению (максимум апостериорной

–  –  –

вероятности, математическое ожидание, медиана, интервальные оценки) в рамках частотного и бейесовского подхода соответственно. Ясно также, что при равномерном априорном, апостери орное распределение есть нормированная функция правдоподобия.

–  –  –

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

В качестве примера приведем в нижеследующих таблицах некоторые интервальные оценки (P –, P +) достоверности = 0.90, полученные по SM2C в рамках бейесовского подхода (SM2C B) при равномерном априорном распределении t, а также для сравнения классические (как обычно, значение P + расположено под P –). Классические интервалы (модель SM1) найдены, исходя из [8].

Уже в приведенных примерах видно сокращение, по сравнению с классическим подходом, ве личин интервалов.

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

6. ВЫВОДЫ Предлагается информационная модель, более адекватно описывающая работу классифици рующего алгоритма, чем классическая. Модель не использует являющуюся слабым местом VC теории гипотезу 2 об априорном задании класса, из которого выбирается алгоритм. На осно ве введенной модели возможно получение более точных, чем классические, оценок надежности Таблица. = 0.90

–  –  –

классификации. Дальнейшее уточнение оценок при малых m возможно путем отказа от предпо ложения о равномерности априорного распределения с использованием принципа согласован ности (см. [12]).

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

Автор признателен Ю.И. Журавлёву за неизменную поддержку и В.Е. Бенингу за полезные консультации. Особая благодарность Е.А. Марченко, выполнившему расчеты неклассических оценок.

–  –  –

СПИСОК ЛИТЕРАТУРЫ

1. Воронцов К.В. Обзор современных исследований по проблеме качества обучения алгоритмов // Таврич.

вестн. информатики и матем. 2004. № 1. С. 5–24.

2. Гуров С.И. Информационная модель алгоритма классификации и оценка его надежности / Интеллек туализация обработки информации: 8 я междунар. научн. конф. (ИОИ 8). Кипр, г. Пафос, 17–23 ок тября 2010 г. Сб. докл. М.: МАКС Пресс, 2010.

3. Воронцов К.В. Комбинаторная теория надежности обучения по прецедентам. Дис.... док. физ. матем.

наук. 05 13 17. ВЦ РАН, 2010. 271 с. (http://www.machinelearning.ru/wiki/images/b/b6/Voron10doct.pdf.)

4. Лбов Г.С., Старцева Н.Г. Логические решающие функции и вопросы статистической устойчивости ре шений. Новосибирск: Изд во Ин та матем., 1999.

5. Гуров С.И. Оценка надежности классифицирующих алгоритмов. М.: МГУ ВМК, 2002.

6. Ицхоки О. Выбор модели и парадоксы прогнозирования // Квантиль. 2006. № 1. С. 43–51.

7. Гуров С.И. Оценка вероятности 0 события // Вестн. Тверского гос. ун та. Сер. Прикл. матем. 2009.

Вып. 3. № 28 (14). С. 55–66.

8. Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 1965.

9. Закс Л. Статистическое оценивание. М.: Статистика, 1976.

10. Кендал М., Стюарт А. Статистические выводы и связи. М.: Наука, 1973.

11. Уилкс С. Математическая статистика. М.: Наука, 1967.

12. Гуров С.И. Интервальное оценивание на основе принципа согласованности // Вестн. Тверского гос.

ун та. Сер. Прикл. матем. 2008. Вып. 9. № 14 (74). С. 77–93.

–  –  –



Похожие работы:

«Н. Н. Самылкина Построение тестовых заданий по информатике 3 е издание (электронное) Москва Лаборатория знаний УДК 004.9 ББК 32.97 С17 Самылкина Н. Н. С17 Построение тестовых заданий по информатике [Электронный ресурс] : методическое пособие / Н. Н. Самылкина. — 3-е изд. (эл.). — Электрон. текстовые дан. (1 файл pdf...»

«DOI: 10.18698/0236-3933-2016-2-53-66 УДК 517.925:519.71 ПЛАНИРОВАНИЕ ПРОСТРАНСТВЕННОГО МАРШРУТА ПОЛЕТА БЕСПИЛОТНОГО ЛЕТАТЕЛЬНОГО АППАРАТА С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЧАСТИЧНО ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Тань Лиго, А.В. Фомич в е МГТУ им. Н.Э. Баумана, Москва, Российская Федерация e-m...»

«РЕГИОНАЛЬНАЯ ИНФОРМАТИКА "РИ-2012"ЮБИЛЕЙНАЯ ХIII САНКТ-ПЕТЕРБУРГСКАЯ МЕЖДУНАРОДНАЯ КОНФЕРЕНЦИЯ Санкт-Петербург, 24-26 октября 2012 года ПРОГРАММА КОНФЕРЕНЦИИ Санкт-Петербург http://spoisu.ru ...»

«Том 9, №2 (март апрель 2017) Интернет-журнал "НАУКОВЕДЕНИЕ" publishing@naukovedenie.ru http://naukovedenie.ru Интернет-журнал "Науковедение" ISSN 2223-5167 http://naukovedenie.ru/ Том 9, №2 (2017) http://naukovedenie.ru/vol9-2.php URL статьи: http://naukovedenie.ru/PDF/20TVN217.pdf Статья опублико...»

«Технологический институт – филиал ФГБОУ ВО Ульяновская ГСХА РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И СЕТИ В ОТРАСЛИ (наименование дисциплины (модуля) Направление подготовки 19.03.03 Продукты питания ж...»

«Применение управляющих структур для организации вычислительного процесса ИНФОРМАТИКА И МАТЕМАТИЧЕСКАЯ ГЕОФИЗИКА УДК 518.5: 622.271.4 И. В. Назаров ПРИМЕНЕНИЕ УПРАВЛЯЮЩИХ СТРУКТУР ДЛЯ ОРГАНИЗАЦИИ АДАПТИВНОГО ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА МОДЕЛИРОВАНИЯ ПЕРЕВАЛКИ ВСКРЫШИ ДРАГЛАЙНАМИ Предложена сетевая структура формализации технолог...»

«Новые возможности применения пассивного микросейсмического мониторинга ИНФОРМАТИКА И МАТЕМАТИЧЕСКАЯ ГЕОФИЗИКА УДК 004.93:550.8 Д. Н. Гапеев, Г. Н. Ерохин С. В. Родин, Р. Д. Седайкин, И. И. Смирнов НОВЫЕ ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ ПАССИВНОГО МИКРОСЕЙСМИЧЕСКОГО МОНИТОРИНГА ДЛЯ ВЫЯВЛЕНИЯ СТРУК...»

«МИНОБРНАУКИ РОССИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "НОВОСИБИРСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ" (НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ, НГУ) Кафедра общей информатики Г. К. Кантеров ИСПОЛЬЗОВАНИЕ АНАЛИЗА ФОРМАЛЬНЫХ ПОН...»

«2014 9416М.1.00.000 ПС 2 Настоящий паспорт (далее – ПС) предназначен для отражения сведений, удостоверяющих гарантированные изготовителем значения основных параметров и характеристик счётчиков жидкости "DYMETIC-9416М.1", гарантий и сведений по их эксплуатации за весь период.В ПС приняты следующи...»








 
2017 www.ne.knigi-x.ru - «Бесплатная электронная библиотека - электронные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.