Лекция3.6:Метод потенциальных функций Предположим, что требуется разделить два непересекающихся образа V1 и V2. Это значит, что в пространстве изображений. - презентация

1 Лекция3.6:Метод потенциальных функций Предположим, что требуется разделить два непересекающихся образа V1 и V2. Это значит, что в пространстве изображений существует, по крайней мере, одна функция, которая полностью разделяет множества, соответствующие образам V1 и V2. Эта функция должна принимать положительные значения в точках, соответствующих объектам, принадлежащим образу V1, и отрицательные в точках образа V2. В общем случае таких разделяющих функций может быть много, тем больше, чем компактней разделяемые множества. В процессе обучения требуется построить одну из этих функций, иногда в некотором смысле наилучшую. Предположим, что требуется разделить два непересекающихся образа V1 и V2. Это значит, что в пространстве изображений существует, по крайней мере, одна функция, которая полностью разделяет множества, соответствующие образам V1 и V2. Эта функция должна принимать положительные значения в точках, соответствующих объектам, принадлежащим образу V1, и отрицательные в точках образа V2. В общем случае таких разделяющих функций может быть много, тем больше, чем компактней разделяемые множества. В процессе обучения требуется построить одну из этих функций, иногда в некотором смысле наилучшую. Метод потенциальных функций связан со следующей процедурой. В процессе обучения с каждой точкой пространства изображений, соответствующей единичному объекту из обучающей последовательности, связывается функция U(X, Xi), заданная на всем пространстве и зависящая от Xi как от параметра. Такие функции называются потенциальными, так как они напоминают функции потенциала электрического поля вокруг точечного электрического заряда. Изменение потенциала электрического поля по мере удаления от заряда обратно пропорционально квадрату расстояния. Потенциал, таким образом, может служить мерой удаления точки от заряда. Когда поле образовано несколькими зарядами, потенциал в каждой точке этого поля равен сумме потенциалов, создаваемых в этой точке каждым из зарядов. Если заряды, образующие поле, расположены компактной группой, потенциал поля будет иметь наибольшее значение внутри группы зарядов и убывать по мере удаления от нее. Метод потенциальных функций связан со следующей процедурой. В процессе обучения с каждой точкой пространства изображений, соответствующей единичному объекту из обучающей последовательности, связывается функция U(X, Xi), заданная на всем пространстве и зависящая от Xi как от параметра. Такие функции называются потенциальными, так как они напоминают функции потенциала электрического поля вокруг точечного электрического заряда. Изменение потенциала электрического поля по мере удаления от заряда обратно пропорционально квадрату расстояния. Потенциал, таким образом, может служить мерой удаления точки от заряда. Когда поле образовано несколькими зарядами, потенциал в каждой точке этого поля равен сумме потенциалов, создаваемых в этой точке каждым из зарядов. Если заряды, образующие поле, расположены компактной группой, потенциал поля будет иметь наибольшее значение внутри группы зарядов и убывать по мере удаления от нее.

2 Обучающей последовательности объектов соответствует последовательность векторов X1, X2, …, в пространстве изображений с которыми связана последовательность U(X, X1), U(X, X2), … потенциальных функций, используемых для построения функций f(X1, X2, …). По мере увеличения числа объектов в процессе обучения функция f должна стремиться к одной из разделяющих функций. В результате обучения могут быть построены потенциальные функции для каждого образа: Обучающей последовательности объектов соответствует последовательность векторов X1, X2, …, в пространстве изображений с которыми связана последовательность U(X, X1), U(X, X2), … потенциальных функций, используемых для построения функций f(X1, X2, …). По мере увеличения числа объектов в процессе обучения функция f должна стремиться к одной из разделяющих функций. В результате обучения могут быть построены потенциальные функции для каждого образа:, (ф. 1), (ф. 1) В качестве разделяющей функции f(X) можно выбрать функцию вида: В качестве разделяющей функции f(X) можно выбрать функцию вида:, (ф. 2), (ф. 2) которая положительна для объектов одного образа и отрицательна для объектов другого. которая положительна для объектов одного образа и отрицательна для объектов другого. В качестве потенциальной функции рассмотрим функцию вида В качестве потенциальной функции рассмотрим функцию вида, (ф. 3), (ф. 3) где j j(X) линейно независимая система функций; l j действительные числа, отличные от нуля для всех j = 1, 2, … ; Xi точка, соответствующая i-му объекту из обучающей последовательности. Предполагается, что j j(X) и U(X, Xi) ограничены при XI V1 E V2; y j (X)=l jj j(X). где j j(X) линейно независимая система функций; l j действительные числа, отличные от нуля для всех j = 1, 2, … ; Xi точка, соответствующая i-му объекту из обучающей последовательности. Предполагается, что j j(X) и U(X, Xi) ограничены при XI V1 E V2; y j (X)=l jj j(X).

