Журнал вычислительной математики и математической физики, 2021, T. 61, № 7, стр. 1192-1205

1. ВВЕДЕНИЕ

В теории кодирования источников с допустимой погрешностью Шенноном введена функция “скорость–погрешность” (rate distortion function) [1], которая при заданной погрешности дает нижнюю границу скорости кодирования, либо при заданной скорости определяет нижнюю границу погрешности для всевозможных способов (алгоритмов) кодирования. Функция “скорость–погрешность” определяется параметрами источника и метрикой погрешности и не зависит от выбранного алгоритма кодирования. Поэтому качество любого алгоритма кодирования может быть оценено избыточностью скорости кода относительно нижней границы при заданной погрешности, либо избыточностью погрешности кода относительно нижней границы при заданной скорости.

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

Известны работы, в которых приводятся теоретические оценки точности для классификаторов с различными решающими правилами [2], [3]. Однако эти работы не содержат общего подхода к построению нижней границы вероятности ошибки, не зависящей от конкретных решающих алгоритмов. Поскольку многие современные модели анализа данных и машинного обучения широко используют методы теории информации [4], естественно предложить новый подход для построения нижней границы вероятности ошибки классификации данных с использованием средней взаимной информации между множеством классифицируемых данных и множеством возможных решений о классах предъявляемых данных. Цель такого подхода заключается в нахождении наименьшей средней взаимной информации как убывающей функции заданной допустимой вероятности ошибки. Очевидно, что при фиксированной средней взаимной информации такая функция дает наименьшую вероятность ошибки.

Для получения нижней границы вероятности ошибки классификации на заданном множестве объектов предлагается использовать теоретико-информационную модель на основе известной схемы кодирования источника с допустимой погрешностью при наличии канала наблюдения с шумом [5]. В предлагаемой модели метки классов и классифицируемые объекты рассматриваются как входные и выходные данные канала наблюдения, вероятностные характеристики которого определяются условными по классам вероятностями или их аппроксимациями, построенными с использованием метрики на множестве объектов. Средняя погрешность между исходными метками классов и решениями измеряется в метрике Хемминга и эквивалентна вероятности ошибки. Для такой модели вводится функция “взаимная информация–вероятность ошибки” в форме зависимости наименьшей средней взаимной информации, содержащейся в множестве объектов относительно множества принимаемых решений, от вероятности ошибки и строится нижняя граница этой функции. Предлагаемая граница анонсирована в работах [6], [7] в форме обобщения нижней границы Шеннона для функции “скорость–погрешность” в схеме кодирования независимых символов конечного алфавита с допустимой средней погрешностью в метрике Хемминга. В настоящей работе дается строгое доказательство предложенной нижней границы для обменного соотношения “взаимная информация–вероятность ошибки”.

В настоящей работе получены нижние границы соотношения “взаимная информация–вероятность ошибки” для множества объектов с заданной метрикой и для ансамбля множеств различной модальности. Показана возможность уменьшения вероятности ошибки за счет увеличения средней взаимной информации между ансамблем данных и множеством классов с увеличением числа источников в ансамбле. Построенные границы достигаются на байесовском решающем алгоритме с разделяющими функциями, заданными апостериорными вероятностями классов [8]. Приведены численные реализации нижних границ функции “взаимная информация–вероятность ошибки” для множества подписей, множества лиц и для множества составных объектов, образованных парами “лицо, подпись”.

2. ТЕОРЕТИКО-ИНФОРМАЦИОННАЯ МОДЕЛЬ КЛАССИФИКАЦИИ И ЗАДАЧА ИССЛЕДОВАНИЯ

Пусть $\Omega = \{ {{\omega }_{1}},...{\text{, }}{{\omega }_{c}}\} $, $c \geqslant 2$, – множество классов с априорными вероятностями $P({{\omega }_{i}}),i = 1,...,c$, и ${\mathbf{X}}$ – множество объектов с условными по классам вероятностями $P({\mathbf{x}}\,{\text{|}}\,{{\omega }_{i}})$ $\forall {\mathbf{x}} \in {\mathbf{X}}$, $i = 1,...,c$. Будем считать, что множества $\Omega $ и ${\mathbf{X}}$ являются входными и выходными данными преобразования $\Omega \to {\mathbf{X}}$. Множество объектов ${\mathbf{X}}$и множество решений $\hat {\Omega } = \left\{ {{{\omega }_{j}} = 1,...,c} \right\}$ о классах этих объектов являются входом и выходом преобразования ${\mathbf{X}} \to \hat {\Omega }$. Пусть ${{{\text{X}}}^{N}} = ({{{\mathbf{x}}}_{1}},...,{{{\mathbf{x}}}_{N}})$ – блок объектов ${{{\mathbf{x}}}_{n}} \in {\mathbf{X}}$, $n = 1,...,N$, и ${{{\mathbf{X}}}^{N}}$ – множество всевозможных блоков длины $N$. Условные по классам вероятности блоков ${{{\text{X}}}^{N}} \in {{{\mathbf{X}}}^{N}}$ являются характеристиками канала наблюдения $\Omega \to {{{\mathbf{X}}}^{N}}$ и образуют множество распределений

