ЭФФЕКТИВНОСТЬ БАЙЕСОВСКИХ ПРОЦЕДУР РАСПОЗНАВАНИЯ часть 1
ЭФФЕКТИВНОСТЬ БАЙЕСОВСКИХ ПРОЦЕДУР РАСПОЗНАВАНИЯ
Авторы: Александра Вагис, Анатолий Гупал
Аннотация: В основе байесовского подхода лежит определение таких структур описания объектов, для которых возможно построение эффективных (оптимальных) процедур распознавания. В настоящее время эти вопросы решены для дискретных объектов с независимыми признаками и объектов, которые описываются цепями Маркова. Получены детерминированные оценки погрешности байесовской процедуры распознавания в зависимости от размеров классов (обучающих выборок), количества признаков и количества значений признаков.
Ключевые слова: Байесовская процедура; погрешность процедуры; цепь Маркова; обучающая выборка.
ACM Classification Keywords: H.4.2 Information Systems Applications: Types of Systems: Decision Support.
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.
Введение
Задача распознавания рассматривается c точки зрения минимизации функционала среднего риска [Вапник, 1979].Такая постановка является обобщением классических задач, решаемых на основе метода наименьших квадратов, в том смысле, что наблюдению объекта может соответствовать не одно, а несколько состояний объектов. Она на порядок сложнее любой NP-полной задачи [Гэри, Джонсон, 1982]. При решении задач распознавания определяющим моментом является структура описания объекта. Если она известна, то не представляет труда по обучающей выборке построить байесовские процедуры, как это проделано для независимых признаков и цепей Маркова [Гупал, 1995], [Гупал, Вагис, 2001]. В дискретном случае показано, что оценка снизу сложности класса задач распознавания совпадает с верхней оценкой погрешности с точностью до абсолютной константы, т.е. байесовская процедура распознавания является субоптимальной. Количество классов и число значений признаков линейным образом входят в оценку погрешности байесовской процедуры распознавания. Таким образом, проблема минимизации среднего риска решена для дискретных объектов с независимыми признаками: построены оптимальные оценки погрешности процедур распознавания в зависимости от входных параметров задачи. Исследование эффективности байесовской процедуры распознавания на цепях Маркова основано на исследовании свойств оценок переходных вероятностей. Для нестационарных цепей Маркова получены асимптотические оценки погрешности байесовской процедуры распознавания, которые аналогичны оценкам для независимых признаков.
( Читать дальше )
Авторы: Александра Вагис, Анатолий Гупал
Аннотация: В основе байесовского подхода лежит определение таких структур описания объектов, для которых возможно построение эффективных (оптимальных) процедур распознавания. В настоящее время эти вопросы решены для дискретных объектов с независимыми признаками и объектов, которые описываются цепями Маркова. Получены детерминированные оценки погрешности байесовской процедуры распознавания в зависимости от размеров классов (обучающих выборок), количества признаков и количества значений признаков.
Ключевые слова: Байесовская процедура; погрешность процедуры; цепь Маркова; обучающая выборка.
ACM Classification Keywords: H.4.2 Information Systems Applications: Types of Systems: Decision Support.
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.
Введение
Задача распознавания рассматривается c точки зрения минимизации функционала среднего риска [Вапник, 1979].Такая постановка является обобщением классических задач, решаемых на основе метода наименьших квадратов, в том смысле, что наблюдению объекта может соответствовать не одно, а несколько состояний объектов. Она на порядок сложнее любой NP-полной задачи [Гэри, Джонсон, 1982]. При решении задач распознавания определяющим моментом является структура описания объекта. Если она известна, то не представляет труда по обучающей выборке построить байесовские процедуры, как это проделано для независимых признаков и цепей Маркова [Гупал, 1995], [Гупал, Вагис, 2001]. В дискретном случае показано, что оценка снизу сложности класса задач распознавания совпадает с верхней оценкой погрешности с точностью до абсолютной константы, т.е. байесовская процедура распознавания является субоптимальной. Количество классов и число значений признаков линейным образом входят в оценку погрешности байесовской процедуры распознавания. Таким образом, проблема минимизации среднего риска решена для дискретных объектов с независимыми признаками: построены оптимальные оценки погрешности процедур распознавания в зависимости от входных параметров задачи. Исследование эффективности байесовской процедуры распознавания на цепях Маркова основано на исследовании свойств оценок переходных вероятностей. Для нестационарных цепей Маркова получены асимптотические оценки погрешности байесовской процедуры распознавания, которые аналогичны оценкам для независимых признаков.
( Читать дальше )
- +2
- 3 ноября 2009, 17:10
- комментировать
СЛОЖНОСТНО–СТРУКТУРНЫЙ ПОДХОД К ИССЛЕДОВАНИЮ ОБЛАСТИ ПРИМЕНИМОСТИ АЛГОРИТМА PROFIT часть 2
Обращение матрицы A осуществляется с помощью итеративного LSQR алгоритма [Слуис, Ворст, 1987], который достаточно быстро сходится при хорошо подобранных параметрах регуляризации Am (амплитуда демпфирования) и Sm (весовой параметр сглаживания скоростных вариаций в соседних
узлах параметризационной сетки). Итерационно решаем систему уравнений:? A?? dT?? ???? am I ?d??? 0? .(6) ????? sm C?? 0?
Где I – диагональная единичная матрица размера M, C — прямоугольная матрица, каждая линия которой состоит из двух единичных элементов противоположного знака, являющихся соседними узлами в параметризационной сетке.
Оптимальные значения этих параметров зависят от многих факторов. Например, при увеличении размера данных параметр демпфирования должен увеличиваться, в то время как при увеличении числа узлов вследствие измельчения разбиения параметр демпфирования должен быть уменьшен. В случае же большого уровня шума в данных параметр демпфирования должен быть достаточно весомым для сохранения устойчивости решения. Процедура нахождения коэффициентов демпфирования до сих пор не формализована. К тому же соотношение между числом параметров, лучей и значениями коэффициентов амплитуд и сглаживания является нелинейным. Например, при удвоении числа лучей соответствующая амплитуда решения получается увеличением коэффициента демпфирования до 1.2. Для каждой сети наблюдений эти значения определяются индивидуально. В качестве основного критерием при нахождении весовых коэффициентов демпфирования используется оценка среднеквадратического среднего (RMS) на каждой итерации. Но он не является абсолютно объективным, поскольку не обеспечивает устойчивости решения. Альтернативным подходом, реализованным в программе PROFIT, к определению оптимальных значений параметров демпфирования является синтетическое моделирование на тестовых примерах с аномалиями фиксированного размера. Например, тесты с шахматной доской.
Скоростные аномалии, полученные после инверсии, вычисляются по регулярной сети и добавляются в скоростную модель, полученную на предыдущей итерации.
( Читать дальше )
- +3
- 3 ноября 2009, 16:40
- комментировать
СЛОЖНОСТНО–СТРУКТУРНЫЙ ПОДХОД К ИССЛЕДОВАНИЮ ОБЛАСТИ ПРИМЕНИМОСТИ АЛГОРИТМА PROFIT часть 1
СЛОЖНОСТНО–СТРУКТУРНЫЙ ПОДХОД К ИССЛЕДОВАНИЮ ОБЛАСТИ ПРИМЕНИМОСТИ АЛГОРИТМА PROFIT
Татьяна Ступина, Иван Кулаков
Аннотация: В работе представлена формальная постановка сложностно — структурного подхода к исследованию области применимости алгоритма PROFIT (PROfile Forward and Inverse Tomographic modeling). Основная идея состоит в определении кластера моделей среды (разреза геологического строения земной коры), представленных изображениями, которые с допустимой погрешностью восстанавливаются алгоритмом. Метрика в пространстве изображений задается специальным образом. Она учитывает изменение поля скоростей и аномальные включения, количественный и качественный состав которых отражает этапы усложнения моделей сред.
Ключевые слова: сейсмическое профилирование, томография, прямое моделирование, синтетическая модель.
ACM Classification: G1.10. Mathematics of Computing — Applications
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.
Введение
Подход к обработке экспериментальных данных зависит от специфики решаемой задачи в конкретной прикладной области и конечной цели, которая ставится в задаче. В различных областях знаний, целью которых является обнаружение причинно-следственных связей какого-либо процесса или явления, необходимо решать обратную задачу, которая, как правило, является неустойчивой как относительно входных данных, так и самого оператора инверсии. Для оценки качества полученного решения также необходимо уметь решать и прямую задачу. На каждом этапе возникают свои трудности, с которыми необходимо справляться, используя, предложенные к обработке данные и основываясь на выбранной модели. Оценить же качество выбранной модели независимо от качества обрабатываемых данных возможно лишь теоретически при известной «истинной» модели [Вапник, 1984].
В данной работе рассматривается алгоритм PROFIT прямого и обратного моделирования профильных данных в сейсмической томографии [Кулаков, 2007]. Преимущества данного алгоритма при решении задач на реальных и синтетических данных подробно отражены в работах И.Ю. Кулакова. В работе представлены основные этапы этого алгоритма, подчеркивающие многопараметрическую сложность и специфику решаемой задачи. Важной компонентой предложенного алгоритма является возможность построения реконструированной модели геологической среды, т.е. глубинного разреза, что является достаточно интересным и важным для задач геологической интерпретации в целях изучения строения земной коры и поиска полезных ископаемых. Для того чтобы оценить множество правдоподобных, относительно экспертных знаний о моделях сред, реконструкций предлагается сложностно — структурный подход.
В работе предложена формальная постановка сложностно — структурного подхода к исследованию области применимости алгоритма PROFIT. Основная идея состоит в определении кластера моделей среды, представленных изображениями глубинных разрезов, которые с допустимой погрешностью восстанавливаются алгоритмом. Элементы кластера формируются в метрическом пространстве изображений относительно некоторого экспертного шаблона (модель, допустимая по смыслу с точки зрения строения земной коры в данном регионе). Другими словами, задается критерий, определяющий допустимую реконструированную модель среды, построенную алгоритмом PROFIT для данного географического региона и фиксированной системы наблюдений.
( Читать дальше )
Татьяна Ступина, Иван Кулаков
Аннотация: В работе представлена формальная постановка сложностно — структурного подхода к исследованию области применимости алгоритма PROFIT (PROfile Forward and Inverse Tomographic modeling). Основная идея состоит в определении кластера моделей среды (разреза геологического строения земной коры), представленных изображениями, которые с допустимой погрешностью восстанавливаются алгоритмом. Метрика в пространстве изображений задается специальным образом. Она учитывает изменение поля скоростей и аномальные включения, количественный и качественный состав которых отражает этапы усложнения моделей сред.
Ключевые слова: сейсмическое профилирование, томография, прямое моделирование, синтетическая модель.
ACM Classification: G1.10. Mathematics of Computing — Applications
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.
Введение
Подход к обработке экспериментальных данных зависит от специфики решаемой задачи в конкретной прикладной области и конечной цели, которая ставится в задаче. В различных областях знаний, целью которых является обнаружение причинно-следственных связей какого-либо процесса или явления, необходимо решать обратную задачу, которая, как правило, является неустойчивой как относительно входных данных, так и самого оператора инверсии. Для оценки качества полученного решения также необходимо уметь решать и прямую задачу. На каждом этапе возникают свои трудности, с которыми необходимо справляться, используя, предложенные к обработке данные и основываясь на выбранной модели. Оценить же качество выбранной модели независимо от качества обрабатываемых данных возможно лишь теоретически при известной «истинной» модели [Вапник, 1984].
В данной работе рассматривается алгоритм PROFIT прямого и обратного моделирования профильных данных в сейсмической томографии [Кулаков, 2007]. Преимущества данного алгоритма при решении задач на реальных и синтетических данных подробно отражены в работах И.Ю. Кулакова. В работе представлены основные этапы этого алгоритма, подчеркивающие многопараметрическую сложность и специфику решаемой задачи. Важной компонентой предложенного алгоритма является возможность построения реконструированной модели геологической среды, т.е. глубинного разреза, что является достаточно интересным и важным для задач геологической интерпретации в целях изучения строения земной коры и поиска полезных ископаемых. Для того чтобы оценить множество правдоподобных, относительно экспертных знаний о моделях сред, реконструкций предлагается сложностно — структурный подход.
В работе предложена формальная постановка сложностно — структурного подхода к исследованию области применимости алгоритма PROFIT. Основная идея состоит в определении кластера моделей среды, представленных изображениями глубинных разрезов, которые с допустимой погрешностью восстанавливаются алгоритмом. Элементы кластера формируются в метрическом пространстве изображений относительно некоторого экспертного шаблона (модель, допустимая по смыслу с точки зрения строения земной коры в данном регионе). Другими словами, задается критерий, определяющий допустимую реконструированную модель среды, построенную алгоритмом PROFIT для данного географического региона и фиксированной системы наблюдений.
( Читать дальше )
- +3
- 3 ноября 2009, 16:37
- комментировать
ЛИНЕЙНЫЕ СТРУКТУРЫ В ПРИКЛАДНЫХ ЗАДАЧАХ И КОНСТРУКТИВНЫЕ МЕТОДЫ ИХ ОПИСАНИЯ часть 3
ЛИНЕЙНЫЕ СТРУКТУРЫ В ПРИКЛАДНЫХ ЗАДАЧАХ И КОНСТРУКТИВНЫЕ МЕТОДЫ ИХ ОПИСАНИЯ
Применения “tips and tricks“- свойств ПдО: линейная регрессия, скалярные наблюдения
Применение ПдО в линейной регрессии определяется тем, что МНК – оценка ^? (оценка метода наименьших квадратов) неизвестного параметра?? R p линейной регрессии p ?1 y? ?? jj? 0 f j ( x )?? на основе наблюдений ( x, y ), x? Rm, y? R1, i? 1, n определяется решением оптимизационной задачи i i i i ^?? Arg min || X?? Y ||2, (11) ??R p в которой X — матрица плана, а Y — вектор – столбец с компонентами y? R1,i? 1,n – вектор наблюдений. В соответствии с соотношением (4) п.13 “tips and tricks“ общее решении задачи (11) определяется соотношением ^?? X ?Y? Z (X )v,v? R p * (12) со свободным параметром v? R p.
Решение задачи МНК — оценивания в виде (12) полностью согласуется с классическим решением уравнения Гаусса – Маркова в виде ^?? (X T X )?1 X TY, Поскольку в случае полного столбцового ранга матрицы плана X?? (X T X )?1 X TY а Z (X )? 0. В этом случае классическом случае множество МНК – оценок в (12) является одно элементным. Применения “tips and tricks“- свойств ПдО: задача терминального управления Под задачей терминального управления для линейноЙ динамической системы с дискретным временем x( k? 1)? A( k ) x( k ) ?b( k )u( k ), x( 0)? x( 0 ), где x( k )? R n, u(k)? R1, A( k )? R n? n, b( k )? R n, k? 0,N, имеют в виду задачу выбора такого управления u(k ), k? 0,N, которое позволяет вывести фазовую траекторию в момент N? 1 на уровень x(1) или, если это невозможно, выбором того же управления минимизировать отклонение 2x( N? 1)? x( 1). Принципиальным результатом для исследования задачи терминального управления является теорема редукции, позволяющая свести задачу терминального управления к СЛАУ.
Теорема (теорема редукции). Задача терминального управления является эквивалентной СЛАУ W ( N? 1)u? x( 1)? A( N? 1) A( N? 2)…A( 0) x( 0 ), в которой вектор u? R N ?1 – объединенный вектор управления, а матрица W ( N? 1) является блочной:
W ( N? 1) ??W ( N? 1,0) #W ( N? 1),1) #…#W ( N? 1,N )?, с блоками W ( N? 1),k ),k? 0,N, определяемыми соотношениями W ( N? 1,k )? A( N ) A( N? 1)…A( k? 1)b( k ),k? 0,N? 1, W ( N? 1,N )? b( N ).
Теорема редукции позволяет исчерпывающим образом исследовать задачу терминального управления с помощью пп.13,14 “tips and tricks”.
( Читать дальше )
Применения “tips and tricks“- свойств ПдО: линейная регрессия, скалярные наблюдения
Применение ПдО в линейной регрессии определяется тем, что МНК – оценка ^? (оценка метода наименьших квадратов) неизвестного параметра?? R p линейной регрессии p ?1 y? ?? jj? 0 f j ( x )?? на основе наблюдений ( x, y ), x? Rm, y? R1, i? 1, n определяется решением оптимизационной задачи i i i i ^?? Arg min || X?? Y ||2, (11) ??R p в которой X — матрица плана, а Y — вектор – столбец с компонентами y? R1,i? 1,n – вектор наблюдений. В соответствии с соотношением (4) п.13 “tips and tricks“ общее решении задачи (11) определяется соотношением ^?? X ?Y? Z (X )v,v? R p * (12) со свободным параметром v? R p.
Решение задачи МНК — оценивания в виде (12) полностью согласуется с классическим решением уравнения Гаусса – Маркова в виде ^?? (X T X )?1 X TY, Поскольку в случае полного столбцового ранга матрицы плана X?? (X T X )?1 X TY а Z (X )? 0. В этом случае классическом случае множество МНК – оценок в (12) является одно элементным. Применения “tips and tricks“- свойств ПдО: задача терминального управления Под задачей терминального управления для линейноЙ динамической системы с дискретным временем x( k? 1)? A( k ) x( k ) ?b( k )u( k ), x( 0)? x( 0 ), где x( k )? R n, u(k)? R1, A( k )? R n? n, b( k )? R n, k? 0,N, имеют в виду задачу выбора такого управления u(k ), k? 0,N, которое позволяет вывести фазовую траекторию в момент N? 1 на уровень x(1) или, если это невозможно, выбором того же управления минимизировать отклонение 2x( N? 1)? x( 1). Принципиальным результатом для исследования задачи терминального управления является теорема редукции, позволяющая свести задачу терминального управления к СЛАУ.
Теорема (теорема редукции). Задача терминального управления является эквивалентной СЛАУ W ( N? 1)u? x( 1)? A( N? 1) A( N? 2)…A( 0) x( 0 ), в которой вектор u? R N ?1 – объединенный вектор управления, а матрица W ( N? 1) является блочной:
W ( N? 1) ??W ( N? 1,0) #W ( N? 1),1) #…#W ( N? 1,N )?, с блоками W ( N? 1),k ),k? 0,N, определяемыми соотношениями W ( N? 1,k )? A( N ) A( N? 1)…A( k? 1)b( k ),k? 0,N? 1, W ( N? 1,N )? b( N ).
Теорема редукции позволяет исчерпывающим образом исследовать задачу терминального управления с помощью пп.13,14 “tips and tricks”.
( Читать дальше )
- +3
- 3 ноября 2009, 15:23
- комментировать
ЛИНЕЙНЫЕ СТРУКТУРЫ В ПРИКЛАДНЫХ ЗАДАЧАХ И КОНСТРУКТИВНЫЕ МЕТОДЫ ИХ ОПИСАНИЯ часть 2
1. “tips and tricks”: LA? L(a(1),..., a(n )). Таким образом, линейное подпространство, порождённое набором векторов, совпадает с подпространством значений матрицы, составленной из векторов набора, как из столбцов.
2. “tips and tricks”: для элементов столбцового и строчного представления матрицы A? Rm ?n справедливы соотношения a( j )? Ae( j ), j? 1,n, T(i )? eT A,i? 1,m.
3. “tips and tricks”: для произведения произвольных матриц? c T B,C со столбовым и строчным ??? (1)? представлением B? (b(1)#...#b(r )),b( j )? Rm, j? 1,r ,C?? " ?,c (r ) ,c(i)? Rn, i? 1,r соответ- ?c T?? (r )? ственно и диагональной матрицы?? diag(?1,..., ?r ) справедливо соотношение rB?C??? b(i )c T. i i ?1 (i )Важной составляющей аппарата конструктивного описания и использования линейных структур является понятие ортогонального проектора, которое полностью отвечает стандартному геометрическому представлению об ортогональном проектировании. Общей, основой эффективного использования ортогональных проекторов является наличие двух эквивалентных определений таких проекторов и возможности их конструктивного построения в связи с линейными подпространствами через псевдообращение.
4. “tips and tricks” («геометрическое определение ортогонального проектора»): для разложения R p? L? L? в прямую сумму ортогональных подпространств ортогональным проектором PL на линейное подпространство PL x? PL (x L? x L? )? x L, где L? R p называется оператор, определяемый соотношением x? x L? x L?, x L? L, x ?L? L?(1)– однозначное представление произвольного вектора x? R p по двум составляющим ортого-нальной суммы. Очевидным образом оператор ортогонального проектирования является линейным оператором.
5. “tips and tricks”: разложение (1) произвольного вектора x? R p в силу симметричности относительно ортогональных слагаемых определяет одновременно два ортогональных проектора: P, P? сL L очевидным соотношением P? P ?L? E p, где E p – единичная матрица соответствующейразмерности.
6. “tips and tricks”: для ортогональногопроектора PL на подпространство L оператор Z L? E p? PL является ортогональным проектором на ортогональное дополнение L? к L: Z? E p? PL? P? .L
7. “tips and tricks“(абстрактное определение ортогонального проектора): для того, чтобы линейный оператор P: R p > R p, был оператором ортогонального проектирования необходимо и достаточно, чтобы он был идемпотентным симметричным оператором. Линейное пространство LP, на которое совершается ортогональное проектирование в соответствии с «геометрическим определением» описывается одним из двух соотношений: L? { x: x? Pu, u? R p }? { x: x? Px, x? R p }.
8. “tips and tricks“(сингулярное или SVD- представление произвольной A? Rm ?n ): для произвольной A? R m ?n ранга r? min(m,n ) справедливо следующее представление матрицы в виде взвешенной суммы тензорных произведений r T где: A?? ?i uivi i ?1, (2) — ?2?…? ?2? 0 общий набор ненулевых собственных чисел матриц AAT, AT A .1- ui r? R m ,i? j,r — ортонормированный набор собственных векторов матрицы AAT, отвечающих ненулевым собственным T 2 2T числам: AA ui? ?i, ?i? 0,i? 1,r ,u i u j? ?ij ,i? j; — vi? R n ,i ?j,r — ортонормированный набор собственных векторов матрицы AT A, отвечающих ненулевым собственным числам: T 2 2 T A Avi? ?i vi, ?i? 0,,i? 1,r ,vi v j? ?ij ,i? j.
9. “tips and tricks“(определение псевдообращения через SVD — представление матрицы): для произвольнойA? R m ?n с SVD — представлением (2) псевдообратная к ней, A?, определяется соотношением r? ?1 T m n A?? ?i vi ui: Ri ?1 > R. (3)Псевдообращение в дальнейшем будет обозначаться аббревиатурой ПдО.Заметим, что SVD — определение ПдО (соотношение (3)) позволяет легко установить, что ПдО коммутирует с транспонированием, а также ряд других полезных соотношений, в частности, что AT (AT )?? A? A.
10. “tips and tricks“: ортогональные проекторы на L A, L A Tопределяется соотношениемrAA??? T, i ?1 AT (AT )? r? A? A? ?v v T i i i ?1
( Читать дальше )
- +3
- 3 ноября 2009, 15:14
- комментировать
ЛИНЕЙНЫЕ СТРУКТУРЫ В ПРИКЛАДНЫХ ЗАДАЧАХ И КОНСТРУКТИВНЫЕ МЕТОДЫ ИХ ОПИСАНИЯ часть 1
ЛИНЕЙНЫЕ СТРУКТУРЫ В ПРИКЛАДНЫХ ЗАДАЧАХ И КОНСТРУКТИВНЫЕ МЕТОДЫ ИХ ОПИСАНИЯ
Авторы Николай Кириченко, Владимир Донченко
Аннотация: Рассмотрены свойства основных линейных структур в евклидовых пространствах, развиты конструктивные способы их описания и построения на основе систематического развития и применения аппарата псевдообращения по Муру — Пенроузу. Важность приведённых результатов проиллюстрирована на широком спектре прикладных задач: от регрессионного анализа и задач прогноза до теории оптимального управления.
Ключевые слова: Псевдообращение по Муру — Пенроузу, сингулярное представление матрицы, метод наименьших квадратов, линейная регрессия, системы оптимального управления, прогноз, кластеризация, искусственные нейронные сети.
ACM Classification Keywords: G.3 Probability and statistics, G.1.6. Numerical analysis: Optimization; G.2.m. Discrete mathematics: miscellaneous.
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.
Вступление
Как отмечалось в работе [Донченко,2009 ], апелляция к «структуре объекта» ассоциируется с представлением об объекте, как чём-то едином, составленном из взаимодействующих между собою частей. Как правило, «структура» и «связи» между частями объекта, рассматриваемого как единое целое, употребляются как реализующие одно и тоже представление об объекте с тем дополнением, что
«структура» – это совокупность частей объекта плюс «связи» между ними. Среди важнейших математических структур, отмеченных в упомянутой выше работе, особое место занимают «линейные структуры». К ним можно отнести линейные пространства и подпространства, гиперплоскости а также – линейные операторы и функционалы. Среди линейных структур по богатству возможностей использования связей занимает евклидово пространство: конечномерное линейное плюс скалярное произведение. Богатство свойств линейных структур: и в варианте линейных пространств и подпространств, и в варианте операторов соответствующего вида, – в математическом моделировании объектов трудно переоценить. Это касается как абстрактных математических, так и исследований прикладного характера. В полной мере сказанное выше относится, в частности, к алгебре, регрессионному анализу, теории случайных процессов, теории дифференциальных и интегральных уравнений, систем оптимального управления, прикладным задачам классификации, прогноза и т.д. Важную роль в прикладных исследованиях играют конструктивные методы описания соответствующих объектов. В том, что касается линейных операторов и линейных функционалов, вопрос конструктивности решается построением матриц соответствующих объектов, а для операций – использованием операций матричной алгебры. В том, что касается подпространств, порождённых теми или иными совокупностями векторов, дело обстоит сложнее. Их конструктивное описание можно получить, связав указанные объекты с пространством значений подходящей матрицы, которое в свою очередь описывают подходящим ортогональным проектором. Именно этот подход развивается ниже. Отметим, что ортогональные проекторы играют важную роль в исчерпывающем исследовании систем линейных алгебраических уравнений (СЛАУ). Принципиально важны они также в постановке и решении важных оптимизационных задач с квадратическим функционалом качества в евклидовых пространствах, в том числе – в построении наилучших квадратических приближений правой части СЛАУ значениями левой, когда СЛАУ несовместна. Такие наилучшие приближения называют также псевдорешениями. Конструктивное описание ортогональных проекторов в связи с естественными подпространствами линейного оператора прямо определяется псевдообращением по Муру — Пенроузу[Moore,1920], [Penrose, 1955](см. также, например, [Алберт, 1977]). Отметим, также, что важную роль в конструктивном решении прикладных задач с использованием линейных структур играет сингулярное представление (его называют также сингулярным разложением или SVD — представлением) матрицы в специфической записи в виде взвешенной суммы тензорных произведений специального набора пар векторов. Ниже рассматриваются основные свойства линейных структур, основные особенности и возможности (“tips and tricks”) их конструктивного описания, а также – использования в для конструктивного решения важнейших прикладных задач прогноза, кластеризации и классификации, в других областях.
( Читать дальше )
Авторы Николай Кириченко, Владимир Донченко
Аннотация: Рассмотрены свойства основных линейных структур в евклидовых пространствах, развиты конструктивные способы их описания и построения на основе систематического развития и применения аппарата псевдообращения по Муру — Пенроузу. Важность приведённых результатов проиллюстрирована на широком спектре прикладных задач: от регрессионного анализа и задач прогноза до теории оптимального управления.
Ключевые слова: Псевдообращение по Муру — Пенроузу, сингулярное представление матрицы, метод наименьших квадратов, линейная регрессия, системы оптимального управления, прогноз, кластеризация, искусственные нейронные сети.
ACM Classification Keywords: G.3 Probability and statistics, G.1.6. Numerical analysis: Optimization; G.2.m. Discrete mathematics: miscellaneous.
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.
Вступление
Как отмечалось в работе [Донченко,2009 ], апелляция к «структуре объекта» ассоциируется с представлением об объекте, как чём-то едином, составленном из взаимодействующих между собою частей. Как правило, «структура» и «связи» между частями объекта, рассматриваемого как единое целое, употребляются как реализующие одно и тоже представление об объекте с тем дополнением, что
«структура» – это совокупность частей объекта плюс «связи» между ними. Среди важнейших математических структур, отмеченных в упомянутой выше работе, особое место занимают «линейные структуры». К ним можно отнести линейные пространства и подпространства, гиперплоскости а также – линейные операторы и функционалы. Среди линейных структур по богатству возможностей использования связей занимает евклидово пространство: конечномерное линейное плюс скалярное произведение. Богатство свойств линейных структур: и в варианте линейных пространств и подпространств, и в варианте операторов соответствующего вида, – в математическом моделировании объектов трудно переоценить. Это касается как абстрактных математических, так и исследований прикладного характера. В полной мере сказанное выше относится, в частности, к алгебре, регрессионному анализу, теории случайных процессов, теории дифференциальных и интегральных уравнений, систем оптимального управления, прикладным задачам классификации, прогноза и т.д. Важную роль в прикладных исследованиях играют конструктивные методы описания соответствующих объектов. В том, что касается линейных операторов и линейных функционалов, вопрос конструктивности решается построением матриц соответствующих объектов, а для операций – использованием операций матричной алгебры. В том, что касается подпространств, порождённых теми или иными совокупностями векторов, дело обстоит сложнее. Их конструктивное описание можно получить, связав указанные объекты с пространством значений подходящей матрицы, которое в свою очередь описывают подходящим ортогональным проектором. Именно этот подход развивается ниже. Отметим, что ортогональные проекторы играют важную роль в исчерпывающем исследовании систем линейных алгебраических уравнений (СЛАУ). Принципиально важны они также в постановке и решении важных оптимизационных задач с квадратическим функционалом качества в евклидовых пространствах, в том числе – в построении наилучших квадратических приближений правой части СЛАУ значениями левой, когда СЛАУ несовместна. Такие наилучшие приближения называют также псевдорешениями. Конструктивное описание ортогональных проекторов в связи с естественными подпространствами линейного оператора прямо определяется псевдообращением по Муру — Пенроузу[Moore,1920], [Penrose, 1955](см. также, например, [Алберт, 1977]). Отметим, также, что важную роль в конструктивном решении прикладных задач с использованием линейных структур играет сингулярное представление (его называют также сингулярным разложением или SVD — представлением) матрицы в специфической записи в виде взвешенной суммы тензорных произведений специального набора пар векторов. Ниже рассматриваются основные свойства линейных структур, основные особенности и возможности (“tips and tricks”) их конструктивного описания, а также – использования в для конструктивного решения важнейших прикладных задач прогноза, кластеризации и классификации, в других областях.
( Читать дальше )
- +2
- 3 ноября 2009, 15:11
- комментировать
СЕГМЕНТАЦИЯ АНОМАЛЬНЫХ ОБЛАСТЕЙ НА МУЛЬТИСПЕКТРАЛЬНЫХ ИЗОБРАЖЕНИЯХ ШЕЙКИ МАТКИ часть 3
Результаты сегментации
Ниже приведены результаты сегментации используя различные функции. Различные сегменты выделены разными оттенками серого.
По изображениям видно, что применение всех функций дает приблизительно одинаковый результат, поэтому в дальнейшем будет использоваться только Гауссова функция принадлежности, так как это наиболее стандартная функция.
Далее представлены результаты сегментации на различное количество кластеров 10, 20 и 50 соответственно: Изображения были разбиты на разное количество сегментов для дальнейшей проверки по базе типов тканей. Оптимальное количество сегментов можно будет определить при дальнейшей работе, хотя уже на данном этапе видно, что 20 сегментов отображают те области, которых не видно при 10 сегментах, что 20 и 50 сегментов практически не отличаются, хотя проверка 50 сегментов по базе типов тканей может занять значительно больше времени.
Рис. 3 Сегментация изображения, применяя Гауссову, усеченную Гауссову и колоколообразную функции
Выводы
−Использование сети Кохонена обусловлено намерением избежать влияния человеческого фактора при сегментации изображения.
−По результатам экспериментов видно, что использование всех функций соседства дает одинаковый результат.
−Были проведены эксперименты по разбиению на разные количества сегментов и уже на данном этапе работы видно, что использование 10 сегментов может бытьнедостаточным, так как не полностью отображает картину состояния органа.
- +2
- 3 ноября 2009, 14:07
- комментировать
СЕГМЕНТАЦИЯ АНОМАЛЬНЫХ ОБЛАСТЕЙ НА МУЛЬТИСПЕКТРАЛЬНЫХ ИЗОБРАЖЕНИЯХ ШЕЙКИ МАТКИ часть 2
Методы
Для сегментации изображений была разработана программа, в которой использовались готовые библиотеки. Приложения с усеченной Гауссовой и колоколообразной функциями соседства были разработаны самостоятельно для проверки их эффективности.
Карты Кохонена Сети, называемые картами Кохонена, — это нейронные сети которые используют неконтролируемое обучение. Обучающее множество состоит лишь из значений входных переменных, в процессе обучения нет сравнивания выходов нейронов с эталонными значениями. Можно сказать, что такая сеть учится понимать структуру данных. Идея сети Кохонена принадлежит финскому ученому Тойво Кохонену (1982 год). Основной принцип работы сетей — введение в правило обучения нейрона информации относительно его расположения [Зайченко Ю.П. 2004].
Самоорганизующаяся сеть подразумевает использование упорядоченной структуры нейронов. Обычно используются одно и двумерные сетки. При этом каждый нейрон представляет собой n-мерный вектор-столбец w = [w1, w2 ,..., wn ]T, где n определяется размерностью исходного пространства (размерностью входных векторов), wi — вес i-го нейрона. Применение одно и двумерных сеток связано с тем, что возникают проблемы при отображении пространственных структур большей размерности.
Обычно нейроны располагаются в узлах двумерной сетки с прямоугольными или шестиугольными ячейками. При этом, как было сказано выше, нейроны также взаимодействуют друг с другом. Величина этого взаимодействия определяется расстоянием между нейронами на карте. На рисунке 1 дан пример расстояния для шестиугольной и четырехугольной сеток.
При этом легко заметить, что для шестиугольной сетки расстояние между нейронами больше совпадает с евклидовым расстоянием, чем для четырехугольной сетки.
( Читать дальше )
- +2
- 3 ноября 2009, 13:59
- комментировать
СЕГМЕНТАЦИЯ АНОМАЛЬНЫХ ОБЛАСТЕЙ НА МУЛЬТИСПЕКТРАЛЬНЫХ ИЗОБРАЖЕНИЯХ ШЕЙКИ МАТКИ часть 1
Катерина Малышевская
Аннотация: В работе представлена сегментация мультиспектральных изображений шейки матки. Представлена сеть Кохонена для сегментации изображений и коротко изложена ее суть. Приведены результаты работы, сделан анализ полученных результатов и выводы относительно проведенной работы.
Ключевые слова: сегментация, сеть Кохонена, шейка матки, диагностика.
ACM Classification Keywords: I.5.1 Pattern Recognition — Neural nets
Аннотация: В работе представлена сегментация мультиспектральных изображений шейки матки. Представлена сеть Кохонена для сегментации изображений и коротко изложена ее суть. Приведены результаты работы, сделан анализ полученных результатов и выводы относительно проведенной работы.
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.
Введение
В данной работе рассмотрена возможность сегментации мультиспектрального изображения шейки матки. Такая задача продиктована необходимостью ранней диагностики заболевания с использованием компьютерной системы, которая поможет врачу определить области с большим риском возникновения раковой трансформации ткани. Данная система базируется на утверждении, что оптические свойства здоровой клетки отличаются от свойств больной и это отличие более выражено, чем отличия клеток разных людей. В качестве исходных данных в данной работе мы имеем информацию о 206 пациентках, прошедших диагностику в клинике при помощи новой оптической системы, внедренной в медицинском университете Аризоны (США). Параллельно врач ставил диагноз пациенткам путем классификации типов тканей, взятых на биопсию. Участки, из которых была сделана биопсия, были обозначены на снимке, и результаты биопсии были сопоставлены с указанными участками на изображении [Schoonmaker J. 2007].
( Читать дальше )
- +2
- 3 ноября 2009, 13:45
- комментировать
АВТОМАТИЗИРОВАННОЕ СОЗДАНИЕ ТЕЗАУРУСА ТЕРМИНОВ ПРЕДМЕТНОЙ ОБЛАСТИ ДЛЯ ЛОКАЛЬНЫХ ПОИСКОВЫХ СИСТЕМ часть 3
Построение тезауруса терминов
Полученный предварительный список терминов редактируется вручную с помощью утилиты – редактора тезауруса терминов предметной области (общий вид окна редактора изображен на Рис. 1.)
Рисунок 1. Главная форма редактора тезауруса терминов предметной области
Входными данными для утилиты является список терминов, сформированный программой «Конспект». Эксперт-аналитик вручную связывает термины, являющиеся синонимами для заданной предметной области (см. Рис.1). Полученные кортежи синонимов терминов предметной области сохраняются в XML- файл заданной структуры, который может использоваться поисковой системой среды Microsoft Office SharePoint Server 2007 в качестве тезауруса (списка расширений). В общем виде процесс автоматизированного построения тезауруса терминов предметной области изображен на Рис. 2.
( Читать дальше )
- +2
- 3 ноября 2009, 13:27
- комментировать