WWW.DISSERS.RU

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

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


Pages:     || 2 | 3 | 4 | 5 |   ...   | 82 |
РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР ИМ. А. А. ДОРОДНИЦЫНА РАН САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ЛЭТИ при поддержке РОССИЙСКОГО ФОНДА ФУНДАМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ КОМПАНИИ FORECSYS Математические методы распознавания образов ММРО-13 Ленинградская область, г. Зеленогорск, 30 сентября 6 октября 2007 Доклады 13-й Всероссийской конференции, посвящённой 15-летию РФФИ Москва, 2007 УДК 004.85+004.89+004.93+519.2+519.25+519.7 ББК Ш Математические методы распознавания образов.

Ш 13-я Всероссийская конференция: Сборник докладов.

М.: МАКС Пресс, 2007. с.

ISBN В сборнике представлены доклады 13-й Всероссийской конференции Математические методы распознавания образов, посвящённой 15-летию РФФИ, проводимой Вычислительным центром им. А. А. Дородницына Российской академии наук при финансовой и организационной поддержке РФФИ (грант № 07-07-06050) и компании Forecsys.

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

УДК 004.85+004.89+004.93+519.2+519.25+519.7 ББК ISBN © Авторы докладов, 2007 © Вычислительный центр РАН, 2007 © Художественное оформление: С. Орлов, 2007 Оргкомитет Председатель: Журавлев Юрий Иванович, академик РАН Зам. председателя: Матросов Виктор Леонидович, чл.-корр. РАН Ученый секретарь: Воронцов Константин Вячеславович, к.ф.-м.н.

Члены: Граничин Олег Николаевич, д.ф.-м.н.

Донской Владимир Иосифович, д.ф.м.н.

Дедус Флоренц Федорович, д.т.н.

Немирко Анатолий Павлович, д.ф.м.н.

Устинин Михаил Николаевич, д.ф.-м.н.

Вальков Антон Сергеевич, к.ф.-м.н.

Инякин Андрей Сергеевич, к.ф.-м.н.

Песков Николай Владимирович, к.ф.-м.н.

Программный комитет Председатель: Рудаков Константин Владимирович, чл.-корр. РАН Зам. председателя: Дюкова Елена Всеволодовна, д.ф.-м.н.

Ученый секретарь: Чехович Юрий Викторович, к.ф.-м.н.

Члены: Микаэлян Андрей Леонович, академик РАН Жижченко Алексей Борисович, чл.-корр. РАН Сойфер Виктор Александрович, чл.-корр. РАН Местецкий Леонид Моисеевич, д.т.н.

Моттль Вадим Вячеславович, д.ф.м.н.

Пытьев Юрий Петрович, д.ф.м.н.

Рязанов Владимир Васильевич, д.ф.м.н.

Рейер Иван Александрович, к.т.н.

Технический комитет Председатель: Громов Андрей Николаевич Члены: Гуз Иван Сергеевич Ефимов Александр Николаевич Ивахненко Андрей Александрович Каневский Даниил Юрьевич Лисица Андрей Валерьевич Назарова Мария Николаевна Никитов Глеб Владимирович Пустовойтов Никита Юрьевич Краткое оглавление Фундаментальные основы распознавания и прогнозирования... Методы и модели распознавания и прогнозирования........ Проблемы эффективности вычислений и оптимизации....... Обработка сигналов и анализ изображений.............. Прикладные задачи интеллектуального анализа данных...... Прикладные системы распознавания и прогнозирования...... Содержание................................ Алфавитный указатель авторов..................... Фундаментальные основы распознавания и прогнозирования Код раздела: TF (Theory and Fundamentals) • Статистические основы обучения по прецедентам.

• Дискретно-логические основы обучения по прецедентам.

• Алгебраический подход к проблеме распознавания.

• Проблема обобщающей способности.

• Теория возможности и неопределённые нечёткие модели.

• Устойчивость обучения.

• Байесовский вывод.

• Теория многокритериального выбора в задачах принятия решений.

• Теоретические проблемы распознавания и прогнозирования.

