|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Оценки степени корректных полиномиальных замыканий подмоделей модели АВОстатья
- Автор: Дьяконов А.Г.
- Сборник: Синтаксис и семантика логических систем: Материалы 3-й Российской школы-семинара, посвященной 80-летию со дня рождения А. И. Кокорина (Иркутск, 10-14 августа 2010 г.)
- Том: 10
- Год издания: 2010
- Место издания: Изд-во ГОУ ВПО "Восточно-Сибирская государственная академия образования" Иркутск
- Первая страница: 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$. В настоящей работе представлены оценки для подмоделей модели АВО.
- Добавил в систему: Дьяконов Александр Геннадьевич