а условные вероятности решений ${{\omega }_{j}} \in \hat {\Omega }$ для каждого предъявляемого блока являются характеристиками тест-канала ${{{\mathbf{X}}}^{N}} \to \hat {\Omega }$ и образуют множество распределений В принятых обозначениях множества $\Omega $ и $\hat {\Omega }$ состоят их одних и тех же элементов, однако вероятности элементов множества $\hat {\Omega }$ могут отличаться от априорных вероятностей соответствующих элементов множества $\Omega $. Множества $\Omega ,\;{{{\mathbf{X}}}^{N}},\;\hat {\Omega }$ совместно с распределениями $\operatorname{P} $ и $\operatorname{Q} $ порождают схему классификации в которой распределения $\operatorname{P} $ считаются известными, а распределения $\operatorname{Q} $ подлежат оптимизации.

Для оптимизации множества распределений $\operatorname{Q} $ в (1) введем функционалы средней взаимной информации ${{I}_{\operatorname{Q} }}({{{\mathbf{X}}}^{N}};\hat {\Omega }) \geqslant 0$ и вероятности ошибки ${{E}_{\operatorname{Q} }}({{{\mathbf{X}}}^{N}},\hat {\Omega }) \geqslant 0$, зависящие от $\operatorname{Q} $. Согласно [1], средняя взаимная информация имеет вид

где соответственно безусловные вероятности блоков ${{{\text{X}}}^{N}} \in {{{\mathbf{X}}}^{N}}$ и решений ${{\omega }_{j}} \in \hat {\Omega }$, а $H(\hat {\Omega })$ и $H(\hat {\Omega }\,{\text{|}}\,{{{\mathbf{X}}}^{N}})$ – соответственно безусловная и условная энтропии на множестве решений $\hat {\Omega }$, причем $H(\hat {\Omega }) \geqslant H(\hat {\Omega }\,{\text{|}}\,{{{\mathbf{X}}}^{N}})$. Средняя вероятность ошибки определяется средним значением индикатора $[{{\omega }_{j}} \ne {{\omega }_{i}}]$ и имеет вид где есть вероятность ошибки на решении ${{\omega }_{j}}$ по блоку объектов ${{{\text{X}}}^{N}}$.

Используя функционалы (2) и (3), введем функцию “взаимная информация–вероятность ошибки”

где внутренний минимум берется по всевозможным множествам распределений $\operatorname{Q} $ при $\varepsilon > 0$ и $N \geqslant 1$. Задача состоит в нахождении нижней границы функции $R(\varepsilon )$ для источника с заданным множеством объектов ${\mathbf{X}}$ и для ансамбля множеств ${{{\mathbf{X}}}^{M}} = {{{\mathbf{X}}}_{1}}...{{{\mathbf{X}}}_{M}}$, порождаемых $M \geqslant 2$ источниками различной модальности.

Следует отметить, что функция $R(\varepsilon )$ убывает с ростом $\varepsilon $ и, следовательно, при любом фиксированном значении дает наименьшую вероятность ошибки, которая может быть достигнута при заданной средней взаимной информации между входом и выходом классификатора. В общем случае минимальная вероятность ошибки соответствует наибольшему значению функции вида (1), которая может быть введена для $M \geqslant 1$ источников. Наибольшее значение такой функции должно определяться средней взаимной информацией $I({{{\mathbf{X}}}^{M}};\Omega )$ между ансамблем ${{{\mathbf{X}}}^{M}}$ и множеством классов $\Omega $. Иллюстрация зависимости минимальной вероятности ошибки от числа источников $M$ дана на фиг. 1. Поскольку средняя взаимная информация $I({{{\mathbf{X}}}^{M}};\Omega ) = H(\Omega ) - H(\Omega |{{{\mathbf{X}}}^{M}})$ является теоретико-информационной мерой пересечения $\Omega \cap {{{\mathbf{X}}}^{M}}$ (“серая область”), а условная энтропия $H(\Omega \,{\text{|}}\,{{{\mathbf{X}}}^{M}})$ – теоретико-информационной мерой разности $\Omega {{\backslash }}{{{\mathbf{X}}}^{M}}$ (“черная область”), то наименьшая вероятность ошибки должна уменьшаться с уменьшением $H(\Omega \,{\text{|}}\,{{{\mathbf{X}}}^{M}})$ и, соответственно, с ростом $I({{{\mathbf{X}}}^{M}};\Omega )$. С увеличением числа $M$ декоррелированных источников “серая область” увеличивается, а “черная область” уменьшается, что должно привести к снижению наименьшей вероятности ошибки. Формальное обоснование зависимости минимальной вероятности ошибки от энтропии $H(\Omega \,{\text{|}}\,{{{\mathbf{X}}}^{M}})$ или взаимной информации $I({{{\mathbf{X}}}^{M}};\Omega )$ будет дано в разд. 3 и 4.

3. НИЖНЯЯ ГРАНИЦА ФУНКЦИИ $R(\varepsilon )$ ДЛЯ ЗАДАННОГО ИСТОЧНИКА

