Алгебраический подход к распознаванию образов

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

Содержание

1 Исторические предпосылки
- 1.1 Эвристические методы распознавания
- 1.2 От алгоритмов вычисления оценок к корректным алгебрам
2 Постановка задачи распознавания
3 Стандартный распознающий алгоритм
- 3.1 Распознающий оператор и решающее правило
- 3.2 Корректное решающее правило
4 Алгебра распознающих операторов
5 Алгоритмы вычисления оценок как базовая модель
- 5.1 Опорные множества и функции близости
- 5.2 Оценки по классам
6 Синтез и обучение корректора
7 Связь с современным искусственным интеллектом
8 Ограничения подхода
9 Применения
10 См. также
11 Литература

Алгебраический подход к распознаванию образов — направление математической теории распознавания образов, созданное Ю. И. Журавлёвым в 1970-х годах. Его основная идея состоит в том, чтобы рассматривать практически полезные, но не обязанные быть безошибочными эвристические алгоритмы как элементы формальной алгебраической системы. Сложение, умножение на скаляр, последовательное применение и другие операции порождают расширения исходных моделей; внутри такого расширения ищется алгоритм, корректный для заданной задачи или экстремальный по выбранному функционалу качества.

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

В современной терминологии ближайшими по архитектуре являются композиции алгоритмов, ансамблевое обучение и стекинг, но полного тождества между ними нет. Теория Журавлёва изучает алгебраические замыкания распознающих операторов и условия существования корректного элемента; современные ансамблевые методы обычно начинают со статистической функции потерь и непосредственно оптимизируют качество обобщения.

Исторические предпосылки

Эвристические методы распознавания

В 1950–1960-х годах задачи распознавания часто поступали из областей, в которых трудно было задать вероятностную модель или исчерпывающую систему правил. Объекты описывались смешанными признаками, обучающие выборки были малы, а сведения о классах могли быть неполными и противоречивыми. На практике применялись метод ближайших соседей, тестовые алгоритмы, алгоритм «Кора», линейные разделяющие правила, метод потенциальных функций и разнообразные схемы голосования.

Такие методы могли давать хорошие результаты, не будучи корректными на всём множестве допустимых задач. Слово некорректный в работах школы Журавлёва означает не ошибку в программе, а отсутствие гарантии правильного ответа для каждого допустимого входа. Слово эвристический подчёркивает, что структура алгоритма основана на содержательной гипотезе и подтверждается практикой.

Переход к алгебраическому подходу потребовал трёх шагов:

представить разнородные методы в единой операторной форме;
определить операции над алгоритмами и порождаемые ими замыкания;
сформулировать условия, при которых замыкание содержит корректный или оптимальный алгоритм.

От алгоритмов вычисления оценок к корректным алгебрам

В 1971 году Ю. И. Журавлёв и В. В. Никифоров описали алгоритмы вычисления оценок (АВО). Эта модель объединила большую группу прецедентных методов: объект сравнивается с обучающими объектами по различным фрагментам признакового описания, совпадения или близости превращаются в голоса, а голоса суммируются в оценки принадлежности классам.

Следующий этап состоял уже не в расширении одного семейства эвристик, а в построении формального аппарата над целыми моделями алгоритмов. В 1976 году была поставлена задача поиска алгоритмов, экстремальных по качеству, в математических моделях распознавания. В 1977–1978 годах вышли доклады об алгебрах над некорректными алгоритмами и цикл «Корректные алгебры над множествами некорректных (эвристических) алгоритмов». Развёрнутое изложение было дано в обзоре Ю. И. Журавлёва «Об алгебраическом подходе к решению задач распознавания или классификации» (1978).

Год	Результат	Значение для теории
1971	Публикация модели АВО Ю. И. Журавлёва и В. В. Никифорова	Единый язык для широкого семейства алгоритмов голосования по прецедентам и признаковым фрагментам
1976	Экстремальные алгоритмы в математических моделях распознавания	Постановка задачи синтеза алгоритма, оптимального по функционалу качества
1977	Алгебры над некорректными алгоритмами; первые две части цикла о корректных алгебрах	Операции над распознающими операторами, алгебраические расширения и условия корректности
1978	Третья часть цикла и общий обзор в «Проблемах кибернетики»	Систематическая теория стандартных алгоритмов, полноты моделей, линейных и функциональных замыканий
1980-е	Работы Ю. И. Журавлёва, К. В. Рудакова и других представителей школы	Перенос алгебраической коррекции на более общие процедуры обработки информации, исследование универсальных и локальных ограничений
2000-е	Исследования А. Г. Дьяконова алгебр над АВО	Оценки минимальной степени корректного алгоритма, операции нормировки и описание алгебраических замыканий
2010-е	Практические алгоритмы алгебраической и логической коррекции; связи с нейросетевыми реализациями	Сравнение корректоров на прикладных задачах и конструктивное воспроизведение корректных алгоритмов нейронными сетями

