Тупиковые тесты

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: {{Задание|Mordasova|Константин Воронцов|15 февраля 2010}} [[Алгоритмы вычисления оценок|Алгоритм вычисления о...)
Текущая версия (15:32, 14 февраля 2010) (править) (отменить)
м (Формулировка задачи)
 
(31 промежуточная версия не показана)
Строка 1: Строка 1:
{{Задание|Mordasova|Константин Воронцов|15 февраля 2010}}
{{Задание|Mordasova|Константин Воронцов|15 февраля 2010}}
-
[[Алгоритмы вычисления оценок|Алгоритм вычисления оценки]], в котором множество опорных множеств является множеством всех '''тупиковых тестов''', называется тестовым алгоритмом. Первый вариант таких [[АВО]] был предложен [[Журавлёв, Юрий Иванович|Ю.И. Журавлевым]]. АВО совмещают метрические и логические принципы классификации. От метрических алгоритмов АВО наследует принцип оценивания сходства через введение ''множества метрик'' <tex>\rho_s(x, x′)</tex>, а от логических принцип поиска конъюнктивных закономерностей, конъюнкции строятся не над бинарными признаками <tex>\beta(x)</tex>, а над бинарными функциями близости вида <tex>\beta(x, x′) = \[\rho_s(x, x′) < \varepsilon_s\]</tex>. В этом случае каждой закономерности соответствует не подмножество признаков, а подмножество метрик, называемое ''опорным множеством''. Как правило одного опорного множества недостаточно, поэтому в АВО применяется взвешенное голосование по системе опорных множеств.
+
[[Алгоритмы вычисления оценок|Алгоритмы вычисления оценки]], в которых опорные множества являются '''тупиковыми тестами''', называются тестовыми алгоритмами. Первый вариант таких [[АВО]] был предложен [[Журавлёв, Юрий Иванович|Ю.И. Журавлевым]]. [[АВО]] совмещают метрические и логические принципы классификации. От [[Метрический классификатор|метрических алгоритмов]] [[АВО]] наследуют принцип оценивания сходства через введение ''множества метрик'' <tex>\rho_s(x, x')</tex>, а от логических принцип поиска конъюнктивных закономерностей, конъюнкции строятся не над бинарными признаками <tex>\beta(x)</tex>, а над бинарными функциями близости вида <tex>\beta(x, x') = \[\rho_s(x, x') < \varepsilon_s\]</tex>. В этом случае каждой закономерности соответствует не подмножество признаков, а подмножество метрик, называемое ''опорным множеством''. Как правило одного опорного множества недостаточно, поэтому в [[АВО]] применяется [[взвешенное голосование]] по системе опорных множеств.
==Описание АВО, основанных на тупиковых тестах==
==Описание АВО, основанных на тупиковых тестах==
 +
===Формулировка задачи===
 +
'''Задача распознавания:''' Дано <tex>\ Y=\bigcup_{i=1\ldots l}{Y_i}\ </tex> — множество непересекающихся классов объектов.<br />
-
'''Дано:''' <tex>Y=\bigcup_{i=1\ldots l}{Y_i}</tex>- множество непересекающихся классов объектов.<br />
+
Дана первоначальная информация <tex>I_0</tex> (обучающая) и описание некоторого объекта <tex>I(x)</tex>, <tex>x \in Y</tex>.<br />
-
Первоначальная информация <tex>I_0</tex> (обучающая) и описание некоторого объекта <tex>I(x)</tex>, <tex>x \in Y</tex>.<br />
+
Объект задается через набор числовых признаков <tex>X=(x_1,\ldots,x_n)</tex>.<br />
-
Объект задается через набор числовых признаков <tex>X=(x_1,\ldots,x_n)</tex>.</br>
+
Задача распознавания состоит в определении включения заданного объекта <tex>x</tex> в классы <tex>Y_i</tex>.<br />
Задача распознавания состоит в определении включения заданного объекта <tex>x</tex> в классы <tex>Y_i</tex>.<br />
В случае АВО, основанных на тупиковых тестах, начальная информация <tex>I_0</tex> задается таблицей:<br />
В случае АВО, основанных на тупиковых тестах, начальная информация <tex>I_0</tex> задается таблицей:<br />
-
*<tex>T_{nml}=\parallel a_{ij}\parallel_{m\times n}</tex>;
+
*<tex>T_{nml}=\parallel a_{ij}\parallel_{m\times n}</tex> - таблица признаков объектов в обучающей выборке;
-
*<tex>I(X_i)=(a_{i1},\ldots,a_{in})</tex>;
+
*<tex>I(X_i)=(a_{i1},\ldots,a_{in})</tex> - описание объекта из обучающей выборки;
-
*<tex>X_{m_{i-1}+1}, X_{m_{i-1}+2},\ldots,X_{m_i}\in K_i, i=1\ldots l, m_0=0, m_l=m</tex>;
+
*<tex>X_{m_{i-1}+1},\ X_{m_{i-1}+2},\ldots,\ X_{m_i}\in Y_i,\ i=1\ldots l,\ m_0=0,\ m_l=m</tex> - выражение, определяющее включение объектов в классы;
-
Алгоритм распознавания <tex>A(I_0,X)=\alpha(X)</tex>, где <tex>\alpha(X) = \alpha_1(I_0,X),\ldots ,\alpha_l(I_0,X)</tex>.<br />
+
'''Алгоритм распознавания'''<tex>A(I_0,X)=\alpha(X)</tex>, где <tex>\alpha(X) = \alpha_1(I_0,X),\ldots ,\alpha_l(I_0,X)</tex>.<br />
 +
<tex>
 +
\alpha_i(X) =
 +
\begin{cases}
 +
1, & X\in Y_i\\
 +
0, & X \notin Y_i \\
 +
\Delta, & \alpha\ \mathrm{doesn't\ accept\ X}.
 +
\end{cases}
 +
</tex>
 +
===Строение АВО===
 +
*<tex>\Omega=\{\omega|\omega \subseteq \{1, \ldots, n\}\}</tex> - ''система опорных множеств'';
-
\alpha_i(X) =
+
*Вводится ''функция близости'' для двух объектов по опорному множеству <tex>\omega</tex> :<br />
 +
<tex>
 +
B_\omega(X, X')=\bigwedge_{s \in \omega}{[\rho_s (X, X') \leq \varepsilon_s]}</tex>,
 +
где <tex>\varepsilon_s </tex> неотрицательные числа, называемые порогами, <tex>s=1,\ldots ,n </tex>;
 +
 
 +
*Вводится оценка близости объекта к классу <tex>\Gamma_c</tex>;
 +
 
 +
*Вычисление алгоритма проводится по правилу:<br />
 +
<tex>
 +
\alpha_j(I_0, X) =
\begin{cases}
\begin{cases}
-
1, & X\in K_i\\
+
1, & \Gamma_j(X)>\Gamma_i(X)+\delta_2;\ i=1,\ldots,l, \ i \neq j;\ \Gamma_j(X)>\delta_1\sum^{l}_{i=1}{\Gamma_j(X)};\\
-
0, & X \notin K_i \\
+
0, & \mathrm{other\ way}.
-
+
\end{cases}
\end{cases}
-
=
+
</tex><br />
 +
<tex>1>\delta_1\geq 1/l,\ \delta_2 \geq 0</tex> - ''пороги осторожности''.
 +
 
 +
===Строение АВО, основанного на тупиковых тестах===
 +
*Вводится система опорных множеств <tex>\Omega</tex>;
 +
 
 +
*Задается функция близости для двух объектов по опорному множеству <tex>\omega=\{j_1,\ldots, j_r\}</tex>:
 +
<tex>
 +
B_\omega(X_{i1}, X_{i2})=\bigwedge^{r}_{t=1}{\[|a_{i1j_t}-a_{i2j_t}| \leq \varepsilon_s\]}</tex>. Если <tex>B=0</tex>, объекты не являются близкими по опорному множеству.
 +
 
 +
==Тупиковые тесты==
 +
'''Тестом''' называется набор столбцов таблицы обучения <tex>T_{nml}</tex> с номерами <tex>j_1,\ldots,\j_r</tex>, если любые два объекта, принадлежащие разным классам <tex>Y_i</tex>, не являются близкими по опорному множеству <tex>\omega =\{j_1,\ldots,\j_r\}</tex>.
 +
'''Тупиковым тестом''' называется тест, у которого его собственное подмножество не является таковым. <br />
 +
Задача распознавания на основе тупиковых тестов решается следующим образом.
 +
Пусть <tex>\{T\}</tex> - множество тупиковых тестов таблицы <tex>T_{nml}</tex>. По тупиковому тесту<tex>j=(j_1,\ldots,j_k)</tex> выделяется подописание для распознаваемого объекта <tex>X=(a_{j_1},\ldots,a_{j_r})</tex>, а затем сравнивается со всеми подописаниями объектов таблицы. Число совпадений с описаниями объектов <tex>i</tex>-го класса обозначается через <tex>\Gamma_{ji}(T)</tex>.<br />
 +
''Оценка объекта по <tex>i</tex>-ому классу'' <tex>\Gamma_{ji}(X) = \Gamma_i(X_j)=\frac{1}{m_j-m_{j-1}}\sum_{T \in\{T\}}{\Gamma_{ji}(T)}</tex>.
 +
 
 +
Далее объект относится к тому классу,по которому он получил максимальную оценку, в случае двух максимумов считается, что объект не классифицируется на заданном тесте.<br />
 +
 
 +
Если считать, что не все признаки, описывающие объект, равнозначны, то они снабжаются числовыми весами <tex>p(j)=\frac{\tau_j(n,m)}{\tau(n,m)}</tex>, где <tex>\tau</tex> - число тупиковых тестов в таблице, <tex>\tau_j</tex> -число тупиковых тестов в таблице, содержащих <tex>j</tex>-ый столбец. Чем больше вес, тем важнее признак в описании объектов множества.
 +
Весами объектов, составляющих таблицу обучения, называется поощрительная величина <tex>\gamma</tex>. В случае совпадения распознаваемого объекта <tex>X</tex> с объектом из таблицы <tex>X_v \in Y_i</tex>, такое совпадение поощряется: <tex>\Gamma_T(X,X_v) = \gamma(X_v)(p(j_1),\ldots,p(j_r))</tex>,
 +
Оценка объекта по <tex>i</tex>-ому классу задается таким образом
 +
<tex>\Gamma_i(X)=\frac{1}{m_i-m_i-1}\sum_{T\in\{T\}}\sum^{m_i}_{m_{i-1}+1}{\Gamma_T(X_v,X)}</tex>.
 +
===Построение тупиковых тестов===
 +
Процесс построения всех тупиковых тестов очень трудоемкий, так как зачастую приходится использовать метод перебора. Для решения задач большой размерности применяются стохастические методы. Для обработки таблиц с относительно большим числом строк по сравнению с числом столбцов может применяться следующий метод. <br />
 +
 
 +
*Пусть <tex>i_1,i_2 \in(1,\ldots,m)</tex>.
 +
Паре объектов <tex>S_{i_1}</tex> и <tex>S_{i_2}</tex> ставится в соответствие строка <tex>I(X_{i_1})\oplus I(X_{i_2})=(a_{i_11}\oplus a_{i_21}, \dots, a_{i_1n}\oplus a_{i_1n})</tex>, если :<br />
 +
<tex>
 +
a_{i_1j}\oplus a_{i_2j} =
\begin{cases}
\begin{cases}
-
n/2, & \mbox{if }n\mbox{ is even} \\
+
0, & |a_{i_1j}-a_{i_2j}|\leq \varepsilon_j\\
-
3n+1, & \mbox{if }n\mbox{ is odd}
+
1, & \mathrm{other\ way}.
\end{cases}
\end{cases}
 +
</tex><br />
 +
*Составим булеву матрицу <tex>L_{nml}</tex> из всех таких строк для объектов из разных классов.
 +
* <tex>U_i</tex> - совокупность всех подмножеств множества <tex>\{1,2,\ldots,h\}</tex> мощности <tex>i</tex>, где <tex>i</tex> - выбранное число из этого множества. <tex>h</tex> - число строк в матрице <tex>L_{nml}</tex>. Элементы множества <tex>U_i</tex> называются наборами.
 +
*Алгоритм построения тупиковых тестов:
 +
#Пусть <tex>i=h, \ U_i=\{1,2,\ldots,h\}</tex>, задача построения множества всех тупиковых тестов таблицы <tex>T_{nml}</tex> сводится к построению множества всех неприводимых покрытий матрицы <tex>L_{nml}</tex>. В этом случае используется детерминированный алгоритм.
 +
#Пусть <tex>i<h</tex>.
 +
##Случайным образом выбираем набор <tex>u=\{i_1,\ldots,\i_r\} \in U_i</tex>, определяющий подматрицу <tex>L^u_{nml}</tex>, образованную строками с номерами <tex>i_1,\ldots,i_r</tex>.<br />
 +
##Тест таблицы <tex>T_{nml}</tex>, состоящий из столбцов <tex>j_1,\ldots,j_r</tex> называется ''u-тестом'', если набор столбцов матрицы <tex>L^u_{nml}</tex> с теми же номерами является неприводимым покрытием. <tex>\mathcal{T}(T_{nml},u)</tex> - множество всех u-тестов в таблице <tex>T_{nml}</tex>.
 +
##Каждому неприводимому покрытию матрицы <tex>L_{nml}</tex> соответствует набор столбцов таблицы <tex>T_{nml}</tex>, который проверяется на тестовость.
 +
##Обработка последовательности <tex>u_1,\ldots,u_v</tex> приводит к построению случайной выборки <tex>\mathcal{T}'(T_{nml})=\bigcup^{v}_{t=1}{\mathcal{T}(T_{nml},u_t)}</tex>. В этом случае используется стохастический способ построения тупиковых тестов.
 +
'''Замечание:''' Требуемая точность алгоритмов зависит от выбора параметров <tex>i</tex> и <tex>v</tex>. При определенных условия выбора этих величин стохастический алгоритм почти всегда совпадает с детерминированным, <tex>i=\log^{\gamma}_2 n, \ \gamma >3</tex>. для решения практических задач достаточно выбрать <tex>i=\log_2 n,\ v=20</tex>.
 +
 +
==Литература==
 +
#''К.В. Воронцов'', [[Машинное обучение (курс лекций, К.В.Воронцов)|Машинное обучение (курс лекций)]].
 +
#{{книга
 +
|автор = Журавлев Ю. И.
 +
|часть = Об алгебраических методах в задачах распознавания и классификации
 +
|заглавие = Распознавание, классификация, прогноз
 +
|год = 1988
 +
|том = 1
 +
|страницы = 9--16
 +
|ссылка = http://www.ccas.ru/frc/papers/zhuravlev88rkp.pdf
 +
}}
 +