Построение нижней границы $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} (\varepsilon ) \leqslant R(\varepsilon )$ базируется на технике, предложенной в работе [5]. Пусть $\Omega {\kern 1pt} * = \{ {{\omega }_{k}},k = 1,...,c\} $ – множество решений о классах, получаемых на преобразовании ${{{\mathbf{X}}}^{{N{\kern 1pt} *}}} \to \Omega {\kern 1pt} *$ с наименьшей вероятностью ошибки $\varepsilon _{{\min }}^{{}}$, которая реализуется на байесовском решающем правиле для блоков ${{\operatorname{X} }^{{N{\kern 1pt} *}}} \in {{{\mathbf{X}}}^{{N*}}}$ длины $N{\kern 1pt} *$ (см. [8]). Введенное преобразование порождает разбиение множества ${{{\mathbf{X}}}^{{N*}}}$ на непересекающиеся области решений ${\mathbf{X}}_{k}^{{N{\kern 1pt} *}} \to {{\omega }_{k}},$ $k = 1,...,c$, которые соответствуют классам множества $\Omega {\kern 1pt} *$. В полученном разбиении $k$-я область имеет вероятность

и для любого блока ${{\operatorname{X} }^{{N{\kern 1pt} *}}} \in {\mathbf{X}}_{k}^{{N{\kern 1pt} *}}$ условная вероятность решения ${{\omega }_{j}} \in \hat {\Omega }$ одинакова и равна $Q({{\omega }_{j}}\,{\text{|}}\,{{\operatorname{X} }^{{N{\kern 1pt} *}}}) = Q{\kern 1pt} *({{\omega }_{j}}\,{\text{|}}\,{{\omega }_{k}})$. С учетом условных распределений и $N = N{\kern 1pt} *$ средняя взаимная информация (2) преобразуется к виду а вероятность ошибки (3) удовлетворяет неравенству Соотношения (5) и (6) сводят нахождение границы $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} (\varepsilon )$ к вычислению минимума Минимум (7) следует из известной нижней границы Шеннона [1] в схеме кодирования $\Omega {\kern 1pt} * \to \hat {\Omega }$ с допустимой погрешностью в метрике Хемминга $[{{\omega }_{k}} \ne {{\omega }_{j}}]$ при условии, что средняя погрешность не превосходит величины $\varepsilon - {{\varepsilon }_{{\min }}} \geqslant 0$. Полученная граница сформулирована в следующей теореме.

Теорема. Нижняя граница функции $R(\varepsilon )$ имеет вид

где $h(z) = - z\ln z - (1 - z)\ln (1 - z)$, $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} ({{\varepsilon }_{{\min }}}) = I({\mathbf{X}};\Omega )$, $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} ({{\varepsilon }_{{\max }}}) = 0$ и $I({\mathbf{X}};\Omega )$ – средняя взаимная информация между множествами ${\mathbf{X}}$ и $\Omega $.

Доказательство. Применение нижней границы Шеннона для минимума в (7) дает

где а условные распределения имеют параметрическую форму с параметром $s > 0$. Значение параметра следует из уравнения которое дает решение ${{e}^{{ - s}}} = (\varepsilon - {{\varepsilon }_{{\min }}}){\text{/}}(c - 1)\left( {1 - (\varepsilon - {{\varepsilon }_{{\min }}})} \right)$ и условные вероятности на которых достигается условная энтропия В точке $\varepsilon = {{\varepsilon }_{{\min }}}$ соотношение (9) дает ${{H}_{s}}(\hat {\Omega }\,{\text{|}}\,\Omega {\kern 1pt} *) = 0$ и правая часть в (8) равна $H(\Omega {\kern 1pt} *)$.

Согласно теореме кодирования для источника [1], энтропия выхода преобразования ${{{\mathbf{X}}}^{{N{\kern 1pt} *}}} \to \Omega {\kern 1pt} *$ удовлетворяет неравенству $H(\Omega {\kern 1pt} *) \geqslant R({{\varepsilon }_{{\min }}})$. Из (4) имеем $R({{\varepsilon }_{{\min }}}) = {{I}_{{\text{Q}}}}({{{\mathbf{X}}}^{{N{\kern 1pt} *}}};\Omega {\kern 1pt} *)$, где ${\text{Q}}$ – множество распределений апостериорных вероятностей (см. [8])

В этом случае ${{I}_{{\text{Q}}}}({{{\mathbf{X}}}^{{N{\kern 1pt} *}}};\Omega {\kern 1pt} *) = I({{{\mathbf{X}}}^{{N{\kern 1pt} *}}};\Omega )$, а $I({{{\mathbf{X}}}^{{N{\kern 1pt} *}}};\Omega )$ – средняя взаимная информации между выходом и входом канала наблюдения в схеме (1) . Поскольку для любого ансамбля ${{{\mathbf{X}}}^{N}} = {{{\mathbf{X}}}_{1}}...{{{\mathbf{X}}}_{N}}$ справедливо неравенство $\max _{{n = 1}}^{N}I({{{\mathbf{X}}}_{n}};\Omega ) \leqslant I({{{\mathbf{X}}}^{N}};\Omega )$, которое в случае тождественных множеств ${{{\mathbf{X}}}_{n}} = {\mathbf{X}},$ $n = 1,...,N$, выполняется со знаком равенства, имеем $I({{{\mathbf{X}}}^{{N{\kern 1pt} *}}};\Omega ) = I({\mathbf{X}};\Omega )$. С учетом сделанных замечаний получаем для энтропии $H(\Omega {\kern 1pt} *{\kern 1pt} )$ следующую нижнюю оценку: Замены условной и безусловной энтропий в (8) правыми частями соотношений (9) и (10) завершают доказательство теоремы.