3 В процессе обучения предъявляется обучающая последовательность и на каждом n-м такте обучения строится приближение fn(X) характеризуется следующей основной рекуррентной процедурой: В процессе обучения предъявляется обучающая последовательность и на каждом n-м такте обучения строится приближение fn(X) характеризуется следующей основной рекуррентной процедурой:, (ф. 4), (ф. 4) Разновидности алгоритмов потенциальных функций отличаются выбором значений qn и rn, которые являются фиксированными функциями номера n. Как правило, qn? 1, а rn выбирается в виде: Разновидности алгоритмов потенциальных функций отличаются выбором значений qn и rn, которые являются фиксированными функциями номера n. Как правило, qn? 1, а rn выбирается в виде:, (ф. 5), (ф. 5) где S(fn, f) невозрастающие функции, причем где S(fn, f) невозрастающие функции, причем (ф. 6) (ф. 6) Коэффициенты g n представляют собой неотрицательную числовую последовательность, зависящую только от номера n. Кроме того, Коэффициенты g n представляют собой неотрицательную числовую последовательность, зависящую только от номера n. Кроме того, и (например, g n=1/n) или g n=const. и (например, g n=1/n) или g n=const. Разработано несколько вариантов алгоритмов потенциальных функций, различие между которыми состоит в выборе законов коррекции разделяющей функции от шага к шагу, т. е. в выборе коэффициентов rn. Приведем два основных алгоритма потенциальных функций. Разработано несколько вариантов алгоритмов потенциальных функций, различие между которыми состоит в выборе законов коррекции разделяющей функции от шага к шагу, т. е. в выборе коэффициентов rn. Приведем два основных алгоритма потенциальных функций.

4 1. Будем считать, что f0(X)? 0 (нулевое приближение). Пусть в результате применения алгоритма после n-го шага построена разделяющая функция fn(X), а на (n+1)-м шаге предъявлено изображение Xn+1, для которого известно действительное значение разделяющей функции f(Xn+1). Тогда функция fn+1(X) строится по следующему правилу: 1. Будем считать, что f0(X)? 0 (нулевое приближение). Пусть в результате применения алгоритма после n-го шага построена разделяющая функция fn(X), а на (n+1)-м шаге предъявлено изображение Xn+1, для которого известно действительное значение разделяющей функции f(Xn+1). Тогда функция fn+1(X) строится по следующему правилу: (ф. 7) (ф. 7) 2. Во втором алгоритме также принимается, что f0(X)? 0. Переход к следующему приближению, т. е. переход от функции fn(X) к fn+1(X), осуществляется в результате следующей рекуррентной процедуры: 2. Во втором алгоритме также принимается, что f0(X)? 0. Переход к следующему приближению, т. е. переход от функции fn(X) к fn+1(X), осуществляется в результате следующей рекуррентной процедуры: (ф. 8) (ф. 8) где l произвольная положительная константа, удовлетворяющая условию l =(1/2)? max(X, Xi). где l произвольная положительная константа, удовлетворяющая условию l =(1/2)? max(X, Xi). Если в (ф. 3) принять Если в (ф. 3) принять,, и предположить, что xv может иметь только два значения 0 и 1, то в этом случае алгоритм потенциальных функций будет совпадать со схемой перцептрона с индивидуальными порогами А-элементов и с коррекцией ошибок. Поэтому многие теоретические положения метода потенциальных функций могут быть успешно применены для анализа некоторых перцептронных схем. и предположить, что xv может иметь только два значения 0 и 1, то в этом случае алгоритм потенциальных функций будет совпадать со схемой перцептрона с индивидуальными порогами А-элементов и с коррекцией ошибок. Поэтому многие теоретические положения метода потенциальных функций могут быть успешно применены для анализа некоторых перцептронных схем.

