WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 82 |

[4] Гранкин М. В., Гуров С. И., Фатхутдинов И. Н. Определение областей компетентности алгоритмов при невыполненной гипотезе компактности // Штучний iнтелект (Донецк). 2006. № 2. С. 88–98.

[5] Донской В. И. О метрических свойствах кратчайших эмпирических закономерностей // Уч. записки ун-та им. В. И. Вернадского. 2003. № 2.

С. 143–147.

[6] Загоруйко Н. Г., Елкина В. Н., Киприянова Т. П. Пакет Прикладных Программ ОТЭКС для Обработки Таблиц Экпериментальных данных. Версия 4.0 www.math.nsc.ru/AP/oteks/Russian/.

[7] SIS: A System for Sequential Circuit Synthesis // Dep. of Electrical Engineering and Computer Science Univ. of California, Berkeley. 1992.

30 (TF) Зубюк А. В.

Алгоритмы идентификации изображений в случайной и нечёткой морфологии Зубюк А. В.

zubuk@cmpd2.phys.msu.su Москва, МГУ им. М. В. Ломоносова, физический факультет В работе [1] рассмотрены основные понятия случайной и нечёткой морфологии и даны постановки ряда задач идентификации изображений, имеющих случайную или нечёткую форму. В настоящем докладе рассмотрены алгоритмы решения этих задач.

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

В то же время, все изображения одной и той же сцены имеют сходные черты, позволяющие отличать изображения этой сцены от изображений других сцен. Такой сходной чертой в ряде случаев может являться геометрическая форма изображённых объектов. Таким образом, существует инвариант, не изменяющийся при изменении условий наблюдения. Методы морфологического анализа изображений ориентированы, прежде всего, на анализ формы изображённых объектов в терминах, инвариантных относительно условий получения изображений [2, 3].

Пусть моделью изображения является элемент евклидова пространства RN. Тогда всевозможные изменения условий его регистраций приведут к тому, что изображение одного и того же объекта будет изменяться в пределах некоторого множества V пространства RN. Это множество называется формой изображения этого объекта [2], т. к. оно отражает его характеристики, не зависящие от условий регистрации изображений.

Случайная и нечёткая формы изображений Напомним кратко основные определения, которые были даны в [1].

Определение 1. Случайной формой элементов пространства RN назовём вероятностное пространство (, A, Pr), где множество непересекающихся подмножеств евклидова пространства RN (форм), образующих разбиение пространства RN, A некоторая -алгебра подмножеств множества, а Pr заданная на ней вероятность.

Алгоритмы идентификации изображений (TF) Каждому событию A A соответствует форма (подмножество) V = = RN, вероятность которой есть Pr(A). По аналогии с опредеA лением 1 введём понятие нечёткой формы:

Определение 2. Нечёткой формой элементов пространства RN назовём пространство с возможностью (, A, P), где множество непересекающихся форм, образующих разбиение RN, A некоторая -алгебра подмножеств, а P заданная на ней возможность.

Задачи идентификации изображений, имеющих случайную или нечеткую форму В докладе рассмотрены алгоритмы решения задач идентификации изображений, поставленных в [1]. Помимо этого, рассмотрены задачи, в которых известна некоторая априорная информация о предъявляемых изображениях. Такая информация заключается в следующем. Предъявляемое изображение является случайным (или нечётким) и для каждой формы известно его условное распределение внутри этой формы.

Учёт этой информации делает гипотезы в минимаксной задаче проверки гипотез простыми. Приведём постановку такой задачи в случайной морфологии.

Пусть заданы две случайные формы: F1 = (, A, Pr1) и F2 = = (, A, Pr2), где вероятности Pr1 и Pr2 заданы плотностями pr(1)(·) и pr(2)(·) соответственно, и предъявляемое для идентификации изображение формируется по схеме = f +, где f и случайные элементы пространства RN (случайные элементы f, и независимы). Требуется по предъявленному изображению определить, какую случайную форму (F1 или F2) имеет элемент f. Для этого можно воспользоваться рандомизированным критерием, являющимся решением следующей минимаксной задачи:

max (1, 2) min ;

1,(1) 1(x) + 2(x) = 1, x RN ;

(x) 0, x RN, i = 1, 2;

i где i def 1- prt (x) i(x) dx, i = 1, 2, prt (x) распределение случай= RN ного элемента, зависящее от распределений элементов, f и.

Алгоритмы решения поставленных задач и их свойства В докладе рассмотрено применение алгоритмов типа случайного поиска (см [5, 6]) для решения минимаксных задач. В частности, для решения минимаксной задачи в теоретико-вероятностной постановке она 32 (TF) Зубюк А. В.

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



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

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

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

Литература [1] Пытьев Ю. П., Зубюк А. В. Случайная и нечёткая морфология (эмпирическое восстановление модели, идентификация) // Материалы IX Межд.

конф. Интеллектуальные системы и компьютерные науки. 2006.

[2] Пытьев Ю. П. Морфологический анализ изображений // Докл. АН СССР. 1983. Т. 269, № 5. C. 1061–1064.