Граница $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} (\varepsilon )$ убывает с увеличением $\varepsilon $ и достигает наибольшего значения $I({\mathbf{X}};\Omega ) = H(\Omega ) - H(\Omega \,{\text{|}}\,{\mathbf{X}})$ $I({\mathbf{X}};\Omega ) = H(\Omega ) - H(\Omega \,{\text{|}}\,{\mathbf{X}})$ в точке $\varepsilon = {{\varepsilon }_{{\min }}}$. Здесь

есть энтропия множества $\Omega $ и есть условная энтропия множества $\Omega $ при заданном множестве ${\mathbf{X}}$, причем $H(\Omega \,{\text{|}}\,{\mathbf{X}}) \leqslant H(\Omega )$.

Следует отметить, что сформулированная в теореме граница $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} (\varepsilon )$ является обобщением нижней границы Шеннона в схеме кодирования независимых дискретных сообщений с ограниченной средней погрешностью, измеряемой в метрике Хемминга [1]. В схеме Шеннона условные вероятности $P({\mathbf{x}}\,{\text{|}}\,{{\omega }_{i}}) = [{\mathbf{x}} = {{{\mathbf{x}}}_{i}}],$ $i = 1,...,c$, принимают значения 1 и 0. В этом случае согласно формуле Байеса $Q({{\omega }_{j}}\,{\text{|}}\,{\mathbf{x}}) = [{{\omega }_{j}} = {{\omega }_{i}}]$ и, следовательно, $H(\Omega \,{\text{|}}\,{\mathbf{X}}) = 0$ и $I({\mathbf{X}};\Omega ) = H(\Omega )$, что дает ${{\varepsilon }_{{\min }}} = 0$ и $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} ({{\varepsilon }_{{\min }}}) = H(\Omega )$. В общем случае ${{\varepsilon }_{{\min }}} \geqslant 0$, а наибольшая вероятность ошибки равна

и преобразуется к виду ${{\varepsilon }_{{\max }}} = {{(c - 1)} \mathord{\left/ {\vphantom {{(c - 1)} c}} \right. \kern-0em} c}$ при равномерном априорном распределении.

Минимальная вероятность ошибки ${{\varepsilon }_{{\min }}}$ зависит от величины условной энтропии $H(\Omega \,{\text{|}}\,{\mathbf{X}}) \geqslant 0$. Поскольку при значениях ${{\varepsilon }_{{\min }}} \geqslant 0$ граница $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} (\varepsilon )$ достигает нулевого значения в точке $\varepsilon = {{\varepsilon }_{{\max }}}$, справедливо равенство

которое с учетом разложения при малых значениях ${{\varepsilon }_{{\min }}}$ преобразуется к виду Решение полученного уравнения относительно ${{\varepsilon }_{{\min }}}$ дает при значениях производных $h{\kern 1pt} '({{\varepsilon }_{{\max }}}) = \ln \left( {(1 - {{\varepsilon }_{{\max }}}){\text{/}}{{\varepsilon }_{{\max }}}} \right)$ и $\left| {h{\kern 1pt} '{\kern 1pt} '({{\varepsilon }_{{\max }}})} \right| = {{\left( {{{\varepsilon }_{{\max }}}(1 - {{\varepsilon }_{{\max }}})} \right)}^{{ - 1}}}$ асимптотическую оценку которая в случае равновероятных классов имеет вид Оценки (11) и (12) демонстрируют уменьшение вероятности ошибки ${{\varepsilon }_{{\min }}}$ с уменьшением условной энтропии $H(\Omega \,{\text{|}}\,{\mathbf{X}})$ и, следовательно, с увеличением средней взаимной информации $I({\mathbf{X}};\Omega )$ при фиксированной энтропии $H(\Omega )$. При этом $H(\Omega \,{\text{|}}\,{\mathbf{X}}) = 0$ обеспечивает ${{\varepsilon }_{{\min }}} = 0$.

4. ОБОБЩЕНИЕ ДЛЯ АНСАМБЛЯ ИСТОЧНИКОВ

Будем считать, что ансамбль ${{{\mathbf{X}}}^{M}} = {{{\mathbf{X}}}_{1}}...{{{\mathbf{X}}}_{M}}$ порождает составные объекты ${{{\mathbf{x}}}^{M}} = {{({{{\mathbf{x}}}_{1}},...,{{{\mathbf{x}}}_{M}})}^{t}}$, содержащие$M$объектов одного класса, по одному от каждого источника ${{{\mathbf{x}}}_{m}} \in {{{\mathbf{X}}}_{m}},$ $m = 1,...,M$, и каждый составной объект ${{{\mathbf{x}}}^{M}}$ образует столбец размера$M$. Набор из $N$ составных объектов образует блок столбцов ${{{\text{X}}}^{{MN}}} = ({\mathbf{x}}_{1}^{M},...,{\mathbf{x}}_{N}^{M}),$ ${\mathbf{x}}_{n}^{M} \in {{{\mathbf{X}}}^{M}},$ $n = 1,...,N$; всевозможные блоки ${{{\text{X}}}^{{MN}}}$ размера $M \times N$ образуют множество ${{{\mathbf{X}}}^{{MN}}}$. В этом случае канал наблюдения $\Omega \to {{{\mathbf{X}}}^{{MN}}}$ задается условными распределениями вероятностей блоков ${{{\text{X}}}^{{MN}}}$:

