Место издания:Изд-во ГОУ ВПО "Восточно-Сибирская государственная академия образования" Иркутск
Первая страница:28
Последняя страница:32
Аннотация:В [1] были исследованы полиномиальные замыкания различных семейств алгоритмов распознавания (классификации),
что положило начало развитию алгебраического подхода к решению задач распознавания.
Идея алгебраического подхода заключается в ведении операций над алгоритмами распознавания (классификации)
и поиске корректного алгоритма (который не делает ошибок на контрольной выборке) в виде алгебраического
выражения. Было доказано (см. [1]), что корректный алгоритм может быть записан в виде
полинома над алгоритмами вычисления оценок. Алгоритмы вычисления оценок (АВО)
были предложены в [2] как некоторая универсальная модель алгоритмов, по отношению
к которой многие другие модели являются подмоделями при специальных ограничениях на значения параметров.
Корректные алгоритмы-полиномы в [1] имели степень асимптотически равную $q\log q$, где $q$ "---
число объектов контрольной выборки задачи классификации. В [3] получена первая нетрививальная
оценка на степень корректного полинома: $k \le q + l - 2$, где $k$ "--- степень полинома, $l$ "--- число классов в задаче классификации,
которая была значительно улучшена в [4]: $k \le
\lfloor\log _2 (ql)\rfloor$ (здесь и далее скобками $\lfloor\,\rfloor$ обозначается
<<целая часть снизу>>). В [5] получена окончательная (непонижаемая в общем случае) оценка
$k \le \lfloor\log _2 q\rfloor + \lfloor\log _2 l\rfloor$.
В настоящей работе представлены оценки для подмоделей модели АВО.