Laboratory of Structural Methods of Data Analysis in Predictive
Modeling Moscow Institute of Physics and Technology
ENG
Логин:
Пароль:
Реализация булевых функций с ограниченным числом нулей в классе дизъюнктивных нормальных форм
Исследованы вопросы сложности булевых классификаторов, основанных на представлении функций \Sigma\Pi и \Pi\Sigma схемами. Исследованы вопросы связанные с вопросами сложности обучения дизъюнктивных нормальных форм (ДНФ) в модели вероятностно почти корректного обучения (PAC learning, probability approximately correct learning) предложенной Prof. Leslie Valiant.
В работах Li, Tromp, Vitanyi с исользованием понятий Колмогоровской сложности было показано, что вопрос существования алгоримов Окамма(Occam algorithms) и вопрос полиномиальной обучаемости ДНФ в PAC модели, тесно связан с оценками сложности в задаче The DNF Exception Problem(Mubayi, Turan, Zhao). В наших работах рассмотрены оценки сложности в задаче The DNF Exception Problem при различных (классических) ограничениях на ее входные данные.

Авторы: Maximov Yury

Дата: 17 ноября 2014

Статус: в печати

Журнал: Журнал вычислительной математики и математической физики

Том: 53

Выпуск: 9

Страницы: 132-151

Год: 2013

Google scholar:

Направления исследований

Statistical methods