а тест-канал ${{{\mathbf{X}}}^{{MN}}} \to \hat {\Omega }$ определяется условными распределениями вероятностей решений: по блокам составных объектов.

Множества $\Omega ,\;{{{\mathbf{X}}}^{{MN}}},\;\hat {\Omega }$ совместно с распределениями ${{\operatorname{P} }^{M}}$ и ${{\operatorname{Q} }^{M}}$ порождают схему классификации

которая аналогична схеме (1) . Распределения ${{\operatorname{P} }^{M}}$ и ${{\operatorname{Q} }^{M}}$ дают среднюю взаимную информацию ${{I}_{{{{\operatorname{Q} }^{M}}}}}({{{\mathbf{X}}}^{{MN}}};\hat {\Omega })$ и вероятность ошибки ${{E}_{{{{\operatorname{Q} }^{M}}}}}({{{\mathbf{X}}}^{N}},\hat {\Omega })$ в форме функционалов (2) и (3). Для заданного значения $\varepsilon > 0$ эти функционалы позволяют ввести невозрастающую функцию в форме, аналогичной (4), причем ${{R}_{M}}(\varepsilon ) = R(\varepsilon )$, когда $M = 1$. Применение техники, использованной в разд. 3 для построения границы $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} (\varepsilon ) \leqslant R(\varepsilon )$, дает для функции (13) нижнюю границу которая по форме аналогична границе $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} (\varepsilon )$, приведенной в теореме. В границе (14) $I({{{\mathbf{X}}}^{M}};\Omega )$ – средняя взаимная информация между ансамблем ${{{\mathbf{X}}}^{M}}$ и множеством $\Omega $, $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} _{M}^{{}}(\varepsilon _{{\min }}^{M}) = I({{{\mathbf{X}}}^{M}};\Omega )$ и $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} _{M}^{{}}(\varepsilon _{{\max }}^{M}) = 0$. Для минимальной вероятности ошибки $\varepsilon _{{\min }}^{M}$ сохраняются асимптотические оценки вида (11) и (12) с заменой энтропии $H(\Omega \,|\,{\mathbf{X}})$ величиной $H(\Omega \,{\text{|}}\,{{{\mathbf{X}}}^{M}})$ и заменой вероятности ошибки ${{\varepsilon }_{{\max }}}$ величиной $\varepsilon _{{{\text{max}}}}^{M}$. При любом $M \geqslant 1$ значение максимальной вероятности ошибки равно $\varepsilon _{{\max }}^{M} = (c - 1)min_{{i = 1}}^{c}P({{\omega }_{i}})$.

Уменьшение минимальной вероятности ошибки $\varepsilon _{{\min }}^{M}$ с ростом числа декоррелированных множеств ${{{\mathbf{X}}}_{m}},m = 1,...,M$, имеет формальное объяснение. Пусть множество ${{{\mathbf{X}}}_{1}}$ обеспечивает наибольшую среднюю взаимную информацию $I({{{\mathbf{X}}}_{1}};\Omega ) = \max _{{m = 1}}^{M}I({{{\mathbf{X}}}_{m}};\Omega )$.

С учетом симметрии средней взаимной информации имеем

где Декорреляция источников предполагает строгую положительность условной средней взаимной информации $I(\Omega ;{{{\mathbf{X}}}_{m}}\,{\text{|}}\,{{{\mathbf{X}}}_{{m - 1}}}...{{{\mathbf{X}}}_{1}}) > 0,$ $m = 2,...,M$, и, следовательно, увеличение средней взаимной информации $I({{{\mathbf{X}}}^{M}};\Omega )$ и уменьшение условной энтропии $H(\Omega \,{\text{|}}\,{{{\mathbf{X}}}^{M}}) = H(\Omega ) - I({{{\mathbf{X}}}^{M}};\Omega )$ с ростом $M$. Поэтому из (11) и (12) следует, что увеличение числа декоррелированных источников приводит к уменьшению $\varepsilon _{{\min }}^{M}$.

Характер границ $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} _{M}^{{}}(\varepsilon )$ при значениях $M \geqslant 1$ показан на фиг. 2 сплошными кривыми. Для сравнения дана точечная кривая нижней границы Шеннона.

5. УСЛОВНЫЕ ПО КЛАССАМ РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ ОБЪЕКТОВ

