_учебник_ Журавлёв Ю.И. Математические основы теории пронозирования (2008) (1185334), страница 6
Текст из файла (страница 6)
для каждой пары S u , S v контрольных объектов, S u = (bu1 . . . bun ), S v = (bv1 . . . bvn )найдется Sr ∈ I, Sr = (ar1 . . . arl ) и признак k, 1 ≤ k ≤ n, r = r(u, v), k = k(u, v)такие, чтоρk (ark , buk ) 6= ρk (ark , bvk )27Лекция 55.1Построение алгоритмов распознавания, корректныхдля заданной контрольной выборкиРассматривается задача распознавания (или прогноза) со стандартной обучающей информацией:I0 = {S1 , . .
. , Sm , α̃(S1 ), . . . , α̃(Sm )},Si = (ai1 , . . . , ain ),i = 1, 2, . . . , m,aij ∈ Mj ,j = 1, 2, . . . , n.Здесь S1 , . . . , Sm — описания объектов, составляющих обучающий материал,α̃(Si ), i = 1, 2, . . . , m, — информационные векторы объектов Si по свойствам Pj ≡ Si ∈ Kj .Другими словами, если α(Si ) = (αi1 , . . .
, αij , αil ), j = 1, 2, . . . , l, то(1, Si ∈ Kj ,αij =¯ Kj .0, Si ∈Задача распознавания Z определяется начальной информацией I0 и конечной выборкойS̃ = (S 1 , . . . , S q ), S i = (bi1 , . . . , bin ), i = 1, 2, . . . , q, т.е. Z = {I0 , S̃ q }.Требуется для каждого объекта S i из S̃ q вычислить его информационный вектор β̃(S i )или, что то же самое, значение свойства Pj (S i ) ≡ S i ∈ Kj , j = 1, 2, . . . , l.Далее будем считать, что информационные векторы для S̃ q известны, и, основываясьна этом, строить алгоритм, который правильно вычисляет эти свойства.qI.
Пусть дано множество {A}, вообще говоря, некорректных алгоритмов для решениязадач распознавания, представленных в виде A = B · C, где B — распознающийоператор, C - решающее правило. Напомним, что B(I0 , S q ) = kΓij kq×l . Здесь Γij —действительные числа, C(kΓij k)q×l = kβij kq×l ; βij ∈ {0, 1, ∆}, βij = ∆ означает, чтоалгоритм A отказался от вычисления свойства Pj (S i ); βij = β, β ∈ {0, 1}, означает, что алгоритм A вычислил свойство Pj (S i ) равным β.
При этом мы допускаемвозможность ошибки.Известно, что каждый алгоритм A может быть представлен в виде B · C и что поисходному семейству {A} с помощью операций сложения, умножения и умноженияна скаляр можно построить алгебраическое расширениеU{A} = U{B} · {C}класса алгоритмов {A} и алгебраические расширения конечных степеней28Uk {A} = Uk {B} · {C}.При выполнении некоторых условий для задачи Z и исходного семейства {A} в расширении Uk {A} можно построить алгоритм A∗ , правильно вычисляющий все значения Pj (S i ), i = 1, 2, . . . , q, j = 1, 2, .
. . , l. Если в качестве исходного семейства {A}рассмотреть класс алгоритмов вычисления оценок, то искомый алгоритм A∗ представим в виде"∗A = (c1 + c2 )qlXX#kβij (Bij )C(c1 , c2 ),i=1 j=1где c1 , c2 — параметры решающего правила C,βij Pj (S i ),i = 1, 2, . . . , q,j = 1, 2, . . . , l,Bij = Bj + Bij ,Bj = Bj1 + . . . + Bj,j−1 + Bj,j+1 + . . . + Bjl ,jjjjBij = Bi1+ . . . + Bi,i−1+ Bi,i+1+ .
. . + Biq;здесь каждый оператор Bij является оператором вычисления оценок, каждый опеjратор Bivявляется либо оператором вычисления оценок, либо разностью двух операторов вычисления оценок. Для величины k также имеется формула, приводитькоторую здесь нет необходимости.Каждый оператор вычисления оценок кодируется значениями 2n + 3m + 3 параметров, где n — число признаков, описывающих объекты, m — число объектов в I0 .Нетрудно также видеть, что приведенная выше формула для алгоритма A∗ включает в себя по крайней мере l(l − 1) + lq(q − 1) операторов вычисления оценок.Следовательно, для полной записи кода алгоритма A∗ требуется по крайней мере(2n + m + 3)l[(l − 1) + q(q − 1)] чисел.
Указанная величина может быть несколькоуменьшена с помощью специальных приемов, однако она все-таки остается большой,и это неудобно при машинной реализации алгоритма, если величины n, m, l, q велики. Поэтому при реальном синтезе корректного алгоритма A∗ будет использоватьсятолько его принципиальная запись, данная выше, а реализация операторов типа Bijбудет проводиться другими методами. В дальнейшем будут использоваться толькопороговые решающие правила C(c1 , c2 ): C(kΓij kq×l ) = kC(Γij )kq×l ,1, Γij > c2 ,C(Γij ) = 0, Γij < c1 ,0 < c1 < c2 .∆, c1 ≤ Γij ≤ c2II.
Рассмотрим информационную матрицу kβij kq×l выборки S̃ q в задаче Z. ПоложимM = {(i, j)},i = 1, 2, . . . , q,j = 1, 2, . . . , l,Mα = {(i, j)} : βij = α,α = 0, 1.29Очевидно, M = M0 ∪ M1 .Пусть B — распознающий оператор иB(Z) = kΓrt (B)kq×l ,где Γrt — действительные числа.Определение 1 Оператор B называется допустимым для задачи Z, если существует хотя бы одна пара (u, v) из M1 такая, что для всех (i, j) из M0Γuv (B) > |Γij (B)|.Пара (u, v) называется в этом случае отмеченной в B.
Совокупность всех пар, отмеченных в B, обозначим через M (B).ПустьΓ0max (B) = max |Γij (B)|,(i,j)∈M0Γ1min (B)=min(i,j)∈M (B)Γij (B).ПоложимΓ(B) = [Γ1min (B)]−1 .(5.1)По оператору B построим оператор B 0 :B 0 = Γ(B) · (B).(5.2)Пусть B 0 (Z) = kΓ0ij kq×l . Тогда из (5.2) легко следует, чтоΓ0ij = Γ(B) · Γij (B).(5.3)Лемма 1 Если (u, v) отмечена в B, то Γ0uv (B) ≥ 1; если (u, v) не отмечена в B,тоΓ0uv (B) ≤Γ0max (B)= Γ(B) < 1.Γ1min (B)Доказательство.
Если (u, v) отмечена в B, то для Γuv (B) выполнено неравенствоΓuv (B) ≥min(i,j)∈M (B)Γij (B) = Γ1min (B).Из этого неравенства и соотношений (5.1)-(5.3) легко следует первое утверждениелеммы.Если пара (u, v) не является отмеченной в B, то30|Γuv (B)| ≤ max Γij (B) = Γ0max <(i,j)∈M0min(i,j)∈M (B)Γij (B) = Γ1min (B).Из последних неравенств и соотношений (5.1)-(5.3) легко следует второе утверждениелеммы.В дальнейшем положимΓ0max (B)/Γ1min (B) = Q(B).Пусть {B} — произвольная конечная система распознающих операторов.Определение 2 Система {B} называется базисной для Z, если[M1 =M (B).B∈{B}По базисной для Z системе {B} построим алгоритм A∗ , корректный для задачи Z.Введем для операторов B 0 , B 0 = Γ(B) · B, B ∈ {B} целые числа k(B 0 ) так, чтобывыполнялось неравенствоc1.(c1 + c2 )|{B}|0[Q(B)]k(B ) <(5.4)Для этого достаточно положитьk(B 0 ) =ln (c1 + c2 ) + ln |{B}| − ln c1+ 1.| ln Q(B)|Очевидно, что в этом случае неравенство (5.4) выполнено.
Напомним, что величиныc1 , c2 суть пороги решающего правила C(c1 , c2 ).Теорема 5 АлгоритмA=(c1 + c2 )X0(B 0 )k(B )· C(c1 , c2 )B∈{B}является корректным для Z.Доказательство. Распознающим оператором B ∗ в алгоритме A∗ является операторX(c1 + c2 )0(B 0 )k(B ) .B∈{B}Пусть B ∗ (Z) = kΓ∗ij kq×l . ТогдаXΓ∗ij = (c1 + c2 )B∈{B}310(Γ0ij (B))k(B ) .Случай 1. Pj (S i ) = βij = 1, 1 ≤ i ≤ q, 1 ≤ j ≤ l,Γ∗ij = (c1 + c2 ) X0X(Γ0ij (B))k(B ) +0(Γ0ij (B))k(B ) .¯ B(i,j)B∈B∈B(i,j)Здесь B(i, j) — совокупность всех операторов из {B}, в которых пара (i, j) являетсяотмеченной.
Так как {B} — базисная система для Z, то множество B(i, j) непусто.ПоэтомуX0(Γ0ij (B))k(B ) ≥ 1,(5.5)B∈B(i,j) Xc10)0k(B < |{B}|(Γ(B)).ij(c1 + c2 )|{B}|B ∈¯ B(i,j)(5.6)Неравенство (5.5) следует из определения отмеченной пары, неравенство (5.6) — из(5.4). Окончательно получаемΓ∗ijc1> (c1 + c2 ) 1 −c1 + c2= c2 .Но тогда из определения порогового решающего правила следует C(Γ∗ij ) = 1 = βij == pj (S j ).Случай 2. pj (S i ) = βij = 0, 0 ≤ i ≤ q, 1 ≤ j ≤ l. В этом случае пара (i, j) не являетсяотмеченной ни в одном операторе B. ПоэтомуΓ∗ij = (c1 + c2 )X0(Γ0ij (B))k(B ) < (c1 + c2 )|{B}| ׯ B(i,j)B∈c1= c1 .(c1 + c2 )|{B}|Из определения C(c1 , c2 ) следуетC(Γ∗ij ) = 0 = βij = Pj (S i ).Теорема доказана.Определение 3 Базисная система {B} называется неприводимой для Z, если никакая собственная часть {B} не является базисной для Z.Очевидно,|{B}| ≤ |M1 | ≤ q × l.Поэтому неравенство (5.4) для неприводимых систем записывается в виде0Q(B)k(B ) <32c1.(c1 + c2 )|M1 |Этому неравенству удовлетворяетk(B 0 ) =ln |M1 | + ln (c1 + c2 ) − ln c1+ 1.ln Q(B)Формулировка теоремы 1 при новых k(B 0 ) сохранится без изменений.Из теоремы 1 следует, что для построения эффективного корректного алгоритмадостаточно построить систему из небольшого числа просто выполняемых распознающих операторов B, базисную для Z.
Из базисной системы затем нетрудно получитьнеприводимую систему. Для построения базисной системы подходит любой оператор,отмечающий непустое множество пар (i, j) таких, что βij = 1. В [X] для любой задачиZ = {I0 , S̃ q }, I0 = {S1 , . . . , Sm , α̃(S1 ), . . . , α̃(Sm )}, в которой объекты из S̃ q попарнонеизоморфны относительно I0 и информационная матрица kαij km×l в I0 состоит изпопарно различны столбцов, указана базисная система из |M1 | операторов. Каждыйоператор этой базисной системы гарантирует отметку, вообще говоря, ровно однойпары (i, j), βij = 1. Можно указать случаи, когда один оператор гарантирует отметку существенно большего числа пар. Это возможно и для простых распознающихоператоров.33Литература[1] Труды Мат. ин-та им.
В.А.Стеклова, том 51, 1958 г.[2] Ю.И. Журавлев. Избранные научные труды. Москва, из-во Магистр, 1996 г.,стр. 378–384[3] Ю.И. Журавлев, И.В. Исаев. Построение алгоритмов распознавания, корректных длязаданной контрольной выборки. Журнал вычислительной математики и математической физики, том 19. №3, 1979 г.34.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
