ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 8, с. 1423-1427
УДК 519.7
ОБ ОДНОМ МЕТОДЕ ПОСТРОЕНИЯ РАСПОЗНАЮЩЕГО АЛГОРИТМА В АЛГЕБРЕ
НАД МНОЖЕСТВОМ ВЫЧИСЛЕНИЯ ОЦЕНОК^
© 2007 г. М. Ю. Романов
(141700 Долгопрудный, М. о., Институтский пер., 9, МФТИ) e-mail: mromanov@ccas.ru Поступила в редакцию 24.01.2007 г.
Предлагается метод построения алгоритма в алгебре над множеством вычисления оценок в алгебраическом расширении наименьшей степени. Библ. 5.
Ключевые слова: алгоритм распознавания, алгебра над множеством вычисления оценок.
В настоящей работе рассматривается метод построения распознающего алгоритма в алгебре над множеством вычисления оценок. Будем использовать обозначения, применяемые в [1].
Рассмотрим алгоритмы вычисления оценок (АВО). Такие алгоритмы составляются из распознающего оператора и решающего правила. Распознающий оператор вычисляет оценки близости объектов к классам, а решающее правило на основе этих оценок классифицирует объекты.
Для распознающих операторов (РО) можно ввести операции сложения, умножения на константу и операторного умножения таким образом, что это будут операции над оценками, т.е. над значениями операторов. Эти операции индуцируют соответствующие операции над алгоритмами распознавания. Над множеством распознающих операторов B* = {B1, B2, ..., Bn} введем линейное замыкание
L (B *) = { c Bi+ c2 B2 + ... + CnBn }, а также алгебраическое замыкание k-й степени
U (B*) = L { B1 ■ B2 ■...■ Bs : Bj, B2,..., Bs e B *, 1 < s < k}.
Множество алгоритмов, построенное на алгебраическом замыкании k-й степени над некоторым набором РО, будем называть алгебраическим расширением k-й степени.
Для краткости степенью алгоритма A будем называть степень алгебраического расширения, в котором построен этот алгоритм. Иначе говоря, это можно понимать как степень полинома над операторами {Bk}, который является распознающим оператором алгоритма A.
Для применения корректного алгоритма A важной характеристикой является его степень. При решении практических задач имеет смысл рассматривать полиномы операторов небольшой степени, поэтому актуальной является проблема минимизации степени полинома.
В работе [2] показано, что для задачи с обучающей выборкой из q объектов и с l классами существует алгоритм степени не выше
[ log 2ql]. (1)
Однако при решении конкретных задач его степень может оказаться существенно ниже. В настоящей работе рассматривается метод построения полиномиального распознающего оператора наименьшей степени, при этом исходный набор распознающих операторов считается заданным.
Опишем формальную постановку задачи построения распознающего алгоритма. Введем обучающую выборку
Sm = {Si = (an, ..., am), i = 1, m}
^ Работа выполнена при финансовой поддержке РФФИ (коды проектов 05-01-00718, 06-07-89299) и гранта Президиума РФ по поддержке ведущих научных школ НШ-5833.2006.1.
1424 РОМАНОВ
и контрольную выборку
5 = {= (Ь,1, ..., Ь1П), I = 1, "}.
Начальная информация 10 задается обучающей выборкой и информационными векторами а (Я), 1 = 1, т . Здесь
а(5) = (а 1} = Р,(Я,) = (5 е К,), у = й).
Таким образом,
10 = {Ът, а(Я), I = 1, т }. Задача распознавания 2 = (10, 5") определяется начальной информацией 10 и контрольной выборкой 5 . Для каждого контрольного вектора необходимо найти информационный вектор
в (Я1) = ф,, = Р/5") = (Я е К),у = 17/).
Рассмотрим множество алгоритмов {А} решения задачи 2 = (10, 5"), представленных в виде произведения операторов А = ВС. Здесь оператор В определяет матрицу оценок В(2) = ||Гу||" х/, где Г, - действительные числа, а оператор С - матрицу ответов С(||Гу||"х) = Цру-Ц"х/, где ву е {0, 1, А}.
Для задачи 2 и заданного множества алгоритмов {А} при выполнении некоторых условий можно построить алгоритм А* (из алгебраического замыкания множества {А} некоторой степени к), определяющий значения Ру(Я') без ошибок (см. [3], [4]).
Будем использовать стандартные пороговые решающие правила
С(||ГУ||, X i) = ||С(Гу)|| q X i, С(Гг]) =
0, гу < Cl5
1, Гг] > c2, 0 < Ci < c2, А, ci <Гу < C2.
Элементы матрицы ответов можно разбить на два множества: ||ßuv||qX i = M0 u M1, где Mi = = {(u, v) : ßuV = i}, q - число объектов, I - число классов.
Оператор B с матрицей оценок B(Z) = ||ruv||q X i называется допустимым для задачи Z, если существует хотя бы одна пара (u, v) е M1 такая, что для всех (i, j) е M0 справедливо неравенство
Tuv (в) > |Г j( B )| .
Такая пара (u, v) называется отмеченной в B, и множество отмеченных в B пар обозначим через M(B). Фактически это означает, что отмеченные пары "отделены" от всех пар (i, j) таких, что объект Si не принадлежит классу Kj. Поэтому при некоторых порогах c1, c2 алгоритм B ■ C будет давать правильные ответы для всех пар, отмеченных в B.
Допускается альтернативный способ определения отмеченных точек. Пара (u, v) называется отмеченной в B при некоторой фиксированной величине 5, если для всех (i, j) е M0 имеет место неравенство
Tuv(B) > |Гу(B)| + 5.
При таком определении все дальнейшие рассуждения остаются справедливыми.
Пусть
r!L(B) = max |ГjB)|,
(i, j) е Mo
rU B) = min |Г ij( B )|.
(i, j)е M(B)
Введем обозначения
Г( B) = [Гтп( B )]-1, Q (B) = Cx (B) / Гтш( B).
Для оператора B можно ввести оператор B' = r(B) ■ B. Определив в задаче Z = (I0, Sq) элементы матрицы оценок в виде B'(Z) = || rj ||q X i, получим rj (B) = r(B) ■ rjB).
В[1] доказана
Лемма 1. Если (и, V) отмечена в В, то имеем Г'у (В) > 1; если (и, V) не отмечена в В, то имеем Г'у (В) < б(В) < 1.
Тогда, учитывая, что матрица оценок В'(2) получается из В(7) поэлементным умножением, получаем, что пара (и, V) является отмеченной в В' тогда и только тогда, когда она отмечена в В.
Будем рассматривать множество операторов {Лк : Лк = Вк ■ С, к = 1, п }, где каждый оператор
Вк дает матрицу оценок Вк(7) = ||Г^ ||г х ¡. Предположим, что для исходного набора операторов уже выполнено описанное выше преобразование, т.е. для каждого оператора Вк выполняется такое свойство:
если (и, V) отмечена в Вк, то Г^ > 1, иначе ГиУ < 1. (2)
Система {Вк} называется базисной для 2, если М, = ^ _М(Вк).
к =1, п
Тогда, по теореме 1 из [1], существует такой набор степеней {хк, к = 1, п }, что для базисной системы {Вк}, удовлетворяющей свойству (2), алгоритм
Л = | £ Вкк I С(с„ С2) (3)
к =1, п
является корректным для задачи 2.
Для того чтобы алгоритм удовлетворял условию корректности, для набора {хк} должны выполняться следующие условия:
1) для любой пары (и, V) е М0 выполняется неравенство Гиу. = = 1 (ГГ) к <
2) для любой пары (и, V) е М1 выполняется неравенство Гиу. = = 1 (Г^) к > с2.
Пользуясь введенными обозначениями, можно сформулировать оптимизационную задачу нахождения степеней операторов {Вк} в алгоритме Л из формулы (3) так, чтобы степень алгоритма была минимальной:
V(u, v) е M0 : £(r"kv)Хк < cl5
к = 1 n
V(u, v) е Mi : £(ГГ)Хк > c2, (4)
к = 1
max xk —min.
к = lTn
В задаче (4) имеются n переменных и q х l ограничений.
X uv
Введем следующие обозначения: yk = e x, уu = ln r"kv, 9uv( y) = ^П = 1 У к . Тогда задача (4) примет следующий вид:
V( u, v) е Mo : (y )< сь
V(u, v) е Mi : 9uv(y) > ¿2, (5)
max yk —► min.
к = 17n
Используя ограничение сверху степени алгоритма, приведенное в формуле (1), можно утверждать, что для всякого решения y оптимизационной задачи (5) выполняются неравенства
yi < M, i = 1, n,
n
1426 РОМАНОВ
где в качестве M можно взять, например,
M = exp ([\0g2ql ]).
Тогда решение задачи не изменится, если к множеству ограничений добавить условияy, <M, i = 1, n. При этом множество ограничений запишется в виде
U = {y : V(u, v) e M0 : quv(y)< Ci; V(u, v)e Mi : ф"v(y)> C2; y, <M, i = 1, n}. Таким образом, задача (5) эквивалентна задаче
R = {y e U, max yk —► min }.
k = lTn
Рассмотрим для каждого непустого множества индексов
I = {i 1, i'2, ..., im }с{ 1, 2, ..., n }
вспомогательную задачу
ri = {y e U, yh = • •• = ylm, y,^^ min }.
Обозначим переменные у, , ..., y,m через z1, а переменныеy, i e {1, ..., n}\I, - через z2,z3, ..., zn- m + 1. Тогда задача RI может быть записана в виде
RI = {z e UI, z1 —► min }.
Здесь, вводя ф" v (z) равным значению ф^ от соответствующего y, полагаем
Uj = {z : V(u, v) e M0 : ф"v(z) < c1; V(u, v) e M1 : ф"v(z) > c2; zt < M}.
Таким образом, из исходной задачи получен набор из 2n - 1 вспомогательных задач. К их решению применимы такие методы, как метод множителей Лагранжа, метод проекции градиента и метод линеаризации (см. [5]).
В частности, если для метода линеаризации представить UI в виде UI = {z : yuv(z) < 0, u = 1, q, v = 1, l; z, <M, i = 1, n - m +1}, где
[ф/v(z) - C1 при (u, v) e Mo, Vu v(z) = \ u v _
L-ф" v(z) + c2 при (u, v) e M1,
то получим последовательность оптимизационных задач вида
Vuv(~zk) + <Vuv(zk), (z- ~zk)>< 0, u = 1, q, v = 1, l,
0 < гг < M, / = 1, и - га + 1,
1z- zk| 2 + ßk(Zi — z1 ) — min.
В результате образуется последовательность задач с линейными ограничениями и квадратичным функционалом. При этом (k + 1)-е приближение zk +1 выбирается как решение k-й оптимизационной задачи. Так как функция yuv является полиномом, то ее производная выписывается аналитически.
В результате для каждого набора индексов I получаем решение Zj задачи RI и, соответственно, набор yI, являющийся решением задачи RI.
Теорема. Существует I такое, что yI является решением задачи R.
Доказательство. Пусть y - решение задачи R, причем max yk = y. Пусть I = {i : y, = y, i = 1, n }.
k = ГГп
Тогда y удовлетворяет ограничениям задачи Rj и условию max yk = y. —► min на U. Следователь-
k = ГГП
но, y является решением задачи Rj.
Из доказательства следует, что кандидатами на решение задачи R могут быть только те решения задач Rj, для которых max (yj)k = (yj, т.е. максимальными компонентами являются
k = ГТп
именно те, которые отобраны в набор I. Таким образом, достаточно среди полученных кандидатов выбрать то решение, для которого (yj), принимает минимальное значение. Полученный
вектор будет давать решение задачи (5), и из него обратной подстановкой переменных легко получить решение исходн
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.