5 Лекция3.7:Метод группового учета аргументов МГУА Метод наименьших квадратов Метод наименьших квадратов Перед тем, как начинать рассмотрение МГУА, было бы полезно вспомнить или узнать впервые метод наименьших квадратов наиболее распространенный метод подстройки линейно зависимых параметров. Перед тем, как начинать рассмотрение МГУА, было бы полезно вспомнить или узнать впервые метод наименьших квадратов наиболее распространенный метод подстройки линейно зависимых параметров. Рассмотрим для примера МНК для трех аргументов: Рассмотрим для примера МНК для трех аргументов: Пусть функция T=T(U, V, W) задана таблицей, то есть из опыта известны числа Ui, Vi, Wi, Ti ( i = 1, …, n). Будем искать зависимость между этими данными в виде: Пусть функция T=T(U, V, W) задана таблицей, то есть из опыта известны числа Ui, Vi, Wi, Ti ( i = 1, …, n). Будем искать зависимость между этими данными в виде: (ф. 1) (ф. 1) где a, b, c неизвестные параметры. где a, b, c неизвестные параметры. Подберем значения этих параметров так, чтобы была наименьшей сумма квадратов уклонений опытных данных Ti и теоретических Ti = aUi + bVi + cWi, то есть сумма: Подберем значения этих параметров так, чтобы была наименьшей сумма квадратов уклонений опытных данных Ti и теоретических Ti = aUi + bVi + cWi, то есть сумма: (ф. 2) (ф. 2) Величина s является функцией трех переменных a, b, c. Необходимым и достаточным условием существования минимума этой функции является равенство нулю частных производных функции s по всем переменным, то есть: Величина s является функцией трех переменных a, b, c. Необходимым и достаточным условием существования минимума этой функции является равенство нулю частных производных функции s по всем переменным, то есть:

6 (ф. 3) (ф. 3) Так как: Так как: (ф. 4) (ф. 4) то система для нахождения a, b, c будет иметь вид: то система для нахождения a, b, c будет иметь вид: (ф. 5) (ф. 5) Данная система решается любым стандартным методом решения систем линейных уравнений (Гаусса, Жордана, Зейделя, Крамера). Данная система решается любым стандартным методом решения систем линейных уравнений (Гаусса, Жордана, Зейделя, Крамера). Рассмотрим некоторые практические примеры нахождения приближающих функций: Рассмотрим некоторые практические примеры нахождения приближающих функций: y = a x2 + b x + g y = a x2 + b x + g Задача подбора коэффициентов a, b, g сводится к решению общей задачи при T=y, U=x2, V=x, W=1, a=a, b=b, g=c. Задача подбора коэффициентов a, b, g сводится к решению общей задачи при T=y, U=x2, V=x, W=1, a=a, b=b, g=c.

7 f(x, y) = a sin(x) + b cos(y) + g /x f(x, y) = a sin(x) + b cos(y) + g /x Задача подбора коэффициентов a, b, g сводится к решению общей задачи при T=f, U=sin(x), V=cos(y), W=1/x, a =a, b =b, g =c. Задача подбора коэффициентов a, b, g сводится к решению общей задачи при T=f, U=sin(x), V=cos(y), W=1/x, a =a, b =b, g =c. Если мы распространим МНК на случай с m параметрами, Если мы распространим МНК на случай с m параметрами, (ф. 6) (ф. 6) то путем рассуждений, аналогичных приведенным выше, получим следующую систему линейных уравнений: то путем рассуждений, аналогичных приведенным выше, получим следующую систему линейных уравнений: (ф. 7) (ф. 7) где, где, Общая схема построения алгоритмов метода группового учета аргументов (МГУА). Общая схема построения алгоритмов метода группового учета аргументов (МГУА).

8 Рис. 1. Селекция самого черного тюльпана при расширяющемся опытном поле (эквивалент полного перебора), и при постоянном размере поля (эквивалент селекции при сохранении свободы выбора решений F = const).

