Ю.И. Журавлёв - Математические основы теории прогнозирования (курс лекций) (1162168), страница 5
Текст из файла (страница 5)
+·+ ...+k−10k−21k−1−rr + −|M | − 1|M |+·.k−1−ννВсе t из M + имеют одинаковый только что выписанный коэффициент при Pt . Остальные случаи вычисляются так же просто.213. В качестве опорных рассматриваются все непустые подмножества множества {1, 2, . . .
, n}.Тогда( +2|M |−1 , для t ∈ M +R(N = 1, t) =0,для t ∈ M − .( +−2|M |−1 · (2|M | − 1), для t ∈ M +R(N = 0, t) =2n−1 ,для t ∈ M − .Подставляя полученные значения в (3.2), получаемwix11 ·Xwt|M + |−1·2+ x10t∈M +Xwt · (2|M+ |−1) · (2|M−|− 1)+t∈M +!!X n−1+wt · 2t∈M −Аналогичный вид принимает после соответствующих подстановок формула (3.3).4. Совокупность характеристических векторов опорных множеств образует интервал вE n , т.е.
удовлетворяет условию: K = 1, K — элементарная конъюнкция. Не ограничивая общности, можно полагатьK = x1 · . . . · xr · xr+1 · . . . · xr+k .Тогда в систему опорных множеств не войдут признаки 1, . . . , r; в каждое из опорныхмножеств войдут признаки r + 1, . . . , r + k, и к ним последовательно присоединятсявсе подмножества (включая пустое, если K =6 0) или все непустые подмножествамножества r + k + 1, .
. . , n, если K = 0. Будем рассматривать K 6= 0 и рассмотримфункцию близости с параметрами 1 , . . . , n .Если не выполнено включение {r + 1, . . . , r + k} ⊆ M + , то R(N = 1, t) = 0,R(N = 0, t) = 2n−(r+k+1) . Последнее следует из того, что |{Ω}A | = 2n−(r+k) , и хотя бы один из признаков любого опорного подмножества принадлежит M − .Пусть имеет место: {r + 1, . . . , r + k} ⊆ M + . Тогда для t ∈ {r + 1, .
. . , r + k}:R(N = 1, t) = 2|M+ |−k|M − |R(N = 0, t) = 2,− 1.Для t ∈ M + \{r + 1, . . . , r + k}:R(N = 1, t) = 2|M+ |−k−1R(N = 0, t) = 2|M+ |−k−1,· (2n−(k+r) − 1).Наконец, для t ∈ M − : R(N = 1, t) = 0, R(N = 0, t) = 2|M− |−1.После соответствующих подстановок, получаем эффективные формулы вычисленияΓj (S), j = 1, . . . , l.Последний случай (4) можно использовать при решении прикладных задач. Рассмотрим булевскую функцию, равную 1 на элементах {ω̃}A . Если реализовать ееrWдизъюнктивной нормальной формойKi , где Ki — элементарные конъюнкции, иi=122TNKu NKv = ∅, то, написав по 4 формулы для каждой Ki и сложив их, получим формулу для вычисления Γj (S), j = 1, .
. . , l. Достаточно и реализации в классе д.н.ф., вкоторых интервалы некоторых пар конъюнкций пересекаются (интервалы конъюнкций из разных пар не пересекаются). Пусть оценка по системе опорныхS множеств, задаваемых конъюнкцией K, есть Γj (K, S). Пусть, также, {ω̃}A = K1 K2 , K1 · K2 6≡ 0.Тогда, очевидно, Γj (S) = Γj (S, K1 ) + Γj (S, K2 ) − Γj (S, K1 · K2 ).23Лекция 44.1Вычисление характеристик, определяющих алгоритмвычисления оценокКак было показано в лекции 3, алгоритм распознавания определяется заданием системы опорных множеств {Ω}A и числовых параметров 1 , .
. . , n , w1 , . . . , wn , w1 , . . . , wm , x11 ,x00 , x01 , x10 , c1 , c2 .В своей работе алгоритм использует исходную (обучающую) информацию, состоящуюиз таблицы обучения kaij km×n и ее информационной матрицы kαij km×l . Рассматриваетсязадача с l, вообще говоря, пересекающимися классами K1 , . . . , Kl .Параметры подбираются таким образом, чтобы обеспечить максимальную точностьраспознавания на определенном заранее множестве объектов.I. Текущий контроль.
Из исходной матрицы последовательно изымаются строки Si ,i = 1 . . . m, вместе с информационным вектором α̃(Si ), и для строки Si по оставшейсяисходной информации строится квази-информационный вектор β̃(Si ) = (βi1 . . . βil ),i = 1...mВ матрице kαij −̇βij km×l определяется число единиц. Операция αij −̇βij определяетсяследующим образом:HHijαij HβHH0101∆011011Алгоритм A подбирается таким образом, чтобы число единиц (т.е. сумма ошибок иотказов) была бы минимальной.II. Независимый контроль.
формируется контрольное множество S 1 , . . . , S q ,Si = (bi1 . . . bin ), i = 1 . . . q и таблицы информационных векторов kβij kq×l . С использованием алгоритма A и всей исходной информации формируется совокупностьγ̃ = (γi1 . . . γil ) квази-информационных векторов и минимизируется число единиц вматрице kβij −̇γij kq×l .1) Система опорных множеств определяется (задается) экспертами и последовательно рассматриваются алгоритмы в набором всех k-элементарных√ подмножеств: k = 2, 3, . . . , r. Как правило, достаточно ограничиться r ≤ 3 n.2) Параметры xij определяются перебором вариантов. Как правило, рассматриваются целочисленные значения x11 = 1, 2, 3, 4, 5, 6, 7; x00 ≤ [ 21 x11 ], x01 , x10 принимают отрицательные или нулевые значения.
В большинстве действующих систем полагают: x11 = 1, x00 = x01 = x10 = 0.243) Пусть определены все характеристики за исключением 1 , . . . , n (о них позднее).Рассмотрим задачу с независимым контролем и напишем систему неравенствΓj (S i ) > c2 , ∀βij = 1Γj (S i ) < c1 , ∀βij = 0i = 1, 2, . . . , q, j = 1, . . . , l(4.1)В левой части системы неравенств (4.1) находятся билинейные формыΣwu · wv . Полагаем w1 = . . . = wn = 1. Получаем систему линейных относительно w1 . . . wq неравенств. Находим максимальную совместную подсистему иее решение w11 , .
. . , w1q . Подставляем эти значения в левую часть (4.1) и получаемлинейную относительно w1 , . . . , wn систему. Находим совместную максимальнуюподсистему и ее решение w11 , . . . , wn1 . Подставляем эти значения левую часть(4.1) и т.д. Процесс заканчивается либо когда удастся получить наборы параметров, удовлетворяющие всем неравенствам (4.1), либо когда после очереднойитерации число неравенств в совместной подсистеме уменьшится.4) Для определения 1 , .
. . , n существует большое число эвристических методов.Приведем один из них (может быть, не лучший). Оставим в таблице обученияи контроля только k-е столбцы: b1ka1k a2k b2k .. , .. . . amkblkДля каждой пары (aik bjk ) вычислим k(α̃(Si ) + β̃(S j ))mod2 k, то есть число различных координат в этом векторе.Если l − kα̃(Si ) + β̃(S j )k > kα̃(Si ) + β̃(S j )k, то формируем неравенство|aik − bjk | < kПри изменении знака:|aik − bjk | > k .При l − kα̃(Si ) + β̃(S j )k = kα̃(Si ) + β̃(S j )k выписываем одно из неравенств|aik − bjk | ≤ k ,|aik − bjk | ≥ k .Значение k находится из условия: данное значение удовлетворяет наибольшемучислу построенных неравенств.254.2Алгебры над алгоритмамиРанее мы видели, что алгоритм вычисления оценок делится на две части: распознающий оператор B и решающее правило C: A = B · C. A(I, S) = (Γ1 (S), .
. . , Γl (S)) = Γ~l (S),C(Γ~l (S)) = (C(Γ1 (S)), . . . , C(Γl (S)))1, Γj (S) > c2C(Γj (S)) = 0, Γj (S) < c1c1 < c2∆, c1 ≤ Γj (S) ≤ c2Оказывается, что подобное представление имеет место для большого класса алгоритмов.Пусть A — алгоритм, работающий с исходной информацией I ∈ {I}, A ∈ {A}, и каждыйиз A по любой I ∈ {I} должен получить ответ на фиксированные вопросы Q1 , .
. . Ql ,причем число возможных ответов равно трем: 1, 0, ∆. ТогдаТеорема 4 Каждый A может быть представлен в виде A = B·C, B(I) = (a1 . . . aj . . . al )— числовой вектор ~a, C(~a) = (C(a1 ), . . . , C(al )), причем1, ai > c2C(ai ) = 0, ai < c1∆, c1 ≤ ai ≤ c2где c1 и c2 — константы, фиксированные для всех алгоритмов. Заметим, чтоA(I) = (C(a1 ), .
. . , C(al )) = (δ1 . . . δl ) = ~δДоказательство. Введем вспомогательный оператор C −1 (~δ) = (C −1 (δ1 ) . . . C −1 (δl )) == (a1 , . . . , al ) = ã. Тогда B = A · C −1 , A = (A · C −1 ) · C. Теорема доказана.Класс алгоритмов {A} порождает класс операторов {B}, которые можно складывать,умножать, умножать на число.Действительно, если B1 (I) = (a11 . . .
a1l ), B2 (I) = (a21 . . . a2l ), то (B1 + B2 )(I) = (a11 ++ a21 , . . . , a1l + a2l ), B1 · B2 (I) = (a11 · a21 , . . . , a1l · a2l ), (d · B1 )(I) = (d · a11 , . . . , d · a1l ).Нетрудно видеть, что используя операторы из {B}, A = B · C, можно построить полиномыB̃ = Σci1 ...ik · Bir11 · . . . · Birkk ,где роль переменных играют операторы; ci1 ...ik — константы.Совокупность {B̃} называют алгебраическим замыканием семейства {B}, а {B̃} · C —алгебраическим замыканием класса алгоритмов {A} — обозначения U{B}, U{A}.Оказывается (Ю. И. Журавлев), что в U{A} при выполнении простых легко проверяемых условий можно построить алгоритм, не делающий ошибок на контрольной совокупности.Алгоритм имеет вид:(d · Σ(ci Bi )ki ) · C.Bi представимы линейными формами от распознающих операторов вычисления оценок.Условия:Пусть I = {kaij km×n kαij km×l }.Контрольный материал: kbuv kq×n , kβij kq×l .261.
в матрице kαij km×l нет одинаковых столбцов.2. для каждой пары 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 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
