WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 | 5 |   ...   | 82 |

Пусть задано множество R и функция T : X X R, где X множество всех конечных выборок из X.

Рассмотрим эксперимент, в котором с равной вероятностью реализуется одно из разбиений n, после чего наблюдателю сообщается вы k борка Xn. Не зная скрытой выборки Xn, наблюдатель должен постро ить функцию T : X R, значение которой на наблюдаемой выборке k Tn = T (Xn) предсказывало бы значение Tn = T (Xn, Xn), существенно заk висящее от скрытой выборки Xn. Требуется также оценить надёжность предсказания, т. е. указать оценочную функцию () такую, что Pn d(Tn, Tn) > (), (1) где d: R R R заданная функция, характеризующая величину отклонения d(r, r) предсказанного значения r R от неизвестного истин ного значения r R. Параметр называется точностью, а величина (1 - ()) надёжностью предсказания. Если в (1) достигается равенство, то () называется точной оценкой. Оценка () может зависеть от и k, а также от вида функций T и T. Если (1) выполняется при достаточно малых и, то говорят, что в окрестности предсказываемого значения имеет место концентрация вероятности [5].

Заметим, что данная постановка задачи не опирается на классическую аксиоматику теории вероятностей. Здесь понятие вероятности яв N ляется лишь синонимом доли разбиений: Pn{(n)} = (n) для N n=произвольного предиката : {1,..., N} {0, 1}, заданного на множестве разбиений выборки XL. Тем не менее, мы предпочитаем пользоваться привычным термином вероятность и говорить, что задача эмпирического предсказания поставлена в слабой вероятностной аксиоматике.

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

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

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

Слабая аксиоматика обходится без этих гипотез. Фактически, в ней остаётся только гипотеза равновероятности разбиений, эквивалентная предположению о независимости выборки XL. Об объектах вне выборки XL вообще не делается никаких предположений.

k 3. Из оценки слабого функционала Pn{(Xn, Xn)} всегда можно получить оценку сильного функционала, взяв матожидание по выборке XL от обеих частей неравенства:

k EXL Pn{(Xn, Xn)} = PXL{(X, Xk)} EXL.

Если не зависит от выборки, то оценка переносится непосредственно.

Для оценок типа Вапника-Червоненкиса это было проделано в [3].

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

5. В современной вычислительной теории обучения [5] для получения верхних оценок надёжности используется математический аппарат функционального анализа и оценки концентрации вероятностной меры.

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

ний. Однако во многих случаях находятся эффективные алгоритмические решения вычислительных проблем.

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

А. Н. Колмогоров [4]:... представляется важной задача освобождения всюду, где это возможно, от излишних вероятностных допущений.

На независимой ценности чисто комбинаторного подхода к теории информации я неоднократно настаивал в своих лекциях.

Ю. К. Беляев [2]:... возникло глубокое убеждение, что в теории выборочных методов можно получить содержательные аналоги большинства основных утверждений теории вероятностей и математической статистики, которые к настоящему времени найдены в предположении взаимной независимости результатов измерений.



Работа выполнена при поддержке РФФИ, проект № 05-01-00877, и программы ОМН РАН Алгебраические и комбинаторные методы математической кибернетики.

Литература [1] Алимов Ю. И. Альтернатива методу математической статистики. Знание, 1980.

[2] Беляев Ю. К. Вероятностные методы выборочного контроля. М.: Наука, 1975.

[3] Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики / Под ред. О. Б. Лупанова. М.: Физматлит, 2004. Т. 13. С. 5–36.

[4] Колмогоров А. Н. Теория информации и теория алгоритмов / Под ред.

Ю. В. Прохорова. М.: Наука, 1987.

[5] Lugosi G. On concentration-of-measure inequalities. // Machine Learning Summer School, Australian National University, Canberra. 2003.

[6] Vapnik V. Statistical Learning Theory. Wiley, New York, 1998.

О теоретико-возможностном методе медицинской диагностики (TF) О теоретико-возможностном методе медицинской диагностики Газарян В. А., Нагорный Ю. М., Пытьев Ю. П.

pytyev@phys.msu.ru Москва, МГУ Теоретико-возможностный метод используется для решения задач медицинской диагностики с помощью возможностного аналога алгоритма Кора.

Функциональные нарушения в системе пищеварения активно изучаются на протяжении ряда последних лет. Проводимые совместно с врачами клиники НИИ питания РАМН исследования позволили значительно продвинуться на пути создания нового комплексного метода компьютерной оценки состояния больных с функциональными нарушениями.

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

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

Оптимальное решение задачи классификации достигается при минимизации возможности (необходимости) потерь [3]. Согласно теореме о P -оптимизации, субъект следует отнести к классу q:

P (q, x) = min P (q, x), (1) q P (q, x) = sup min(|(x|k), l(k, q)), (2) k где P (q, x) возможность ошибки при отнесении субъекта = x к классу = q, = 1,..., n, x = x1,..., xn, xj значение j-го признака (симптома), |(x|k) условное распределение возможностей пациенту класса k обладать признаками (симптомами) x.

Условное распределение |(x|k) получим в результате стохастического моделирования условных возможностей определенных наборов 26 (TF) Газарян В. А., Нагорный Ю. М., Пытьев Ю. П.

признаков при условии принадлежности субъекта выделенным классам путем применения оптимизированного алгоритма гранулирования [4].