[3] Pyt’ev Yu. P. Morphological Image Analysis // Pattern Recognition and Image Analysis. 1993. Vol. 3, № 1. P. 19–28.

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

[5] Гладков Д. И. Оптимизация систем неградиентным случайным поиском.

М: Энергоатомиздат, 1984.

[6] Жиглявский А. А. Математическая теория глобального случайного поиска Л: Изд-во Ленингр. ун-та, 1985.

Верхние оценки переобученности логических закономерностей (TF) Верхние оценки переобученности и профили разнообразия логических закономерностей Ивахненко А. А., Воронцов К. В.

andrej_iv@mail.ru, voron@ccas.ru Москва, Вычислительный Центр РАН Логические алгоритмы классификации представляют собой композиции элементарных классификаторов, называемых также закономерностями. Существуют два противоположных подхода к повышению качества (обобщающей способности) таких алгоритмов: либо увеличение числа закономерностей в композиции [1], либо повышение качества закономерностей. Качество алгоритма в обоих случаях может оказаться сопоставимым, однако при втором подходе получаются более простые, легко интерпретируемые алгоритмы. В данной работе понятие обобщающей способности, которое обычно определяется для алгоритмов, распространяется на случай закономерностей. В рамках комбинаторного подхода [2] выводятся сложностные оценки качества закономерностей. Предлагается методика эмпирического измерения завышенности получаемых оценок, основанная на скользящем контроле.

Основные определения Рассмотрим стандартную постановку задачи классификации. Задано множество допустимых объектов X, конечное множество имён классов Y и обучающая выборка X = (xi, yi) X Y. Предполагается, что i=yi = y(xi), где y : X Y неизвестная целевая зависимость. Требуется построить алгоритм a: X Y, приближающий y на всём X.

Закономерностью называется предикат y : X {0, 1}, выделяющий достаточно много объектов класса y и достаточно мало объектов всех остальных классов. Предикат y выделяет объект x, если y(x) = 1.

Логические алгоритмы представляются в виде линейных композиций T t y t вида a(x) = arg max wyt (x), где t закономерности, wy веса t=1 y y yY закономерностей, Ty число закономерностей класса y.

Методом обучения называется отображение µ, которое по выборке X t=1,T y строит набор закономерностей µX µ(X) = t (x).

y yY Частота ошибок закономерности y на выборке U X есть (y, U) = y(x) = [y(x) = y].

|U| xU Переобученностью закономерности y µX при заданной контрольной выборке Xk называется разность частот её ошибок на контроле и на обучении (y, X, Xk) = (y, Xk) - (y, X).

34 (TF) Ивахненко А. А., Воронцов К. В.

k Рассмотрим множество всех разбиений полной выборки XL = XnXn на две подвыборки обучающую длины и контрольную длины k, где +k = L, индекс n пробегает множество всех разбиений N = {1,..., CL}.

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

1 k Q(µ, XL) = (, Xn, Xn) >.

|N| |µXn| nN µXn где [0, 1) порог переобученности. Аналогичный функционал, его верхние оценки и связь с теорией Вапника-Червоненкиса рассматривались в [2] для алгоритмов классификации и регрессии.

Коэффициенты и профили разнообразия Назовем предикаты, : X {0, 1} неразличимыми или эквивалентными на выборке XL, если (x) = (x) для всех x XL. Коэффициентом разнообразия (shatter coefficient) (, XL) множества предикатов на выборке XL называется максимальное число попарно неразличимых предикатов из, оно же число классов эквивалентности на.

Коэффициент разнообразия характеризует сложность множества предикатов относительно заданной выборки XL.

Рассмотрим множество закономерностей, получаемых методом µ по N всевозможным обучающим подвыборкам: (µ, XL) = µXn.

L L n=Его коэффициент разнообразия (µ, XL) = (, XL) назовём L L L локальным коэффициентом разнообразия метода µ на выборке XL.

Разобьём множество на L + 1 подмножеств, состоящих из законоL мерностей с фиксированным числом ошибок m на полной выборке XL:

m m m(µ, XL) = : (, XL) =, m = 0,..., L.

L L Локальным профилем разнообразия метода µ на выборке XL назовём последовательность коэффициентов разнообразия Dm Dm(µ, XL) = = (m, XL), m = 0,..., L. Очевидно, что = D0 + · · · + DL.





L Наряду с функционалом Q определим функционал Q,m как долю переобученных закономерностей, допускающих m ошибок на XL:

1 k m Q,m(µ, XL) = (, Xn, Xn) > (, XL) =.

L |N| |µXn| nN µXn Теорема 1. Для любых µ, XL и порога переобученности [0, 1) m sQ,m(µ, XL) DmH, m = 0,..., L, (1) L m s s s -s где H = CmCL-m/CL гипергеометрического распреL s=s хвост деления, s0 = max{0, m - k} и s1 = (m - k).

