3.2 Вычисление значений поддержки с использованием региональных запросов
В этом разделе мы увидим, как быстро вычислить поддержку и доверие, используя региональные запросы. Техника, использованная здесь, в основном взята из Mander и Baeza-Yates [21]. Идея состоит в сведении поиска оптимального образца к рассмотрению прямоугольников со сторонами, параллельными осям, на двумерной плоскости рангов лексикографически упорядоченных суффиксов.
Пусть Ap1, Ap2, … , Apn – последовательность, полученная лексикографическим упорядочиванием всех суффиксов A. Здесь Ap – суффикс строки A, начинающийся в позиции p. Затем, сохраняем индексы p1,…,pn в массив suf: [1..n] ® [1..n] длины n в этом порядке, и определяем массив pos: [1..n] ® [1..n], как обратное отображение подстановки suf. Эти массивы называются суффиксными массивами (Gonnet, Baeza-Yates [14]; Manber, Myers [22]). По определению, suf(i) – позиция суффикса ранга i, pos(p) – ранг суффикса Ap.
Сначала, мы соблюдаем, чтобы для любой вершины v дерева TreeA, набор местонахождений слова Word(v) занимал смежный подинтервал I(v) = [x1..x2] в массиве suf.
Лемма 4. Подинтервалы I(v) для всех вершин v вычисляются за время O(n).
Доказательство. I(v) вычисляется проходом дерева TreeA, от листьев до корня, например поиском в глубину. Просматривая листья слева направо, полагаем I(vi) = [i..i] для i-го листа (i = 1,…,n). Затем, проходя дерево TreeA от листьев до корня, мы посещаем каждую вершину v с её детьми v1, …, vh и полагаем I(v) = [L..R], где L – левая граница интервала I(v1), R – правая граница интервала I(vh). ÿ
Далее, алгоритм строит из S и C диагональное множество ширины k, которое представляет собой множество помеченных точек на плоскости:
Diagk = { ( p, q; doc(p) ) | 1 £ p,q £ n, 0 £ (q-p) £ k, doc(p) = doc(q) }.
Затем алгоритм преобразует Diagk в следующее множество помеченных точек на плоскости:
Rankk = { (pos(p), pos(q); i) | (p, q; i) Î Diagk }
Для образца зависимых k-близких слов P = (a, k, b), мы рассмотрим двухмерный прямоугольный регион Rect(P) = I(a) x I(b) и определим count(Rect(P),Q) как число различных i таких что (x,y;i) Î Q Ç Rect(P) x [1..m], где Q – любое подмножество множества Rankk.
Лемма 5. Для любого образца зависимых k-близких слов P, верно count(P,S) = count(Rect(P), Rankk).
Из леммы 5 задача вычисления suppS(P) и confS(P) свелась к задаче вычисления count(Rect(P), Rankk). В [27] стандартными способами показывают верность следующей леммы.
Лемма 6. Пусть i - любое число, Q Í [1..l]2 x [1..m] – множество помеченных точек на плоскости и R[1..n]2 – любой прямоугольник. Тогда, count(R,Q) вычисляется за время O(m log2n) с использованием памяти O(mn log n) с временем предобработки O(n log n), где n – число точек в Q.
Теорема 1. Пусть (S, S, C, k, s) является примером задачи оптимизации доверия образца. Тогда алгоритм Find_Optimal, данный выше, находит все оптимизированные образцы в канонической форме с близостью k и порогом поддержки s за время O(mn2 log2n) с использованием памяти O( kmn log(n) ), где m = card(S) и n = size(S).
Доказательство. Сначала мы строим суффиксное дерево за линейное время с линейными расходами памяти. Затем, вычисляем интервалы I(v) для всех вершин v за время O(n) с использованием алгоритма динамического программирования (Preparata и Shamos 1985). Из леммы 1 и леммы 3, это достаточно для поиска самое большее O(n2) канонических образцов P = (Word(u), k, Word(v)), перечислением пар u, v вершин дерева TreeA. Затем, мы можем видеть из леммы 5 и леммы 6, что для каждого P мы вычисляем supp(P) и conf(P) за время O(knm log n) предобработки, используя O(kmn log n) памяти, время единичного запроса O(m log2n). Обратите внимание, что число Rankk самое большее kn. Поскольку число возможных шаблонов в канонической форме O(n2), утверждение доказано. ÿ
В этом разделе мы представляем модифицированную версию нашего алгоритма, которая выполняется за время O(max{k,m}n2) с использованием памяти O(kn). В этом алгоритме реализуется механизм регионального поиска непосредственно на суффиксном дереве, вместо запроса на региональном дереве, и вычисляем значения count(Rect(P),Rankk) методом динамического программирования, подобным изложенному в Maass [20].
Procedure Modified_Find_Optimal;
Вход: Выборка S = {s1,…,sm}, целевое условие C, близость k ³ 0 и Минимальная поддержка 0£s£1.
Выход: Оптимизированные образцы (a,k, b) в канонической форме.
Используемые структуры: приоритетная очередь Q.
begin
1 Q := Æ; A := s1$s2…sm, вычислить doc;
2 Построить суффиксное дерево TreeA и суффиксные массивы suf, pos;
3 Вычислить Diagk и Rankk.
4 for (каждой вершины u дерева TreeA, обходимых с листьев до корня) do
5 if (u – x-ый лист lx) then
6 B(lx) := { <y,z> | <x,y,z> Î Rankk, $y, $z};
7 If (u – интервальная вершина с детьми u1, …, uh) then
8 B(u) := B(u1) È … È B(uh), затем выбрасываем (discard) B(u1), …, B(uh);
9 for (каждой вершины v дерева TreeA, обходимого с листьев до корня) do
10 if (v – y-ый лист ly) then
11 С(ly) := {<z> | <y,z>Î B(u), $z };
12 if (v – интервальная вершина с детьми v1, …, vh) then
13 C(v) := C(v1) È … È B(vh), затем выбрасываем (discard) B(v1), …, B(vh);
14 P := (Word(u), k, Word(v) );
15 Вычислить count(P,S1) и count(P, S0) из C(v);
16 if (supp(P) ³ s) then
17 Добавить P в Q с ключом conf(P);
18 end for;
19 end for;
20 Вывести все образцы из Q.
end proc.
Каждая вершина v дерева TreeA имеет линейные списки B(v) и C(v). Элементами B(v) являются пары <y,z> Î [1..n] x [1..m] и сортируются по координате y. Аналогично, элементы C(v) метки <z> Î [1..m] сортируются по координате z. Для любого x Î [1..n], обозначим как lx x-ый лист.
Лемма 7. Предположим, алгоритм Modified_Find_Optimal посещает вершину u в цикле (строка 4), посещает вершину v в цикле (строка 9) и достигает строки 15. Тогда C(v) – упорядоченный список z, такой что (x,y;z) Î Rankk Ç Rect(P) x [1..m].
Доказательство. Доказывается индукцией по высоте вершин u и v подобным образом как в 4-ой лемме. ÿ
Теорема 2. Пусть (S, S, C, k, s) является примером задачи оптимизации доверия образца. Тогда алгоритм Modified_Find_Optimal находит все оптимальные образцы в канонической форме близости k и порогом поддержки s за время O(max{k,m}n2) с используемым объемом памяти O(kn), где m = card(S), n = size(S).
Доказательство. Утверждение следует из леммы 1, леммы 3, леммы 5 и леммы 7. Оцениваем время. Строка 1 – строка 3 расходует время O(n + kn). Поскольку дерево TreeA содержит O(n) вершин, внешний цикл (строка 4) выполняется за время O(n) и, таким образом, внутренний цикл (строка 9) выполняется за время O(n2). В каждом посещении вершины u во внешнем цикле каждая операция объединения (строка 8) занимает время O(kn) потому что длина получаемого списка B(u) очевидно ограничена числом kn = card(Rankk). Строка 6 алгоритма дает общее время O(kn) просмотра всех листьев. Аналогично, каждое посещение вершины v во внутреннем цикле, каждая операция объединения (строка 13) дает время O(hm) потому что каждый C(vi) отсортирован и его длина ограничена числом m, где р – число детей. Поскольку суммарное количество детей всех вершин O(n), амортизированное общее время строки 13 O(mn). Амортизированное время строки 11 O(kn) – просмотр всех листьев фиксированной вершины u. Объединяя эти наблюдения получаем, что полное время выполнения алгоритма T(n) = O(kn) + O(kn) + n * (O(kn) + O(mn) )= O(max{k,m}n2). ÿ
Известно, что высота суффиксного дерева O(log n) для случайных текстов сгенерированных равномерным распределением [7]. На основании теоремы 3 мы с высокой вероятностью ожидаем эффективного выполнения алгоритма за время O(kn log3n) для таких случайных текстов.
Теорема 3. Пусть (S, S, C, k, s) является примером задачи оптимизации доверия образца. Тогда существует алгоритм который вычисляет все оптимальные образцы в канонической форме близости k и порогом поддержки s за время O(kd2n log n ) используя O(kn) памяти, где n = size(S), d – высота суффиксного дерева.
Доказательство. Заметим, что каждый слой, набор вершин на одном уровне, суффиксного дерева содержит Т = kn элементов в B(u) (C(u)). В модифицированном алгоритме мы связываем с каждой вершиной указатель на её родителя и отсортированный список C(v) и B(u) точек <y,z> и <x,y,z>. Мы используем сбалансированные деревья для представления каждого списка C(v), так чтобы мы могли осуществить вставку элементов и подсчет положительно помеченных или отрицательно помеченных элементов за время log l для l = card(C(v)). Используя их, мы проходим уровни дерева (tree levelwise) от листьев до корня. Таким образом, в каждой вершине u со списком B(u), мы можем вычислить все C(v) за время O(dn0 log n0) (строка 10 – строка 17 алгоритма), где n0 = card(B(u)). Неоднократно повторяя это рассуждение, мы можем получить оценку O(kd2n log n). Мы опускаем детали. ÿ
5 Agnostic PAC-learning и минимизация эмпирической ошибки
Agnostic PAC-learning – обобщение хорошо знакомой в вычислительной теории обучения (computational learning theory) модели PAC – learning, которая предназначается для захвата изучаемых ситуаций из реального мира (intended to capture learning situation in real world) [16, 17, 20]. В модели Agnostic PAC-learning самообучающийся алгоритм может корректно работать с зашумленными средами, и даже имеют возможность аппроксимировать произвольное неизвестное распределение вероятности.
Haussler [16] и Kearns [17] показали близкую связь между Agnostic PAC-learning и задачей минимизации эмпирической ошибки, определенную выше. Величина Vapnik-Chervonenkis (VC-величина, VC-dimension) измеряет сложность класса понятий (concept class) (см. например [16,17]). Класс образцов зависимых k-близких слов, очевидно, имеет полиномиальную VC-величину для любого фиксированного неотрицательного k.