Обучение возможностного аналога алгоритма классификации Кора проводится на основании ранжированных по возможностям групп признаков.

В каждом классе k определяется набор ws, имеющий максимальную k переходную возможность:

p(k|ws ) = max p(k|ws), s = 1,..., Sk.

k s Далее в (2) значение p(x|k) используется в качестве |(x|k).

Субъект x относится к тому классу q, которому соответствует минимальная возможность ошибки (1) (в котором есть набор ws, имеющий q минимальную возможность ошибки):

P (q, ws ) = min P (q, ws ).

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

Литература [1] Газарян В. А., Иваницкая Н. В., Пытьев Ю. П., Шаховская А. К. // Вестн.

Моск. ун-та. Физ. Астрон. 2003. № 2. С. 12.

[2] Газарян В. А., Илюшин В. Л., Пытьев Ю. П., Шаховская А. К. // Вестн.

Моск. ун-та. Физ. Астрон. 2005. № 4. С. 3.

[3] Пытьев Ю. П. Возможность. Элементы теории и применения. М.: УРСС, 2000.

[4] Пытьев Ю. П. Возможность как альтернатива вероятности. Математические и эмпирические основы, применения. М.: Физматлит, 2007.

Решение задач распознавания с невыполненной гипотезой компактности (TF) Решение задач распознавания с невыполненной гипотезой компактности Гуров С. И., Потепалов Д. Н., Фатхутдинов И. Н.

sgur@cs.msu.ru, mmp@cs.msu.ru Москва, МГУ им. М. В. Ломоносова, факультет ВМиК Реализованные на сегодняшний день алгоритмы логического синтеза имеют разную эффективность на различных типах схем. Поэтому возникает задача определения наилучшего алгоритма синтеза исходя из тех или иных характеристик входного описания схемы.

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





Поставленная задача решалась методами распознавания образов.

Суть предложенного решения заключается в построении признакового пространства образов (описаний схем) с последующим решением в нём задачи классификации. Первый, почти не разработанный в теоретическом плане и трудоёмкий на практике этап состоит в: (1) фиксации набора первичных числовых признаков прецедентов; (2) построении достаточно представительной совокупности вторичных признаков как функций от первичных; (3) отборе наиболее информативных вторичных признаков. На втором этапе строится решающее правило, относящее описание схемы в построенном признаковом пространстве к тому или иному классу.

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

Разработанные алгоритмы указанных задач оказались эффективными.

Анализ показывал, что схемы из одного и того же класса образовывали некомпактные области в пространствах их исходного описания, т.е.

для них не выполнялась т.н. гипотеза компактности (ГК). Это характеризует задачи как чрезвычайно сложные в практическом и теоретическом аспектах, для которых обычные методы распознавания оказываются непригодными.

28 (TF) Гуров С. И., Потепалов Д. Н., Фатхутдинов И. Н.

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

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

Задачи, где ГК не имеет места, указанные хорошие свойства алгоритмов распознавания при использовании обычных подходов отнюдь не гарантируются. В силу этого на протяжении последних лет они находились вне круга интересов разработчиков: теория, способная дать направления решения таких задач отсутствовала. Здесь надо сказать, что попытки решения задач с невыполненной ГК делались ещё на заре развития теории и практики распознавания образов. В известной монографии М. М. Бонгарда [3] приведён демонстрационный пример решения задачи указанного типа. Однако этот подход на многие годы оставался невостребованным...

Для решения задач данного типа необходимо было понять, что же понимается под неформальным понятием компактные образы, откуда берётся и как формируется пространство свойств, и т. д. В связи с этим в последнее время были предприняты некоторые попытки формализации ГК [6, 5]. Однако они либо носили частный характер, либо уводили проблему в общефилософскую плоскость [2]. Так что на сегодняшний день этот вопрос является открытым.

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

Данная формулировка, по сути, лишь несколько уточняет первоначальную, высказанную М. А. Айзерманом в первых работах по распознаванию образов конца 50-х годов XX в.

Решение задач распознавания с невыполненной гипотезой компактности (TF) Решения задач. Результаты Для решения задач использовался вышеупомянутый подход М. М. Бонгарда. На основе первичных признаков (до 10–12) объектов генерировались вторичные признаки (до десятков тысяч) как функции от первичных, из которых отбирались наиболее информативные. Окончательно задачи классификации (определения областей компетентности имеющихся алгоритмов) решались в сформированном признаковом пространстве.

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

В задаче № 1 исследовались 19 практических алгоритмов синтеза схем и 120 описаний реальных схем (первые результаты см. в [4]). В задаче № исследовались 185 схем (разбиение по классам: 175 + 10).

Программные модули, реализующие разработанные алгоритмы, интегрированы в открытую среду SIS [7], информационно совместимую со многими промышленными системами синтеза БИС, в частности используемой в фирме Intel Inc.

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

Работа выполнена при поддержке РФФИ, проект № 07-01-00211.

Литература [1] Aйзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970. 384 с.

[2] Белозерский Л. А. Современный взгляд на гипотезу компактности // Штучний iнтелект (Донецк). 2005. № 3. С. 6–12.

[3] Бонгард М. М. Проблема узнавания. М.: Наука, 1967.

Pages:     | 1 | 2 || 4 | 5 |   ...   | 82 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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