Вычисление средней взаимной информации $I({\mathbf{X}};\Omega )$, которая используется в нижней границе ${{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} }_{M}}(\varepsilon )$, требует знания совместного распределения вероятностей $\{ P({{\omega }_{i}},{\mathbf{x}}) = P({{\omega }_{i}})P({\mathbf{x}}\,{\text{|}}\,{{\omega }_{i}}),\;\forall {\mathbf{x}} \in {\mathbf{X}},$ $i = 1,...,c\} $ на произведении $\Omega \times {\mathbf{X}}$. Априорные вероятности считаются известными, а условные по классам вероятности могут быть определены с помощью метрики $d({\mathbf{x}},{\mathbf{\hat {x}}}) \geqslant 0{\text{ }}$ в ${{L}_{p}},p \geqslant 1$, для любой пары объектов ${\mathbf{x}} \in {\mathbf{X}},$ ${\mathbf{\hat {x}}} \in {\mathbf{X}}$.

Полагая, что ${{{\mathbf{x}}}_{i}} \in {{{\mathbf{X}}}_{i}},i = 1,...,c$, являются “центрами” непересекающихся кластеров ${{{\mathbf{X}}}_{i}}:\bigcup\nolimits_{i = 1}^c {{{{\mathbf{X}}}_{i}}} = {\mathbf{X}}$ и объекты каждого класса обладают свойством компактности, определим условные по классам вероятности

с параметрами ${{{v}}_{i}} > 0,$ $i = 1 = 1,...,c$. Параметры распределений (15) могут быть оценены с использованием расстояний между объектами из ${\mathbf{X}}$ и “центрами” которые обеспечивают наименьшие рассеяния объектов внутри кластеров.

Для нахождения параметров ${{v}_{i}},i = 1,...,c$, воспользуемся плотностями распределения

случайных величин ${{\theta }_{i}} = d({\mathbf{x}},{{{\mathbf{x}}}_{i}})$. Используя плотность $p({{\theta }_{i}})$ и требуя максимума вероятности значений ${{\theta }_{i}}$ в ${{\alpha }_{i}}$-окрестности среднего значения ${{\mu }_{i}} > 0$ (указанная вероятность выражена в терминах неполных гамма-функций), получаем где $0 < {{\alpha }_{i}} < 1$.

Параметры ${{\mu }_{i}}$ и ${{\alpha }_{i}}$ в (17) определяются статистиками внутриклассовых расстояний $d({\mathbf{x}},{{{\mathbf{x}}}_{i}})$ в виде выборочных средних

и выборочных дисперсий Используя величины вычисляются значения $\alpha _{i}^{{}} = \alpha _{i}^{*} + 2(1 - \alpha _{i}^{*}){{\tau }_{s}} - (1 - \alpha _{i}^{*})\tau _{s}^{2} < 1$ в точках ${{\tau }_{s}} = \sum\nolimits_{k = 1}^s {{{2}^{{ - k}}}} ,$ $s = 1,2,...$, и соответствующие растущие значения параметра ${{v}_{i}}$ вида (17) и $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} ({{\varepsilon }_{{\max }}}) < 0$ до выполнения условия $\left| {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} ({{\varepsilon }_{{\max }}})} \right| \leqslant \delta $ при достаточно малом пороге δ, когда μ_i ≥ σ_i. Для вычисления значений $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} ({{\varepsilon }_{{\max }}})$ используются асимптотические оценки ${{\varepsilon }_{{\min }}}$ вида (11). Истинное значение ${{\varepsilon }_{{\min }}}$ вычисляется коррекцией оценки ${{\varepsilon }_{{\min }}}$ при наибольшем значении ${{v}_{i}}$ путем сдвига вправо до достижения равенства $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} ({{\varepsilon }_{{\max }}}) = 0$.

Полученные на множествах объектов от различных источников вероятности (15) с учетом оценок (16) и (17) порождают условные по классам распределения

на множествах ${{{\mathbf{X}}}_{m}},m = 1,...,M$, и условные по классам распределения на ансамбле ${{{\mathbf{X}}}^{M}} = {{{\mathbf{X}}}_{1}}...{{{\mathbf{X}}}_{M}}$. Условные распределения (18) и (19) совместно с априорным распределением классов позволяют вычислить среднюю взаимную информацию $I({{{\mathbf{X}}}_{m}};\Omega )$ для каждого источника ${{{\mathbf{X}}}_{m}},m = 1,...,M$, и среднюю взаимную информацию$I({{{\mathbf{X}}}^{M}};\Omega )$ для ансамбля источников ${{{\mathbf{X}}}^{M}} = {{{\mathbf{X}}}_{1}}...{{{\mathbf{X}}}_{M}}$ и, следовательно, получить численные реализации нижней границы вида (14) при значениях $M \geqslant 1.$

6. ЭКСПЕРИМЕНТАЛЬНЫЕ СООТНОШЕНИЯ “ВЗАИМНАЯ ИНФОРМАЦИЯ–ВЕРОЯТНОСТЬ ОШИБКИ” ДЛЯ МНОЖЕСТВА ПОДПИСЕЙ, МНОЖЕСТВА ЛИЦ И ДЛЯ АНСАМБЛЯ ЭТИХ ИСТОЧНИКОВ

