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

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

(Различия между версиями)

Перейти к: навигация, поиск

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

Данная статья является непроверенным учебным заданием.

Студент: Участник:Mordasova

Преподаватель: Участник:Константин Воронцов

Срок: 15 февраля 2010

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

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

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

Содержание

1 Описание АВО, основанных на тупиковых тестах
2 Тупиковые тесты
- 2.1 Построение тупиковых тестов
3 Литература

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

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

Задача распознавания: Дано $\ 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$ называются наборами.
Алгоритм построения тупиковых тестов:

Пусть $i=h, \ U_i=\{1,2,\ldots,h\}$ , задача построения множества всех тупиковых тестов таблицы $T_{nml}$ сводится к построению множества всех неприводимых покрытий матрицы $L_{nml}$ . В этом случае используется детерминированный алгоритм.
Пусть .
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$ .

Литература

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A2%D1%83%D0%BF%D0%B8%D0%BA%D0%BE%D0%B2%D1%8B%D0%B5_%D1%82%D0%B5%D1%81%D1%82%D1%8B»

Категория: Непроверенные учебные задания

@@ Строка 1: / Строка 1: @@
 {{Задание|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>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}
+,  &  X\in Y_i\\
+, & 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}
-,  &  X\in K_i\\
+,  &  \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)};\\
-, & X \notin K_i \\
+, & \mathrm{other\ way}.
 \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}
-  n/2,  & \mbox{if }n\mbox{ is even} \\
+,  &  |a_{i_1j}-a_{i_2j}|\leq \varepsilon_j\\
-n+1, & \mbox{if }n\mbox{ is odd}
+, & \mathrm{other\ way}.
 \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
+}}

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

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

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

Содержание

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

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

Строение АВО

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

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

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

Литература

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты