Вероятностные алгоритмы поиска сходств и GOFAI

В докладе будет представлен обзор работ автора по вероятностно-комбинаторному формальному методу (ВКФ-методу) обучения, основанному на теории решеток. Мы начнем с примера правдоподобных рассуждений (включающих обобщение по индукции, рассуждение по аналогии и абдукцию). Также кратко будет рассказано о фантомных гипотезах — механизме переобучения в этом подходе.
После краткого пояснения основных идей Анализа формальных понятий мы представим вероятностный алгоритм поиска случайного подмножества сходств обучающих примеров, основанного на спаривающих цепях Маркова. Обоснование необходимости вероятностного взгляда обосновывается теоремой об экспоненциальном числе сходств (в худшем случае) для плотных обучающих выборок.
Будет приведена теорема о полиномиальном числе случайных сходств в вероятно приближенно-корректном обучении (PAC-learning). Из-за сильного завышения теоретических оценок в качестве практической альтернативы используется метод минимизации эмпирического риска В.Н.Вапника-А.Я.Червоненкиса (мы обсудим его близкую связь с процедурой абдукции).
Будет сформулирована теорема о полиномиальной средней длине траектории спаривающей цепи Маркова (для дихотомизированных обучающих выборок), что обеспечивает полиномиальность общей схемы вычислений ВКФ-метода. Для частных случаев булевой алгебры и линейного порядка будут приведены точные результаты о средней длине траекторий.