В численном эксперименте использованы множества подписей и лиц, заданные полутоновыми изображениями размера 256 × 256 с 8-битовым кодированием элементов. Каждое изображение содержит один информативный объект (лицо или подпись). Множества лиц и подписей содержат по 1000 объектов от 25 персон ($c = 25$), по 40 реализаций от каждой персоны. Априорное распределение классов принято равномерным. Информативные объекты заданы древовидными представлениями в виде структурированных наборов эллиптических примитивов [9]. Различие любой пары объектов на множестве их древовидных представлений определяется расстоянием в метрике ${{L}_{p}},p \geqslant 1$, которое является модификацией расстояния в метрике ${{L}_{1}}$, введенного в [9]. Цель вычислительного эксперимента состояла в получении реализаций границы $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} (\varepsilon )$ на множестве лиц и множестве подписей с использованием матриц расстояний, заданных ресурсами [10] и [11], а также в вычислении границы $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} _{M}^{{}}(\varepsilon )$ на ансамбле этих источников.

Примеры древовидных представлений подписи и лица даны на фиг. 3. Информативные уровни $l = 1,...,8$ представлений содержат по ${{2}^{l}}$ эллиптических примитивов. Параметры примитива нулевого уровня используются для нормировки параметров примитивов последующих уровней. Нормированные примитивы всех уровней задаются в собственных координатных осях примитива нулевого уровня и имеют номера соответствующих им вершин бинарного дерева. Построение примитивов в собственных осях нулевого уровня и нормировка параметров примитивов обеспечивают инвариантность представлений к сдвигу, повороту, масштабу и уровню яркости объектов. Приведенные представления могут быть построены для любого объекта, заданного на изображении односвязным или многосвязным набором пикселей, который имеет идентифицируемые собственные оси.

В соответствии с выбранным способом представления, объект ${\mathbf{x}} \in {\mathbf{X}}$ преобразуется в набор эллиптических примитивов

образующих бинарное дерево глубины $L$. Глубина дерева определяется наибольшим уровнем разрешения; эллиптический примитив ${{\operatorname{E} }_{n}}$ соответствует $n$-й вершине дерева и определяется вектором центра ${{{\mathbf{r}}}_{n}}$, векторами большой и малой полуосей ${{{\mathbf{u}}}_{n}},{\text{ }}{{{\mathbf{v}}}_{n}}$ и средней яркостью ${{z}_{n}}$ фрагмента, аппроксимируемого примитивом. Номера вершин формируются согласно правилу: каждая промежуточная вершина с номером $n$ порождает пару вершин следующего уровня с номерами $2n + 1,$ $2n + 2$; вершина нулевого уровня имеет номер $n = 0$. При указанной нумерации примитив ${{\operatorname{E} }_{n}}$ с номером $n$ находится в дереве на уровне $l = \left\lfloor {{{{\log }}_{2}}(n + 1)} \right\rfloor $.

Используя представления вида (20), введем на множестве ${\mathbf{X}}$ расстояние в метрике ${{L}_{p}},p \geqslant 1$, между любой парой объектов ${\mathbf{x}} \in {\mathbf{X}}$ и ${\mathbf{\hat {x}}} \in {\mathbf{\hat {X}}}$. Примитивы ${{\operatorname{E} }_{n}} \in {{{\mathbf{x}}}^{L}}$ и ${{\hat {E}}_{n}} \in {{{\mathbf{\hat {x}}}}^{L}}$ с одинаковыми номерами будем считать соответственными, так что множество пар $({{\operatorname{E} }_{n}},{{\hat {E}}_{n}})$ образует пересечение ${{{\mathbf{x}}}^{L}} \cap {{{\mathbf{\hat {x}}}}^{L}}$. На пересечении любой пары представлений ${{{\mathbf{x}}}^{L}}$ и ${{{\mathbf{\hat {x}}}}^{L}}$ определим их $p$-степенные различия по векторам центров $({{{\mathbf{r}}}_{n}},{{{\mathbf{\hat {r}}}}_{n}})$, векторам полуосей $({{{\mathbf{u}}}_{n}},{{{\mathbf{\hat {u}}}}_{n}})$, $({{{\mathbf{v}}}_{n}},{{{\mathbf{\hat {v}}}}_{n}})$ и уровням яркости$({{z}_{n}},{{\hat {z}}_{n}})$:

где есть вес $n$-й пары соответственных примитивов. Введенные различия дают средние значения на множестве объектов ${\mathbf{X}}$ относительно объекта ${\mathbf{\hat {x}}} \in {\mathbf{X}}$. Указанные характеристики позволяют ввести расстояние в метрике ${{L}_{p}},p \geqslant 1$, между объектами ${\mathbf{x}}$ и ${\mathbf{\hat {x}}}$ в форме

Расстояния  вида  (21) на множествах ${{{\mathbf{X}}}_{m}},m = 1,...,M$, совместно с представителями классов (16) и оценками параметров (17) полностью определяют для указанных источников условные по классам распределения вида (18), а также условные по классам распределения вида (19) для ансамбля этих источников. В экспериментах использованы расстояния в метрике ${{L}_{p}}$ с параметром $p = 1$ и $p = 2$.