L Верхние оценки переобученности логических закономерностей (TF) Задача L Глобальный Локальный Эффективный crx 690 2.8 · 108 3.5 · 104 21 ± german 1000 5.2 · 108 3.1 · 104 47 ± hepatitis 155 5.5 · 106 1.8 · 104 58 ± horse-colic 300 1.9 · 106 1.3 · 104 5 ± hypothyroid 3163 5.3 · 108 2.2 · 104 43 ± liver 345 1.5 · 107 2.9 · 104 12 ± promoters 106 4.4 · 109 5.3 · 104 13 ± Таблица 1. Коэффициенты разнообразия на 7 задачах классификации из репозитория UCI. Выборка разбивалась 20 раз случайным образом на равные части = k со стратификацией классов; = 0.05.

Теорема 2. Для любых µ, XL и порога переобученности [0, 1) L m sQ(µ, XL) DmH.

L m= Определим эффективный локальный профиль разнообразия Dm как гипотетическое значение локального профиля Dm, при котором оценка (1) не является завышенной, т. е. неравенство обращается в равенство:

m s Dm = Q,m(µ, XL) H, m = 0,..., L.

L Эту величину легко измерить эмпирически, если в функционале Q,m заменить сумму по всем разбиениям N суммой по некоторому подмножеству N N (в методе Монте-Карло N случайное подмножество).

Наконец, эффективный локальный коэффициент разнообразия опре делим как = D0 + · · · + DL. Эта величина показывает, какое значение L должен был бы принимать локальный коэффициент разнообразия, чтобы верхняя оценка не была завышенной. Данная методика измерения завышенности существенно уточняет методику, ранее предложенную в [3].

Измерение профилей разнообразия: эксперименты и выводы Алгоритмы поиска закономерностей, основанные на непосредственном переборе предикатов, очень удобны для эмпирического исследования завышенности сложностных оценок, поскольку: (а) глобальный коэффициент разнообразия (функция роста по Вапнику) вычисляется по эффективной рекурсивной формуле [3]; (б) локальный коэффициент оценивается снизу числом различных закономерностей, найденных методом µ на подвыборках {Xn : n N}. Результаты сравнения этих величин с эффективным локальным коэффициентом приведены в Таблице 1.

Эффективный локальный коэффициент всегда оказывался существенно меньшим длины выборки L. Это означает, что при фиксиро36 (TF) Ивахненко А. А., Воронцов К. В.

hepatitis, класс 0 horse, класс Профиль разнообразия Профиль разнообразия 0.06 0.0.05 0.0.04 0.0.03 0.0.02 0.0.01 0.0 20 30 40 50 60 70 80 90 100 40 50 60 70 80 90 100 110 120 130 m m эффективный локальный профиль оценка p(m) эффективный локальный профиль оценка p(m) Рис. 1. Сравнение эффективного профиля Dm и нормированного локального профиля p(m) на двух задачах: hepatitis и horse.

ванных XL, y и µ ёмкость (VC-dimension) эффективно используемого множества закономерностей никогда не превышает единицы.

Эмпирические нижние оценки локальных коэффициентов завышены, как минимум, на три порядка. Ни один из известных на сегодня подходов, включая наиболее точные [4], не способен дать оценки коэффициентов разнообразия порядка 101–102.

Интересные результаты дало сравнение эффективного профиля Dm с нижней оценкой локального профиля Dm, подсчитанной как число различных закономерностей из {µXn : n N}, допускающих m ошибок на XL. Практически во всех задачах оказалось, что нормированный локальный профиль p(m) = Dm/(D0 + · · · + DL) является лишь слегка заниженной оценкой эффективного профиля Dm и, как правило, сильно с ним коррелирует (Рис. 1). Данному факту пока не найдено объяснения.

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

Литература [1] Cohen W. W., Singer Y. A simple, fast and effective rule learner // Proc. of the 16 National Conference on Artificial Intelligence. 1999. Pp. 335–342.

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

[3] Воронцов К. В., Ивахненко А. А. Эмпирические оценки локальной функции роста в задачах поиска логических закономерностей // Искусственный Интеллект. Донецк, 2006. С. 281–284.

[4] Langford J. Quantitatively tight sample complexity bounds. 2002. Carnegie Mellon Thesis.

Построение оптимальной вероятностной модели систем распознавания (TF) Способы построения оптимальной вероятностной модели систем распознавания Капустий Б. Е., Русын Б. П., Таянов В. А.

vtayanov@ipm.lviv.ua Украина, Львов, Физико-механический институт им. Г. В. Карпенка НАН Украины Актуальность задачи построения математической модели систем распознавания (СР) состоит в том, что она позволяет исследовать эту систему, не реализуя её в полном объёме. Определение параметров проводится на основании обучающей выборки. Оптимальность модели определяется её точностью и скоростью вычисления параметров [3]. Поэтому важным является применение дифференциального подхода, дающего возможность определить вероятность правильного распознавания отдельно тестируемого образа. Этот подход даёт возможность построить оптимальный вариант модели СР в условиях малых выборок [4]. Математическую модель СР можно представить в виде некоторого функционала M = R(fx, n, s, t), (1) где fx обобщённый классификатор (далее просто классификатор);

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 82 |










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

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