6 (TF) Фундаментальные основы распознавания и прогнозирования О неморсовости гауссовой смеси (TF) О неморсовости гауссовой смеси Апраушева Н. Н., Сорокин С. В.

plat@ccas.ru, www2007@ccas.ru Москва, Вычислительный центр РАН Широкое использование гауссовых смесей при решении задач классификации вызывает необходимость определения числа их мод, на чём основан модальный анализ [1, 2]. При этом в некоторых публикациях, например [2], среди свойств гауссовой смеси отмечается их морсовость.

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

Исследовалась смесь нормальных распределений с плотностью вероятности k 1 f (x) = ifi(x), fi(x) = exp - (x - µi)2, i=где x R, k = 2, 2 дисперсия компонент смеси, µi математическое ожидание i-й компоненты, i её априорная вероятность, i (0, 1), k i = 1.

i=Гладкая функция является функцией Морса, если все её критические точки (КТ) невырождены [3].

Вырожденные критические точки функции f(x) являются решения ми системы уравнений fx(x) = 0, fxx(x) = 0. Если функция f(x) имеет вырожденную критическую точку, то при небольшом изменении параметров распределения наблюдается неустойчивость, т. е. меняется число её критических точек [3]. Поиск ВКТ функции f(x) проводился на основе результатов [4]. Для определённости положим µ1 < µ2.

Теорема 1. При k = 2 и 2 функция f(x) унимодальна, где расстояние Махаланобиса, = (µ2 - µ1)-1.

Теорема 2. При k = 2 и > 2, 1 = 2 функция f(x) бимодальна и точка xc = (µ1 + µ2) является точкой её минимума.

Из теорем 1 и 2 имеем: для k = 2 и = 2, 1 = 2 точка xc = = (µ1 +µ2) является вырожденной модой функции f(x), что проверяется подстановкой значений параметров 1 = 2, µ2 = µ1 +2, xc = µ1 + в выражения fx(x) и fxx(x). Вырожденная критическая точка минимума смеси xc была найдена для k = 3, µ1 = -2.446, µ2 = 0, µ3 = 2.446, 1 = 0.4, 2 = 0.2, xc = 0.



8 (TF) Апраушева Н. Н., Сорокин С. В.

Теорема 3. При k = 2 и > 2, 1 = 2 функция f(x) унимодальна, если - ln(12 ) 1 + 2 ln 1 + 2 4.

- (1) 2 Эксперименты показали, что при выполнении неравенства, противоположного неравенству (1), при фиксированном значении и различных значениях 1, 2 для числа критических точек m функции f(x) имеют место неравенства 1 m 3. Если m = 2, то одна из КТ функции f(x), точка перегиба, является вырожденной.

Для k = 2 при различных значениях параметров, 1, 2 экспериментальным путём было найдено 15 критических точек перегиба, для каждой из которых вычислялись значения параметров и 1() = = | ln(12)-1|; при тех же значениях вычислялись значения функции 2(), представляющей собой правую часть неравенства (1), и функции = 2 - 1. На Рис. 1 представлены графики функций 1, 2,. Для получения 15 критических точек перегиба фиксировалось значение µи варьировались значения µ2, 1, 2.

Аппроксимировав функцию параболой, = a2 + b + c и вычислив неизвестные коэффициенты a, b, c методом наименьших квадратов, получили уравнение регрессии = -0.3272 + 3.867 - 3.738, (2) средняя абсолютная погрешность = 0.101, средняя относительная погрешность = 0.024, средне-квадратическое отклонение 1 = 0.124.

На основе введенных обозначений 1, 2, и формул (1), (2) для функции 1, 1 = 2 -, имеем выражение - ln 12 = 0.8272 + 2 ln[2-1( + 2 4)] - 3.867 + 3.738, (3) уравнение (3) является аппроксимационным уравнением границы унимодальности и бимодальности функции f(x).

Оценим доверительный коридор для функции (), используя неравенство Чебышева P | - | t1 1 - t-2, при t = 3, 1 = 0.124 имеем P - 0.372 < < + 0.372 > 0.888. (4) Поскольку 1 = 2 -, то для искомой функции 1 на основании (3), (4) имеем P d + 3.366 < 1 < d + 4.110 > 0.888. (5) О неморсовости гауссовой смеси (TF) Рис. 1. Графики функций 1(), 2() и ().