#{{книга
 +
|автор = Бушманов О. Н., Дюкова Е. В., Журавлев Ю. И., Кочетков Д. В., Рязанов В. В.
 +
|часть = Система анализа и распознавания образов
 +
|заглавие = Распознавание, классификация, прогноз
 +
|год = 1989
 +
|место = М.
 +
|издательство = Наука
 +
|том = 2
 +
|страницы = 250–273
 +
|ссылка = http://www.ccas.ru/frc/papers/bushmanov89obraz.pdf
 +
}}

Текущая версия

Данная статья является непроверенным учебным заданием.
Студент: Участник:Mordasova
Преподаватель: Участник:Константин Воронцов
Срок: 15 февраля 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Алгоритмы вычисления оценки, в которых опорные множества являются тупиковыми тестами, называются тестовыми алгоритмами. Первый вариант таких АВО был предложен Ю.И. Журавлевым. АВО совмещают метрические и логические принципы классификации. От метрических алгоритмов АВО наследуют принцип оценивания сходства через введение множества метрик \rho_s(x, x'), а от логических принцип поиска конъюнктивных закономерностей, конъюнкции строятся не над бинарными признаками \beta(x), а над бинарными функциями близости вида \beta(x, x') = \[\rho_s(x, x') < \varepsilon_s\]. В этом случае каждой закономерности соответствует не подмножество признаков, а подмножество метрик, называемое опорным множеством. Как правило одного опорного множества недостаточно, поэтому в АВО применяется взвешенное голосование по системе опорных множеств.

Содержание

Описание АВО, основанных на тупиковых тестах

Формулировка задачи

Задача распознавания: Дано \ Y=\bigcup_{i=1\ldots l}{Y_i}\ — множество непересекающихся классов объектов.

Дана первоначальная информация I_0 (обучающая) и описание некоторого объекта I(x), x \in Y.
Объект задается через набор числовых признаков X=(x_1,\ldots,x_n).
Задача распознавания состоит в определении включения заданного объекта x в классы Y_i.

В случае АВО, основанных на тупиковых тестах, начальная информация I_0 задается таблицей:

  • T_{nml}=\parallel a_{ij}\parallel_{m\times n} - таблица признаков объектов в обучающей выборке;
  • I(X_i)=(a_{i1},\ldots,a_{in}) - описание объекта из обучающей выборки;
  • X_{m_{i-1}+1},\ X_{m_{i-1}+2},\ldots,\ X_{m_i}\in Y_i,\ i=1\ldots l,\ m_0=0,\ m_l=m - выражение, определяющее включение объектов в классы;

Алгоритм распознаванияA(I_0,X)=\alpha(X), где \alpha(X) = \alpha_1(I_0,X),\ldots ,\alpha_l(I_0,X).

\alpha_i(X) = 
\begin{cases} 
1,  &  X\in Y_i\\
0, & X \notin Y_i \\
\Delta, & \alpha\ \mathrm{doesn't\ accept\ X}.
\end{cases}

Строение АВО

  • \Omega=\{\omega|\omega \subseteq \{1, \ldots, n\}\} - система опорных множеств;
  • Вводится функция близости для двух объектов по опорному множеству \omega :


B_\omega(X, X')=\bigwedge_{s \in \omega}{[\rho_s (X, X') \leq \varepsilon_s]}, где \varepsilon_s неотрицательные числа, называемые порогами, s=1,\ldots ,n ;

  • Вводится оценка близости объекта к классу \Gamma_c;
  • Вычисление алгоритма проводится по правилу:


\alpha_j(I_0, X) = 
\begin{cases} 
1,  &  \Gamma_j(X)>\Gamma_i(X)+\delta_2;\ i=1,\ldots,l, \ i \neq j;\ \Gamma_j(X)>\delta_1\sum^{l}_{i=1}{\Gamma_j(X)};\\
0, & \mathrm{other\ way}.
\end{cases}
1>\delta_1\geq 1/l,\ \delta_2 \geq 0 - пороги осторожности.

Строение АВО, основанного на тупиковых тестах

  • Вводится система опорных множеств \Omega;
  • Задается функция близости для двух объектов по опорному множеству \omega=\{j_1,\ldots, j_r\}:


B_\omega(X_{i1}, X_{i2})=\bigwedge^{r}_{t=1}{\[|a_{i1j_t}-a_{i2j_t}| \leq \varepsilon_s\]}. Если B=0, объекты не являются близкими по опорному множеству.

Тупиковые тесты

Тестом называется набор столбцов таблицы обучения T_{nml} с номерами j_1,\ldots,\j_r, если любые два объекта, принадлежащие разным классам Y_i, не являются близкими по опорному множеству \omega =\{j_1,\ldots,\j_r\}. Тупиковым тестом называется тест, у которого его собственное подмножество не является таковым.
Задача распознавания на основе тупиковых тестов решается следующим образом. Пусть \{T\} - множество тупиковых тестов таблицы T_{nml}. По тупиковому тестуj=(j_1,\ldots,j_k) выделяется подописание для распознаваемого объекта X=(a_{j_1},\ldots,a_{j_r}), а затем сравнивается со всеми подописаниями объектов таблицы. Число совпадений с описаниями объектов i-го класса обозначается через \Gamma_{ji}(T).
Оценка объекта по i-ому классу \Gamma_{ji}(X) = \Gamma_i(X_j)=\frac{1}{m_j-m_{j-1}}\sum_{T \in\{T\}}{\Gamma_{ji}(T)}.

Далее объект относится к тому классу,по которому он получил максимальную оценку, в случае двух максимумов считается, что объект не классифицируется на заданном тесте.

Если считать, что не все признаки, описывающие объект, равнозначны, то они снабжаются числовыми весами p(j)=\frac{\tau_j(n,m)}{\tau(n,m)}, где \tau - число тупиковых тестов в таблице, \tau_j -число тупиковых тестов в таблице, содержащих j-ый столбец. Чем больше вес, тем важнее признак в описании объектов множества. Весами объектов, составляющих таблицу обучения, называется поощрительная величина \gamma. В случае совпадения распознаваемого объекта X с объектом из таблицы X_v \in Y_i, такое совпадение поощряется: \Gamma_T(X,X_v) = \gamma(X_v)(p(j_1),\ldots,p(j_r)), Оценка объекта по i-ому классу задается таким образом \Gamma_i(X)=\frac{1}{m_i-m_i-1}\sum_{T\in\{T\}}\sum^{m_i}_{m_{i-1}+1}{\Gamma_T(X_v,X)}.

Построение тупиковых тестов

Процесс построения всех тупиковых тестов очень трудоемкий, так как зачастую приходится использовать метод перебора. Для решения задач большой размерности применяются стохастические методы. Для обработки таблиц с относительно большим числом строк по сравнению с числом столбцов может применяться следующий метод.

  • Пусть i_1,i_2 \in(1,\ldots,m).

Паре объектов S_{i_1} и S_{i_2} ставится в соответствие строка I(X_{i_1})\oplus I(X_{i_2})=(a_{i_11}\oplus a_{i_21}, \dots, a_{i_1n}\oplus a_{i_1n}), если :

a_{i_1j}\oplus a_{i_2j} = 
\begin{cases} 
0,  &  |a_{i_1j}-a_{i_2j}|\leq \varepsilon_j\\
1, & \mathrm{other\ way}.
\end{cases}

  • Составим булеву матрицу L_{nml} из всех таких строк для объектов из разных классов.
  • U_i - совокупность всех подмножеств множества \{1,2,\ldots,h\} мощности i, где i - выбранное число из этого множества. h - число строк в матрице L_{nml}. Элементы множества U_i называются наборами.
  • Алгоритм построения тупиковых тестов:
  1. Пусть i=h, \ U_i=\{1,2,\ldots,h\}, задача построения множества всех тупиковых тестов таблицы T_{nml} сводится к построению множества всех неприводимых покрытий матрицы L_{nml}. В этом случае используется детерминированный алгоритм.
  2. Пусть i<h.
    1. Случайным образом выбираем набор u=\{i_1,\ldots,\i_r\} \in U_i, определяющий подматрицу L^u_{nml}, образованную строками с номерами i_1,\ldots,i_r.
    2. Тест таблицы T_{nml}, состоящий из столбцов j_1,\ldots,j_r называется u-тестом, если набор столбцов матрицы L^u_{nml} с теми же номерами является неприводимым покрытием. \mathcal{T}(T_{nml},u) - множество всех u-тестов в таблице T_{nml}.
    3. Каждому неприводимому покрытию матрицы L_{nml} соответствует набор столбцов таблицы T_{nml}, который проверяется на тестовость.
    4. Обработка последовательности u_1,\ldots,u_v приводит к построению случайной выборки \mathcal{T}'(T_{nml})=\bigcup^{v}_{t=1}{\mathcal{T}(T_{nml},u_t)}. В этом случае используется стохастический способ построения тупиковых тестов.

Замечание: Требуемая точность алгоритмов зависит от выбора параметров i и v. При определенных условия выбора этих величин стохастический алгоритм почти всегда совпадает с детерминированным, i=\log^{\gamma}_2 n, \ \gamma >3. для решения практических задач достаточно выбрать i=\log_2 n,\ v=20.

Литература

  1. К.В. Воронцов, Машинное обучение (курс лекций).
  2. Журавлев Ю. И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз. — 1988 T. 1. — С. 9--16.
  3. Бушманов О. Н., Дюкова Е. В., Журавлев Ю. И., Кочетков Д. В., Рязанов В. В. Система анализа и распознавания образов // Распознавание, классификация, прогноз. — М.: Наука, 1989. — T. 2. — С. 250–273.
Личные инструменты