Графики границ $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} _{M}^{{}}(\varepsilon )$, вычисленных на множестве лиц ${{{\mathbf{X}}}_{1}}$ и множестве подписей ${{{\mathbf{X}}}_{2}}$, а также на ансамбле ${{{\mathbf{X}}}_{1}}{{{\mathbf{X}}}_{2}}$, даны на фиг. 4. Для сравнения приведена точечная кривая нижней границы Шеннона. Графики демонстрируют существенное уменьшение минимальной вероятности ошибки на ансамбле по сравнению с аналогичными вероятностями ошибки на множествах лиц или подписей. Необходимо отметить, что для рассматриваемых источников расстояние в метрике ${{L}_{2}}$ обеспечивает возможность достижения большей точности по сравнению с расстоянием в метрике ${{L}_{1}}$.

7. ИЗБЫТОЧНОСТЬ ВЕРОЯТНОСТИ ОШИБКИ РЕШАЮЩЕГО АЛГОРИТМА

Полученная нижняя граница ${{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} }_{M}}(\varepsilon )$ позволяет оценить избыточность вероятности ошибки алгоритма, принимающего решения по блокам ${{{\text{X}}}^{{MN}}}$ из $N \geqslant 1$ объектов ($M \geqslant 1$) с использованием набора разделяющих функций

Разделяющие функции дают значения правдоподобия решений ${{\omega }_{j}} \in \hat {\Omega },$ $j = 1,...,c$, по предъявляемому блоку ${{{\text{X}}}^{{MN}}}$ и позволяют минимизировать вероятность ошибки при использовании решающего правила $j{\kern 1pt} * = \arg \max _{{j = 1}}^{c}g_{j}^{{}}({{{\text{X}}}^{{MN}}})$. В общем случае разделяющие функции отличаются от апостериорных вероятностей, поэтому реализуемая на них вероятность ошибки превосходит минимальную вероятность ошибки байесовского алгоритма.

Решающее правило на наборе разделяющих функций ${\text{G}}$ порождает разбиение множества ${{{\mathbf{X}}}^{{MN}}}$ на непересекающиеся области решений ${\mathbf{X}}_{j}^{{MN}} \to {{\omega }_{j}},$ $j = 1,...,c$, которые имеют вероятности

Тогда набор ${\text{G}}$дает энтропию множества решений и вероятность ошибки где

есть оценка апостериорной вероятности решения ω_j по блоку составных объектов X^MN.

Cогласно теореме кодирования [1] справедливо неравенство ${{H}_{\operatorname{G} }} \geqslant {{R}_{M}}({{\varepsilon }_{\operatorname{G} }})$. Тогда пара ${{H}_{\operatorname{G} }},\;{{\varepsilon }_{\operatorname{G} }}$ позволяет ввести избыточность ${{r}_{\operatorname{G} }} = {{\varepsilon }_{\operatorname{G} }} - \varepsilon $ вероятности ошибки ${{\varepsilon }_{\operatorname{G} }}$ относительно значения

где $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} _{M}^{{ - 1}}({{H}_{\operatorname{G} }})$ – значение обратной функции от нижней границы ${{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} }_{M}}(\varepsilon ) = {{H}_{\operatorname{G} }}$.

В случае принятия решений по блокам объектов длины $N \geqslant 1$, наименьшая вероятность ошибки ${{\varepsilon }_{\operatorname{G} }}$ реализуется на байесовском алгоритме, разделяющие функции которого дают апостериорные вероятности $P({{\omega }_{j}}\,{\text{|}}\,{{{\text{X}}}^{{MN}}}),$ $j = 1,...,c$ (см. [8]). В этом случае ${{H}_{\operatorname{G} }} \geqslant I({{{\mathbf{X}}}^{M}};\Omega )$ и избыточность ${{r}_{\operatorname{G} }} = {{\varepsilon }_{\operatorname{G} }} - \varepsilon _{{\min }}^{M} \geqslant 0$. При оптимальной длине блоков $N = N{\kern 1pt} *$ байесовский алгоритм достигает минимальной вероятности ошибки $\varepsilon _{{\min }}^{M}$ и обеспечивает нулевую избыточность.

8. ЗАКЛЮЧЕНИЕ

Исследована теоретико-информационная модель классификации данных, для которой введено обменное соотношение между наименьшей средней взаимной информацией множества классифицируемых объектов относительно множества решений по классам и заданной допустимой вероятностью ошибки. Соотношение “взаимная информация–вероятность ошибки” определено для заданного источника данных и для ансамбля источников, и является аналогом известной в теории информации функции “скорость–погрешность” (rate distortion function) для модели кодирования с заданной точностью при наличии канала наблюдения с шумом. Построена нижняя граница функции “взаимная информация–вероятность ошибки”, которая является обобщением нижней границы Шеннона. Полученная граница зависит от априорного распределения классов и условных по классам распределений на заданном множестве объектов и не зависит от решающего алгоритма. При любом фиксированном значении средней взаимной информации нижняя граница функции “взаимная информация–вероятность ошибки” дает потенциально достижимую вероятность ошибки классификации по объектам источника или по составным объектам от ансамбля источников. Показана возможность оценивания избыточности вероятности ошибки относительно нижней границы для решающего алгоритма с заданным набором разделяющих функций. Предложенная методика вычисления избыточности позволяет оценить качество любых разделяющих функций, построенных независимо от априорных вероятностей классов и условных по классам распределений предъявляемых объектов.