Выражение (5) с вероятностью более 0.888 даёт доверительный коридор для всех ВКТ перегиба функции f(x), в этом коридоре функция f(x) может быть как унимодальной, так и бимодальной.

Таким образом, при > 2 и 1 = 2 с вероятностью более 0. функция f(x) унимодальна, если выполняется неравенство - ln(12 ) > d + 4.110, и бимодальна, если выполняется неравенство - ln(12 ) < d + 3.366.

Итак, для исследуемой гауссовой смеси получены достаточные условия её унимодальности и бимодальности.

Литература [1] Дюран Б., Оделл П. Кластерный анализ. М.: Статистика, 1975.

[2] Carreira-Perpin M.A., Williams C. On the Number of Modes of a Gaussian Mixture. Inform. Res. Report EDI-INF-RR-0159. School of Inf. Univ. of Edinburg, 2003.

[3] Арнольд В. И., Варченко А. Н., Гусейн-Заде С. М. Особенности дифференцируемых отображений. М.: Наука, 1982. 304 с.

[4] Апраушева Н. Н., Сорокин С. В. Об унимодальности простейшей гауссовой смеси // ЖВМиМФ, 2004. Т. 44, № 5. С. 838–846.

10 (TF) Брусенцов Н. П., Владимирова Ю. С.

Конструктная компьютеризация силлогистики Брусенцов Н. П., Владимирова Ю. С.

ramil@cs.msu.su, julia_vladi@mtu-net.ru Москва, МГУ им. М. В. Ломоносова, факультет ВМиК Аристотелева силлогистика непарадоксальна и не вписывается в исчисления классической логики, потому что в основе ее лежит принцип сосуществования противоположностей [1, с. 87–92], предотвращающий возникновение химер, в частности, именуемых парадоксами и провозглашаемых законами, но не соответствующих реальности, подобно положенному в основу формальной логики хризиппову закону исключенного третьего, отвергающего сосуществование противоположностей и заблокировавшего развитие диалектической логики Аристотеля.

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

Так, конъюнкции xyz, xyz, xy различаются тем, что термин z первой присущ, второй антиприсущ, а в третьей присущность его несущественна: xy(z z) xy, в ней z умалчивается. К сожалению, для членов ДНФ и КНФ подобное не предусмотрено: умалчивание означает исключенность члена, а несущественность неотобразима, третье невозможно.

Естественней (и единообразней) сохранить принятое в элементарных выражениях умалчивать несущественное и ввести функтор исключения, допустим, минус. Теперь непарадоксальную импликацию (полноценное следование) x y можно выразить трехчленом xy-xyxy, тогда как материальная импликация x y будет: xy -xy xy xy. Это экстенциональный (объемный) вариант подчинения логики высказываний принципу сосуществования противоположностей.

Суждения силлогистики истолковываются интенсинально в них речь не о высказываниях и предикатах, а о существовании или несуществовании вещей, охарактеризованных совокупностями их существенных особенностей. Выражающая отношение следования x y общеутвердительная посылка Axy ( Все x суть y ) представима конъюнкцией трех дизъюнктов:

Axy Vxy Vxy Vxy, где Vxy существование xy-вещей, Vxy несуществование xy-вещей, Vxy существование xy-вещей. Умалчивание существования или Конструктная компьютеризация силлогистики (TF) несуществования xy-вещей означает несуществовенность его для представленного отношения.





В минимальной форме Axy Vx Vxy Vy, а в универсуме Аристотеля УА [1, с. 91], необходимо подчиненном принципу сосуществования противоположностей Vx Vx Vy Vy, т. е. предполагающем, что x-, x-, y-, yвещи необходимо существуют, Vxy истолковывается как Vx Vxy Vy несовместимость x с y, что равносильно x y. Таким образом, дизъюнкт Vxy, означающий в модальной логике парадоксальную строгую импликацию Льюиса [3], в универсуме Аристотеля обретает смысл полноценного содержательного следования.