Постановка задачи распознавания

Допустимые объекты, классы и информация

Пусть $\mathcal S$ — множество допустимых объектов, а $K_1,\ldots,K_l\subseteq\mathcal S$ — классы. Классы могут пересекаться. Для каждого класса определён предикат

$P_j(S)=[S\in K_j],\qquad j=1,\ldots,l,$

где квадратные скобки обозначают индикатор истинности высказывания. Объекту $S$ сопоставлено допустимое описание $I(S)$ . Начальная информация о классах обозначается $I_0(K_1,\ldots,K_l)$ ; в стандартной задаче это размеченная обучающая выборка, но теория допускает и другие типы исходной информации.

Пусть для распознавания предъявлены объекты $S_1,\ldots,S_q$ . Их описания образуют информацию

$I_q=I(S_1,\ldots,S_q)=(I(S_1),\ldots,I(S_q)).$

Истинной информационной матрицей этой совокупности называется матрица

$M^{\ast}=(\alpha_{ij})_{q\times l},\qquad \alpha_{ij}=P_j(S_i)\in\{0,1\}.$

Строка $(\alpha_{i1},\ldots,\alpha_{il})$ называется истинным информационным вектором объекта $S_i$ . Задача распознавания состоит в восстановлении $M^{\ast}$ по паре $(I_0,I_q)$ .

Распознающий алгоритм

В исходной теории допускается три ответа на каждый вопрос о принадлежности классу:

$1$ — объект отнесён к классу;
$0$ — объект не отнесён к классу;
$\Delta$ — алгоритм отказался от ответа.

Обозначим $E_3=\{0,1,\Delta\}$ . Распознающим алгоритмом называется отображение

$A:(I_0,I_q)\longmapsto R_A=(\beta_{ij})_{q\times l},\qquad \beta_{ij}\in E_3.$

Отказ $\Delta$ является частью математической модели, а не техническим сбоем. Благодаря ему можно формально различать ошибочный ответ и отсутствие достаточных оснований для решения; эта идея соответствует современной классификации с отказом.

Функционал качества

Пусть $\rho$ — функция расхождения между истинным и вычисленным информационными векторами, причём $\rho(u,u)=0$ . Пусть функция $F_q$ достигает абсолютного максимума в точке $(0,\ldots,0)$ . Тогда функционал качества можно записать в форме

$\Phi_q(A)=F_q\bigl(\rho(\alpha_1,\beta_1^A),\ldots,\rho(\alpha_q,\beta_q^A)\bigr),$

где $\alpha_i$ и $\beta_i^A$ — строки матриц $M^{\ast}$ и $R_A$ . Частным случаем служит отрицательное число ошибочных ответов. Такая абстрактная запись позволяет одновременно учитывать ошибки разных типов и отказы.

Алгоритм корректен для данной задачи, если

$R_A=M^{\ast}.$

При принятой нормировке корректность влечёт достижение абсолютного максимума $\Phi_q$ . Обратное верно, если максимум $F_q$ достигается только в точке $(0,\ldots,0)$ и равенство $\rho(u,v)=0$ возможно только при $u=v$ . Корректность для конечной задачи не следует смешивать с обобщающей способностью: она утверждает точность на заданной совокупности объектов, но сама по себе ничего не говорит об ошибке на новых данных.

Стандартный распознающий алгоритм

Распознающий оператор и решающее правило

Основная структурная декомпозиция отделяет вычисление вещественных оценок от окончательного решения.

Распознающий оператор $B_A$ переводит исходную информацию в числовую матрицу оценок:

$B_A(I_0,I_q)=M_A=(a_{ij})_{q\times l},\qquad a_{ij}\in\mathbb R.$

Число $a_{ij}$ интерпретируется как оценка принадлежности объекта $S_i$ классу $K_j$ . Решающее правило $C_A$ переводит произвольную числовую матрицу соответствующей размерности в информационную матрицу:

