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

Материал из 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://poligon.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»

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

@@ Строка 4: / Строка 4: @@
 ==Описание АВО, основанных на тупиковых тестах==
 ===Формулировка задачи===
-'''Задача распознавания:''' <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</tex> в классы <tex>Y_i</tex>.<br />
@@ Строка 30: / Строка 30: @@
 *Вводится ''функция близости'' для двух объектов по опорному множеству <tex>\omega</tex> :<br />
 <tex>
-B_\omega(X, X')=\bigwedge_{s \in \omega}{[\rho_s (X, X') \leq \varepsilon_s]}</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>\varepsilon_s </tex> неотрицательные числа, называемые порогами, <tex>s=1,\ldots ,n </tex>;
-*Вводится оценка близости объекта к классу <tex>\Gamma_c</tex>
+*Вводится оценка близости объекта к классу <tex>\Gamma_c</tex>;
 *Вычисление алгоритма проводится по правилу:<br />
@@ Строка 39: / Строка 39: @@
 \alpha_j(I_0, X) =
 \begin{cases}
-,  &  \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)}\\
+,  &  \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)};\\
 , & \mathrm{other\ way}.
 \end{cases}
 </tex><br />
-<tex>1>\delta_1\leq 1/l,\ \delta_2 \geq 0</tex> - ''пороги осторожности''.
+<tex>1>\delta_1\geq 1/l,\ \delta_2 \geq 0</tex> - ''пороги осторожности''.
 ===Строение АВО, основанного на тупиковых тестах===
@@ Строка 50: / Строка 50: @@
 *Задается функция близости для двух объектов по опорному множеству <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>, объекты не являются близкими по опорному множеству.
+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>, а затем сравнивается со всеми подописаниями объектов таблицы. Число совпадений с описаниями объектов i-го класса обозначается через <tex>\Gamma_{ji}(T)</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 />
-''Оценка объекта по i-ому классу'' <tex>\Gamma_{ji}(X) = \Gamma_i(X_j)=\frac{1}{m_j-m_{j-1}}\sum_{T \in\{T\}}{\Gamma_{ji}(T)}</tex>.
+''Оценка объекта по <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> -число тупиковых тестов в таблице, содержащих j-ый столбец. Чем больше вес, тем важнее признак в описании объектов множества.
+Если считать, что не все признаки, описывающие объект, равнозначны, то они снабжаются числовыми весами <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>,
-Оценка объекта по i-ому классу задается таким образом
+Оценка объекта по <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>.
+<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=(1,\ldots,m)</tex>.
+*Пусть <tex>i_1,i_2 \in(1,\ldots,m)</tex>.
-Паре объектов <tex>S_1</tex> и <tex>S_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>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} =
@@ Строка 78: / Строка 78: @@
 </tex><br />
 *Составим булеву матрицу <tex>L_{nml}</tex> из всех таких строк для объектов из разных классов.
-* <tex>U_i</tex> - совокупность всех подмножеств множества <tex>\{1,2,\ldots,h\}</tex> мощности i - выбранного числа из этого множества. h - число строк в матрице <tex>L_{nml}</tex>. Элементы множества <tex>U_i</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>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>. В этом случае используется стохастический способ построения тупиковых тестов.
-'''Замечание:''' Требуемая точность алгоритмов зависит от выбора параметров i и v. При определенных условия выбора этих величин стохастический алгоритм почти всегда совпадает с детерминированным, <tex>i=\log^{\gamma}_2 n, \ \gamma >3</tex>. для решения практических задач достаточно выбрать <tex>i=\log_2 n, v=20</tex>.
+'''Замечание:''' Требуемая точность алгоритмов зависит от выбора параметров <tex>i</tex> и <tex>v</tex>. При определенных условия выбора этих величин стохастический алгоритм почти всегда совпадает с детерминированным, <tex>i=\log^{\gamma}_2 n, \ \gamma >3</tex>. для решения практических задач достаточно выбрать <tex>i=\log_2 n,\ v=20</tex>.
 ==Литература==
-#''К.В. Воронцов'', [[Машинное обучение (курс лекций, К.В.Воронцов)|Машинное обучение (курс лекций)]]
+#''К.В. Воронцов'', [[Машинное обучение (курс лекций, К.В.Воронцов)|Машинное обучение (курс лекций)]].
 #{{книга
 |автор         = Журавлев Ю. И.

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

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

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

Содержание

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

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

Строение АВО

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

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

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

Литература

Просмотры

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

Навигация

Поиск

Инструменты