9 Заимствование алгоритмов переработки информации у природы является одной из основных идей кибернетики. "Гипотеза селекции" утверждает, что алгоритм массовой селекции растений или животных является оптимальным алгоритмом переработки информации в сложных задачах. При массовой селекции высевается некоторое количество семян. В результате опыления образуются сложные наследственные комбинации. Селекционеры выбирают некоторую часть растений, у которых интересующее их свойство выражено больше всего (эвристический критерий). Семена этих растений собирают и снова высевают для образования новых, еще более сложных комбинаций. Через несколько поколений селекция останавливается и ее результат является оптимальным. Если чрезмерно продолжать селекцию, то наступит "инцухт" вырождение растений. Существует оптимальное число поколений и оптимальное количество семян, отбираемых в каждом из них. Заимствование алгоритмов переработки информации у природы является одной из основных идей кибернетики. "Гипотеза селекции" утверждает, что алгоритм массовой селекции растений или животных является оптимальным алгоритмом переработки информации в сложных задачах. При массовой селекции высевается некоторое количество семян. В результате опыления образуются сложные наследственные комбинации. Селекционеры выбирают некоторую часть растений, у которых интересующее их свойство выражено больше всего (эвристический критерий). Семена этих растений собирают и снова высевают для образования новых, еще более сложных комбинаций. Через несколько поколений селекция останавливается и ее результат является оптимальным. Если чрезмерно продолжать селекцию, то наступит "инцухт" вырождение растений. Существует оптимальное число поколений и оптимальное количество семян, отбираемых в каждом из них. Алгоритмы МГУА воспроизводят схему массовой селекции [5], показанной на Рис. 1. В них есть генераторы усложняющихся из ряда в ряд комбинаций и пороговые самоотборы лучших из них. Так называемое полное описание объекта Алгоритмы МГУА воспроизводят схему массовой селекции [5], показанной на Рис. 1. В них есть генераторы усложняющихся из ряда в ряд комбинаций и пороговые самоотборы лучших из них. Так называемое полное описание объекта j = f(x1,x2,x3,...,xm), j = f(x1,x2,x3,...,xm), где f некоторая элементарная функция, например степенной полином, заменяется несколькими рядами "частных" описаний: где f некоторая элементарная функция, например степенной полином, заменяется несколькими рядами "частных" описаний: 1-ряд селекции: y1= f(x1x2), y2= f(x1x3),..., ys= f(xm-1xm), 1-ряд селекции: y1= f(x1x2), y2= f(x1x3),..., ys= f(xm-1xm), 2-ряд селекции: z1= f(y1y2), z2= f(y1y2),..., zp= f(ys-1ys), где s=c2, p=cs2 и т.д. 2-ряд селекции: z1= f(y1y2), z2= f(y1y2),..., zp= f(ys-1ys), где s=c2, p=cs2 и т.д. Входные аргументы и промежуточные переменные сопрягаются попарно, и сложность комбинаций на каждом ряду обработки информации возрастает (как при массовой селекции), пока не будет получена единственная модель оптимальной сложности. Входные аргументы и промежуточные переменные сопрягаются попарно, и сложность комбинаций на каждом ряду обработки информации возрастает (как при массовой селекции), пока не будет получена единственная модель оптимальной сложности.

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

11

12 В этом алгоритме [5, 6] используются частные описания, представленные в следующих формулах: В этом алгоритме [5, 6] используются частные описания, представленные в следующих формулах: yi=a0+a1xi+a2xj+a3xixj; yi=a0+a1xi+a2xj+a3xixj; yk=a0+a1xi+a2xj+a3xixj+a4xi2+a5xj2. yk=a0+a1xi+a2xj+a3xixj+a4xi2+a5xj2. Сложность модели увеличивается от ряда к ряду селекции как по числу учитываемых аргументов, так и по степени. Степень полного описания быстро растет. На первом ряду квадратичные описания, на втором четвертой степени, на третьем восьмой и т. д. В связи с этим минимум критерия селекции находится быстро, но не совсем точно. Кроме того, имеется опасность потери существенного аргумента, особенно на первых рядах селекции (в случае отсутствия протекции). Специальные теоремы теории МГУА определяют условия, при которых результат селекции не отличается от результата полного перебора моделей. Сложность модели увеличивается от ряда к ряду селекции как по числу учитываемых аргументов, так и по степени. Степень полного описания быстро растет. На первом ряду квадратичные описания, на втором четвертой степени, на третьем восьмой и т. д. В связи с этим минимум критерия селекции находится быстро, но не совсем точно. Кроме того, имеется опасность потери существенного аргумента, особенно на первых рядах селекции (в случае отсутствия протекции). Специальные теоремы теории МГУА определяют условия, при которых результат селекции не отличается от результата полного перебора моделей. Для того чтобы степень полного уравнения повышалась с каждым рядом селекции на единицу, достаточно рассматривать все аргументы и их ковариации как обобщенные аргументы и пользоваться составленными для них линейными описаниями. Для того чтобы степень полного уравнения повышалась с каждым рядом селекции на единицу, достаточно рассматривать все аргументы и их ковариации как обобщенные аргументы и пользоваться составленными для них линейными описаниями.