$C_A:M_{q\times l}(\mathbb R)\longrightarrow M_{q\times l}(E_3).$

Стандартным распознающим алгоритмом называется последовательное применение этих отображений. В обозначениях исходных работ

$A=B_A C_A,$

а в современной записи композиции функций

$A=C_A\circ B_A.$

Например, пороговое решающее правило порядка один имеет для класса $K_j$ два порога $c_{0j}<c_{1j}$ :

При $a_{ij}<c_{0j}$ полагают $\beta_{ij}=0$ .

При $c_{0j}\leq a_{ij}<c_{1j}$ полагают $\beta_{ij}=\Delta$ .

При $a_{ij}\geq c_{1j}$ полагают $\beta_{ij}=1$ .

Теорема о стандартном представлении. Для каждого распознающего алгоритма $A$ существует эквивалентный стандартный распознающий алгоритм $A'=B_{A'}C_{A'}$ , который на каждой паре $(I_0,I_q)$ выдаёт ту же информационную матрицу:

$A(I_0,I_q)=A'(I_0,I_q).$

Эта теорема позволяет проводить алгебраические операции на уровне числовых операторов $B_A$ , сохраняя решающее правило отдельным компонентом.

Корректное решающее правило

Решающее правило $C$ называется корректным, если для всякой конечной совокупности допустимых объектов $S_1,\ldots,S_q$ существует числовая матрица $M$ , которую $C$ переводит в истинную информационную матрицу этой совокупности:

$C(M)=M^{\ast}.$

Это свойство относится к выразительности правила, а не к способу построения матрицы $M$ . Пороговые правила с достаточно свободным выбором оценок являются типичным примером корректных правил.

Алгебра распознающих операторов

Линейные операции

Пусть два распознающих оператора на одном входе строят матрицы

$B_1(I_0,I_q)=M_1,\qquad B_2(I_0,I_q)=M_2.$

Сумма операторов и произведение оператора на скаляр определяются через операции над матрицами:

$(B_1+B_2)(I_0,I_q)=M_1+M_2,$

$(cB_1)(I_0,I_q)=cM_1,\qquad c\in\mathbb R.$

Теорема о линейном пространстве распознающих операторов. По операциям сложения и умножения на скаляр множество распознающих операторов образует линейное пространство над $\mathbb R$ .

Пусть $\mathcal M_C=\{B C:B\in\mathcal B\}$ — модель стандартных алгоритмов с фиксированным решающим правилом $C$ . Её линейное замыкание состоит из алгоритмов

$L(\mathcal M_C)=\left\{\left(\sum_{r=1}^{m}c_rB_r\right)C:\ m<\infty,\ B_r\in\mathcal B,\ c_r\in\mathbb R\right\}.$

Коэффициенты $c_r$ задают алгебраический корректор. Даже если каждый $B_rC$ ошибается, линейная комбинация матриц оценок может оказаться правильно расположенной относительно порогов решающего правила.

Полнота и корректность модели

Определения корректности и полноты относятся к модели алгоритмов, а не к одному фиксированному алгоритму.

Корректная модель. Модель $\mathcal M$ называется корректной, если для любых допустимых $I_0$ , $q$ и $S_1,\ldots,S_q$ в ней существует алгоритм, на котором функционал $\Phi_q$ достигает абсолютного максимума.

Пусть $\mathcal B(\mathcal M)$ — множество распознающих операторов модели. Для фиксированной задачи рассмотрим множество порождаемых матриц

$\mathcal V(I_0,I_q)=\{B(I_0,I_q):B\in\mathcal B(\mathcal M)\}\subseteq\mathbb R^{q\times l}.$

Полная модель. Модель $\mathcal M$ называется полной, если для любых допустимых $I_0,I_q$ множество $\mathcal V(I_0,I_q)$ содержит базис пространства $\mathbb R^{q\times l}$ .

Полнота сильнее простого разнообразия алгоритмов: требуется возможность получить $ql$ линейно независимых направлений в пространстве всех матриц оценок.

Основная теорема о линейной коррекции. Если модель $\mathcal M$ полна и все входящие в неё решающие правила корректны, то линейное замыкание $L(\mathcal M)$ является корректным.

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

Последовательное применение и полиномиальные расширения

Линейное замыкание использует только операции первой степени. Для построения более богатых моделей вводится произведение распознающих операторов. Пусть оценки, вычисленные оператором $B_1$ , добавляются к описаниям обучающих и распознаваемых объектов как новые числовые признаки. Обозначим преобразованную информацию через $T_{B_1}(I_0,I_q)$ . Тогда последовательное применение определяется равенством

$(B_1B_2)(I_0,I_q)=B_2\bigl(T_{B_1}(I_0,I_q)\bigr).$

Таким образом, произведение в общей теории — это не покомпонентное умножение двух матриц, а вычислительный каскад. В общем случае оно некоммутативно:

$B_1B_2\ne B_2B_1.$

Используя сложение, умножение на скаляр и последовательное произведение, можно строить операторные многочлены

$P(B_1,\ldots,B_m)=\sum_{w}c_w B_{i_1(w)}B_{i_2(w)}\cdots B_{i_{d(w)}(w)},$

где сумма конечна, $c_w\in\mathbb R$ , а $d(w)$ — степень соответствующего одночлена. Совокупность таких операторов образует алгебраическое замыкание исходной модели. Алгоритмы вида

$A=P(B_1,\ldots,B_m)C$

называются полиномиальными коррекциями.

В специальных алгебрах над АВО вводились также покомпонентные операции над матрицами оценок, нормировка и деление. Эти конструкции являются отдельными конкретными алгебрами и не изменяют смысла общего последовательного произведения.

Функциональное замыкание

Корректировать можно не только числовые оценки, но и окончательные ответы алгоритмов. Пусть $A_1,\ldots,A_n$ выдали информационные матрицы $R^{(1)},\ldots,R^{(n)}$ . Для функции трёхзначной логики

$f_n:E_3^n\longrightarrow E_3$

новый алгоритм определяется покомпонентно:

$\beta_{ij}=f_n\bigl(\beta_{ij}^{(1)},\ldots,\beta_{ij}^{(n)}\bigr).$

Множество алгоритмов, получаемых допустимыми функциями $f_n$ , называется функциональным замыканием. Примеры включают большинство голосов, комитетные правила и правила с приоритетом положительного, отрицательного ответа или отказа.

Для обучения логического корректора результаты базовых алгоритмов на размеченных объектах задают частично определённую функцию: наблюдаемому набору ответов ставится в соответствие истинный ответ. Задача состоит в доопределении этой функции на всём кубе $E_3^n$ с учётом содержательных ограничений, например идемпотентности

$f_n(a,\ldots,a)=a$

и запрета порождать положительный ответ, если ни один базовый алгоритм его не дал. В отличие от алгебраической коррекции, здесь операции выполняются над дискретными ответами, а не над вещественными оценками.

Алгоритмы вычисления оценок как базовая модель

Опорные множества и функции близости

Пусть объект описан признаками

$I(S)=(x_1(S),\ldots,x_n(S)),$

а обучающая информация содержит объекты $S_1,\ldots,S_m$ с известной принадлежностью классам. Алгоритм АВО задаёт систему опорных множеств

$\Omega_A\subseteq 2^{\{1,\ldots,n\}}.$

Опорное множество $\omega\in\Omega_A$ выделяет фрагмент признакового описания. Для него определяется функция близости $b_\omega(S,S_i)$ . Например, для дискретных признаков строгая близость имеет вид

$b_\omega(S,S_i)=\prod_{r\in\omega}[x_r(S)=x_r(S_i)].$

Для метрических признаков можно использовать допуски $\varepsilon_r$ :

$b_\omega(S,S_i)=\prod_{r\in\omega}[\rho_r(x_r(S),x_r(S_i))\leq\varepsilon_r].$

В общей модели допускаются более сложные функции близости, веса объектов $t_i$ и веса опорных множеств $p_\omega$ . Оценка объекта $S$ по прецеденту $S_i$ и опорному множеству $\omega$ может быть записана как

$\Gamma_\omega(S,S_i)=t_i p_\omega b_\omega(S,S_i).$

Оценки по классам

Пусть $X_j=\{i:S_i\in K_j\}$ и $X_j\ne\varnothing$ . Типичная нормированная оценка принадлежности классу равна

$\Gamma_j(S)=\frac{1}{|X_j|}\sum_{i\in X_j}\sum_{\omega\in\Omega_A}t_i p_\omega b_\omega(S,S_i).$

Последовательно применяя формулу к объектам $S_1',\ldots,S_q'$ , получают матрицу оценок

$B_A(I_0,I_q)=\bigl(\Gamma_j(S_i')\bigr)_{q\times l}.$

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

Выбором $\Omega_A$ , функции близости, точностей $\varepsilon_r$ , весов $t_i,p_\omega$ , нормировок и решающего правила получают большое семейство алгоритмов. В него входят голосование по наборам признаков, тестовые алгоритмы и многие логические и метрические процедуры. Именно поэтому АВО удобны как базовая модель алгебраического подхода: отдельные параметры задают разные эвристики, а операции над их операторами порождают корректирующие расширения.

Синтез и обучение корректора

В исходной теории обучение формулируется как поиск экстремального алгоритма в параметрической модели или её замыкании. Практическая процедура состоит из следующих этапов.

Формирование базовых моделей. Выбираются алгоритмы разных типов или экземпляры одной модели с различными признаками, опорными множествами, функциями близости и параметрами.
Получение матриц оценок. Каждый распознающий оператор независимо применяется к обучающей или контрольной совокупности, формируя матрицу $M_r=B_r(I_0,I_q)$ .
Выбор корректирующего класса. Задаётся линейная форма, операторный многочлен ограниченной степени или функция трёхзначной логики.
Оптимизация параметров. Подбираются коэффициенты $c_r$ , параметры операторов и пороги решающего правила, максимизирующие $\Phi_q$ .
Контроль сложности и устойчивости. Ограничиваются число базовых операторов, степень многочлена и сложность логической функции; качество проверяется на объектах, не использованных при настройке корректора.

Для линейной коррекции

$B_c=\sum_{r=1}^{m}c_rB_r$

и порогового правила условия правильного распознавания превращаются в систему неравенств по коэффициентам $c_r$ и порогам. Если система несовместна, ищется максимальная совместная подсистема или непосредственно минимизируется число нарушений. В современных обозначениях типичная регуляризованная постановка имеет вид

$\min_{c,\theta}\ \sum_{i=1}^{q}\ell\bigl(\alpha_i,C_\theta(\sum_{r=1}^{m}c_rM_{r,i})\bigr)+\lambda\Omega(c),$

где $M_{r,i}$ — строка оценок $r$ -го алгоритма, $C_\theta$ — решающее правило с параметрами $\theta$ , $\ell$ — функция потерь, а $\Omega$ ограничивает сложность. Регуляризованная запись является современной реализацией общей идеи; исходные работы формулировали задачу через функционал качества и экстремальный алгоритм.

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

Связь с современным искусственным интеллектом

Прямое развитие внутри школы Журавлёва

Алгебраический подход продолжал развиваться как самостоятельная исследовательская программа.

К. В. Рудаков распространил идею коррекции на общие процедуры обработки информации и исследовал ограничения, при которых возможно построение корректных расширений.
А. Г. Дьяконов изучил алгебры над АВО, минимальную степень корректных алгоритмов, нормировки и системы эквивалентностей, описывающие алгебраические замыкания.
В. В. Рязанов, О. В. Сенько, А. А. Докукин и другие представители школы разрабатывали практические алгебраические и логические корректоры и программные системы распознавания.
В работе Ю. И. Журавлёва и А. Е. Дюсембаева 2019 года для модели с кусочно-линейными поверхностями и параметрами построена нейронная сеть, воспроизводящая вычисления корректного алгоритма. Это является прямой математической связью двух формализмов, а не только внешним сходством.

Практические исследования 2010-х годов использовали двухэтапную схему: группа алгоритмов независимо решает задачу для объекта, после чего корректор вычисляет коллективное решение. Эксперименты проводились с тестовыми, логическими, линейными, нейросетевыми и другими базовыми алгоритмами; рассматривались как логические корректоры, так и алгебраические корректоры малой степени.

Сопоставление с ансамблевыми методами

Современный метод	Общее с алгебраическим подходом	Существенное различие
Простое голосование	Функция применяется к ответам нескольких алгоритмов	Голосование использует заранее заданную симметричную операцию; функциональный корректор может быть произвольной обучаемой функцией допустимого класса
Бэггинг	Коллективное решение агрегирует несколько несовершенных алгоритмов	Бэггинг создаёт разнообразие бутстреп-выборками и прежде всего уменьшает дисперсию; алгебраическая теория не требует такого механизма порождения базы
Бустинг	Итоговая оценка часто является взвешенной линейной комбинацией базовых правил	Бустинг последовательно меняет веса объектов и строит новые базовые правила для уменьшения функции потерь; линейное замыкание Журавлёва сначала задаёт модель операторов и исследует существование корректной комбинации
Стекинг	Оценки базовых моделей становятся признаками для корректора второго уровня	Стекинг ориентирован на статистическую ошибку на новых объектах и обычно обучается по out-of-fold-предсказаниям; классическая теория корректности формулируется для конечной задачи
Глубокая нейронная сеть	Последовательное применение операторов порождает новые признаки; линейные операции сочетаются с нелинейным решающим правилом	Нейронная сеть обычно обучает все уровни совместно градиентным методом; алгебраический подход допускает разнородные готовые алгоритмы и дискретные операции синтеза
AutoML	Ищется экстремальный алгоритм в расширенной модели, включая структуру и параметры	AutoML является вычислительной технологией поиска и оценки; алгебраическая теория прежде всего описывает выразимость замыканий и условия корректности

Наиболее близок к алгебраической коррекции стекинг: в обоих случаях выходы базовых алгоритмов образуют новое пространство признаков, а второй уровень исправляет систематические ошибки первого. Однако работа Д. Уолперта о стекинге была сформулирована независимо в языке минимизации ошибки обобщения. Поэтому корректно говорить о близости конструкций и раннем появлении общей архитектурной идеи в школе Журавлёва, но не о доказанной прямой генеалогии каждого современного ансамблевого метода.

Выразительность и универсальная аппроксимация

Полнота алгебраической модели содержательно напоминает универсальную выразительность: на любой конечной задаче операторы модели порождают базис пространства матриц оценок. Тем не менее это разные утверждения.

Полнота определяется относительно конечной совокупности объектов и пространства $\mathbb R^{q\times l}$ .
Теоремы универсальной аппроксимации описывают приближение функций на области в выбранной норме.
Ни одно из этих свойств само по себе не гарантирует малой ошибки обобщения или устойчивости алгоритма.

Алгебраическая теория рано отделила представимость правильного решения от процедуры поиска решения. Это различие остаётся центральным для современного ИИ: большая модель может содержать требуемую функцию, но обучение должно найти её по ограниченным данным и не переобучиться.

Гибридные и нейросимвольные системы

Допустимость разнородных базовых алгоритмов делает подход естественным языком для гибридных систем. Один оператор может быть метрическим, другой логическим, третий нейросетевым; корректор работает с их оценками или ответами без требования одинаковой внутренней реализации. В современных терминах это близко к нейросимвольным системам, mixture-of-experts и объединению моделей разных модальностей.

Особенно важны три идеи:

модульность — базовый алгоритм и решающее правило являются отдельными объектами;
замкнутость относительно операций — новые модели строятся систематически, а не перечисляются по отдельности;
коррекция ошибок — ценность алгоритма определяется не только его индивидуальной точностью, но и тем, какую информацию его ответы добавляют коллективу.

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

Ограничения подхода

Алгебраическая теория даёт строгий ответ на вопрос о существовании корректного элемента в расширении модели, однако из этого ответа не следуют автоматически практические гарантии.

Конечная корректность не равна обобщению. Алгоритм может точно воспроизвести информационную матрицу контрольной совокупности и ошибаться на новых объектах.
Полнота может быть избыточной. Базис всего пространства $\mathbb R^{q\times l}$ позволяет реализовать любую разметку, включая случайную, и потому не является формой регуляризации.
Синтез может быть трудным. Поиск базиса, минимальной степени многочлена или максимальной совместной подсистемы ограничений является комбинаторной задачей.
Высокие степени могут быть неустойчивыми. Полиномиальный корректор способен усиливать малые изменения оценок; в практических алгоритмах приходится ограничивать степень и число одночленов.
Результат зависит от языка операций. Полнота и корректность относятся не к исходным эвристикам вообще, а к конкретно выбранным операциям, решающим правилам и допустимым задачам.

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

Применения

Методы школы Журавлёва применялись в задачах, где исходная информация мала, неоднородна или плохо формализована:

медицинская диагностика и прогнозирование;
геологический прогноз и поиск месторождений;
распознавание изображений и техническая диагностика;
химическая информатика и прогнозирование свойств соединений;
экономический и финансовый анализ;
обработка неполных и противоречивых данных;
коллективное решение наборами логических, метрических и нейросетевых алгоритмов.

Для прикладных задач особенно полезна возможность объединять содержательно разные модели, сохранять отказ от ответа и выбирать корректор по контрольной выборке. Программные системы ПАРК и «Распознавание», создававшиеся представителями школы, объединяли АВО, логические, статистические, линейные, нейросетевые и коллективные методы в общей среде решения задач.

См. также

Литература

Журавлёв Ю. И., Никифоров В. В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. 1971. № 3. С. 1–11.
Журавлёв Ю. И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации // Доклады АН СССР. 1976. Т. 231. № 3. С. 532–535.
Журавлёв Ю. И. Алгебры над множествами некорректных (эвристических) алгоритмов // Доклады АН СССР. 1977. Т. 235. № 4. С. 761–763.
Журавлёв Ю. И. Экстремальные алгоритмы в алгебре над некорректными алгоритмами // Доклады АН СССР. 1977. Т. 237. № 3. С. 509–512.
Журавлёв Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. I // Кибернетика. 1977. № 4. С. 5–17.
Журавлёв Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. II // Кибернетика. 1977. № 6. С. 17–24.
Журавлёв Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. III // Кибернетика. 1978. № 2. С. 35–43.
Журавлёв Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. 1978. Вып. 33. С. 5–68.
Журавлёв Ю. И., Зенкин А. А., Зенкин А. И., Исаев И. В., Кольцов П. П., Кочетков Д. В., Рязанов В. В. Задачи распознавания и классификации со стандартной обучающей информацией // Журнал вычислительной математики и математической физики. 1980. Т. 20. № 5. С. 1294–1309.
Журавлёв Ю. И., Рудаков К. В. Об алгебраической коррекции процедур обработки (преобразования) информации // Проблемы прикладной математики и информатики. 1987. С. 187–198.
Дьяконов А. Г. Алгебра над алгоритмами вычисления оценок: минимальная степень корректного алгоритма // Журнал вычислительной математики и математической физики. 2005. Т. 45. № 6. С. 1134–1145.
Журавлёв Ю. И., Рязанов В. В., Сенько О. В. Распознавание. Математические методы. Программная система. Практические применения. М.: ФАЗИС, 2005.
Zhuravlev Yu. I., Ablameyko S. V., Biryukov A. S., Dokukin A. A., Krasnoproshin V. V., Obraztsov V. V., Romanov M. Yu., Ryazanov V. V. Algorithms for Algebraic and Logical Correction and Their Applications // Pattern Recognition and Image Analysis. 2010. Vol. 20. No. 2. P. 105–117.
Дьяконов А. Г. Теория систем эквивалентностей для описания алгебраических замыканий обобщённой модели вычисления оценок // Журнал вычислительной математики и математической физики. 2010. Т. 50. № 2. С. 388–400.
Абламейко С. В., Бирюков А. С., Докукин А. А., Краснопрошин В. В., Образцов В. В., Романов М. Ю., Рязанов В. В. Практические алгоритмы алгебраической и логической коррекции в задачах распознавания по прецедентам // Журнал вычислительной математики и математической физики. 2014. Т. 54. № 12. С. 1979–1993.
Журавлёв Ю. И., Дюсембаев А. Е. Построение нейросети на основе модели алгоритмов с кусочно-линейными поверхностями и параметрами для задач распознавания со стандартной информацией // Доклады Академии наук. 2019. Т. 488. № 1. С. 11–15.
Wolpert D. H. Stacked Generalization // Neural Networks. 1992. Vol. 5. No. 2. P. 241–259.
Breiman L. Bagging Predictors // Machine Learning. 1996. Vol. 24. P. 123–140.
Freund Y., Schapire R. E. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting // Journal of Computer and System Sciences. 1997. Vol. 55. No. 1. P. 119–139.
D’yakonov A. G., Vinogradov A. P., Dokukin A. A., Ryazanov V. V., Senko O. V. Recognition Methods in Academician Yu. I. Zhuravlev’s Scientific School // Pattern Recognition and Image Analysis. 2023. Vol. 33. No. 4. P. 952–982.

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BF%D0%BE%D0%B4%D1%85%D0%BE%D0%B4_%D0%BA_%D1%80%D0%B0%D1%81%D0%BF%D0%BE%D0%B7%D0%BD%D0%B0%D0%B2%D0%B0%D0%BD%D0%B8%D1%8E_%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2»

Категории: Энциклопедия анализа данных | Распознавание образов | Теоретические исследования | Популярные и обзорные статьи