Оценки степени корректных полиномиальных замыканий подмоделей модели АВОстатья

Работа с статьей


[1] Дьяконов А. Г. Оценки степени корректных полиномиальных замыканий подмоделей модели АВО // Синтаксис и семантика логических систем: Материалы 3-й Российской школы-семинара, посвященной 80-летию со дня рождения А. И. Кокорина (Иркутск, 10-14 августа 2010 г.). — Т. 10. — Изд-во ГОУ ВПО "Восточно-Сибирская государственная академия образования" Иркутск, 2010. — С. 28–32. В [1] были исследованы полиномиальные замыкания различных семейств алгоритмов распознавания (классификации), что положило начало развитию алгебраического подхода к решению задач распознавания. Идея алгебраического подхода заключается в ведении операций над алгоритмами распознавания (классификации) и поиске корректного алгоритма (который не делает ошибок на контрольной выборке) в виде алгебраического выражения. Было доказано (см. [1]), что корректный алгоритм может быть записан в виде полинома над алгоритмами вычисления оценок. Алгоритмы вычисления оценок (АВО) были предложены в [2] как некоторая универсальная модель алгоритмов, по отношению к которой многие другие модели являются подмоделями при специальных ограничениях на значения параметров. Корректные алгоритмы-полиномы в [1] имели степень асимптотически равную qlogq, где q "— число объектов контрольной выборки задачи классификации. В [3] получена первая нетрививальная оценка на степень корректного полинома: kq + l - 2, где k "— степень полинома, l "— число классов в задаче классификации, которая была значительно улучшена в [4]: k ≤ ⌊log_2 (ql)⌋ (здесь и далее скобками ⌊⌋ обозначается <<целая часть снизу>>). В [5] получена окончательная (непонижаемая в общем случае) оценка k ≤⌊log_2 q⌋+ ⌊log_2 l⌋. В настоящей работе представлены оценки для подмоделей модели АВО.

Публикация в формате сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл скрыть