Общеотрицательная посылка Exy Все x суть y получается из Axy инверсией y: Exy Axy Vxy Vx Vy. Частноутвердительная посылка Ixy Некоторые x суть y, Существуют xy, несовместимая с общеотрицательной, в УА равнозначна ее инверсии: Ixy inv( Vxy) Vxy, что, с учетом Vx Vx Vy Vy, означает Ixy Vxy Vx Vy. Соответственно, частноотрицательная посылка Oxy как инверсия общеутвердительной Axy будет Oxy Vxy Vx Vy Ixy. Таким образом, при использовании инверсии терминов в силлогистике достаточно двух функторов A и I. При этом восполнимы упущенные традиционной теорией отношения: Axy, Axy, Ixy, Ixy.

Наша цель компьютеризация восполненной и упорядоченной посредством принципа сосуществования противоположностей аристотелевой силлогистики путём конструктного кодирования [4] её суждений и программной реализации умозаключений (модусов). Предполагается принятое в УА истолкование выражений.

Вывод из пары общих посылок общего заключения реализуется склеиванием их (элиминацией среднего термина). Например, модус Barbara:

Axy Ayz Vxy Vyz V(xy yz) V(xyz xyz xyz xyz) V(xy xz yz) Vxy Vxz Vyz Vxz Axz.

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

Например, из Axy Ayz общего заключения нет. Посылке Axy подчинены Ixy Vxy и Ixy Vxy.

Ixy Ayz Vxy Vyz Vxy Vxyz Vxyz нет заключения.

Ixy Ayz Vxy Vyz Vxy Vxyz Vxyz Vxy Vxyz Vxyz Vxz Ixz.

12 (TF) Брусенцов Н. П., Владимирова Ю. С.

+ + + 0 0 - + - + - - Рис. 1. Таблица операции.

Таким образом, из пары с общим (средним) термином, включающей общую и частную посылки, заключение возможно, но не необходимо.

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

Компьютеризация категорической силлогистики просто и экономно реализуется при помощи четырехтритных конструктов [4], кодирующих трехтерминные дизъюнкты существования и несуществования. Значение первого (головного) трита указывает тип дизъюнкта: + существование, представляющее частную посылку, - несуществование, общая посылка. Последующие триты сопоставлены терминам x, y, z, указывая их статусы. Например, Vxyz (+ + -+), Vxy (+ + +0), Vxz (+-0+), Vxy (-+-0), Vxyz (-+-+), Vxz (-+0-).

Общее заключение из пары общих посылок, если оно существует, достигается склеиванием (потритным логическим сложением, Рис. 1) соответствующих конструктов. Например, Axy Ayz Vxy Vyz (- + +0) (-0 - +) (- + 0+) Vxz Axz.

Частное заключение получается склеиванием конструкта, кодирующего частную посылку с инверсией представляющего общую. Например, Ixy Ayz (+ - -0) inv(-0 - +) (+ - -0) (+0 + -) (+ - 0-) Ixz.

Если склеивания (элиминации среднего термина) нет, то и заключения не существует.

Интеллект реализованной в диалоговой системе структурированного программирования ДССП программы силлогистического вывода значительно превзошел то, что достигнуто невооруженными умами людей.

Число правильных модусов, составляющее в традиционной логике 19, а в математической логике сокращенное до 15, оказалось равным 128.

Об ускорении процессов обучения и принятия решений (TF) Литература [1] Брусенцов Н. П. Искусство достоверного рассуждения. М.: Фонд Новое тысячелетие. 1998.

[2] Брусенцов Н. П. Трехзначная интерпретация силлогистики Аристотеля // Историко-математические исследования. Вторая серия. Вып. 8 (43).

М.: Янус-К, 2003. С. 317–327.

[3] Слинин Н. И. Современная модальная логика. Л.: Изд-во Ленинградского ун-та, 1976. С. 8.

[4] Брусенцов Н. П., Владимирова Ю. С. Троичная компьютеризация логики // ММРО-12. М.: МАКС-Пресс, 2005. С. 40–42.

Об ускорении процессов обучения и принятия решений Вайнцвайг М. Н.

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

Трудности моделирования работы этого механизма связаны со следующими обстоятельствами.

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

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

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

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










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

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