ИСТИНА |
Войти в систему Регистрация |
|
ИПМех РАН |
||
В [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$. В настоящей работе представлены оценки для подмоделей модели АВО.