Обсуждение:Прогнозирование формы множества

Материал из MachineLearning.

Версия 13:43, 12 июля 2010

Первое впечатление

Yet Another Classifier. Во всём мире специалисты по Machine Learning давно сошлись во мнении, что изобретение очередных «универсальных» (и по любому эвристических!) методов классификации лишено смысла. Уже есть тысячи методов, и простым комбинированием известных идей можно изобрести ещё миллионы. Один из них и предложен в данной статье.

Есть ещё одно популярное мнение. Практически любую изначально разумную эвристику можно довести до «мирового уровня», если тщательно её поисследовать, выявить причины недостатков и устранить их с помощью десятка «вспомогательных эвристик», попросту говоря, «костылей» и «заплаток». Такая доводка требует большого труда и времени. Вопрос: имеют ли смысл трудозатраты на изобретение велосипеда, если можно взять любой готовый «универсальный» метод, скажем, нейронную сеть, машину опорных векторов, бустинг над решающими деревьями, и т.д.

Такая работа обычно имеет смысл, если в основе метода лежит удачная, простая и красивая математика. Например, в бустинге и в SVM она есть, и это определило «удачность» и популярность этих методов. Наличие изящной математической идеи позволяет достаточно далеко продвинуться в теоретическом понимании метода. Если же метод слишком громоздкий или основан на эклектичном наборе эвристик (IMHO что и имеет место быть в данной статье), то его теоретическое исследование будет сильно затруднено, совершенствовать его придётся чисто эмпирически, путём проб и ошибок. У автора может просто не хватить времени, сил, энтузиазма на доведение своей задумки до конкурентоспособного уровня.

Несколько мелких замечаний:

• необходимо расставить запятые согласно правилам русской пунктуации;
• стиль оставляет желать лучшего («классическую задачу классификации», «формы множеств», «прогнозирования множества всех возможных объектов с ассоциированными классами», и многое другое);
• «Если признаки бинарные то можно выбрать в качестве мета-признака элементарную дизъюнкцию» — может, всё-таки, конъюнкцию, раз выше речь шла о пересечении?
• без строгой математической постановки задачи довольно трудно понять, что же всё-таки предлагается;
• построение алгоритмов классификации на основе ДНФ и КНФ было предложено многими авторами лет 40–50 назад, в частности, академиком Ю. И. Журавлёвым; в чём отличие предлагаемого метода?
• зачем использовать триангуляцию Делоне? наверняка можно сделать попроще, и работать будет не хуже;
• предлагаемый метод вызывает кучу ассоциаций и с байесовским классификатором, и с методом потенциальных функций, и с композициями типа бустинга, и с дискретно-логическими алгоритмами; не понятно, почему он должен быть лучше других;
• не думаю, что автору удастся решить проблему стремительной потери эффективности при увеличении размерности.

— К.В.Воронцов 17:42, 11 июля 2010 (MSD)

В ближайшем будущем постараюсь доработать статью чтобы ввести более строгую математику.

По поводу простой математической идеи. Мне сложно пока ее сформулировать, у меня есть только филосовские рассуждения. Когда удалось найти этот метод, первая моя цель была в формализации гипотезы компактности. Я думал о том что если все множества компактны то как правильно нужно строить их модель. Я решил поменять немного взгяд на гипотезу компактности - рассматривать модель источника - как он формирует компактные множества. Можно допустить что у него есть какойто алгоритм основанный на операциях над какимито стандартными множествами. Оставалось определить какие операции и какие эти стандартные множества. Я решил рассматривать операции объединения и пересечения - между ними большой разницы нет потому что они двойственны - смотря что мы моделируем множество либо отрицание множества. Выбор стандартных множеств определяет способность источника формировать компактные множества. Вот несколько мыслей по поводу стандартных множеств:

• стандартных множеств не может быть бесконечное количество (на каждый случай формы множества объектов (класса)),
• чем меньше требуется стандартных множеств для описания множества объектов (класса) тем больше это множество статистически зависимо от этих стандартных множеств,
• необходимо такие стандартные множества чтобы классы вселенной чаще всего описывались наименьшим набором стандартных множеств - это будет означать что классы вселенной имеют наибольшую статистическую зависимость от данного пространства стандартных множеств,
• пространство стандартных множеств должно иметь максимальную прогнозирующую способность формы классов вселенной, или другими словами - если множество было образовано путем объединения (пересечения) набора стандартных множеств то скорее всего понадобится бОльший набор множеств, из другого набора стандартных множеств, для формирования этого множества.

По поводу математики в основе метода. Бинарный случай. Если источник имеет набор "трафаретов" - элементарные дизъюнкции и формирует множества путем их пересечения - КНФ, то задачей нахождения КНФ на основе ДНФ (обучающей выборки) мы пытаемся смоделировать поведение источника. Этот момент мне пока сложно выразить формально - это чтото близкое к методу максимального правдоподобия. Когда мы получаем КНФ, вычисление вероятности эквивалентно вычислению информативности имеющихся мета-признаков у точки. Информативность имеющихся метапризнаков у точки - оценка условной вероятности того что из множества точек, описанным данным набором мета-признаков, будет обнаружена точка принадлежащая множеству точек класса. Формализация вычисления вероятности тут не сложна. Вещественный случай. Формализация этого метода у меня вызвала затруднения. Основной мой вариант формализации это переход от бинарного случая. Отрицание гиперсферы очень похоже на элементарную дизъюнкцию - можно описывать множества путем их пересечений. Триангуляция Делоне дает нам минимальный набор отрицаний гиперсфер для описание множества точек в непрерывном пространстве если не принимать во внимание проблему бесконечного окружающего пространства. Главные проблемы в формализации: простарнство бесконечно, точка имеет нулевую площадь. Я интуитивно определил распределение как смесь нормальных распределений. Я уверен что тот кто владеет хорошо предельным переходом сможет доказать что мой вариант близок к истине.

Главное отличие от алгоритмов классификации на основе ДНФ и КНФ, которые были предложены авторами 40–50 назад, заключается в том что мы строим модель множества с использованием "трафаретов" элементарных компактных множеств в предположении что именно они обеспечивают наибольщую статистическую зависимость со встречаемыми множествами во вселенной.

Я выбрал триангуляцию Делоне для поиска теоретического решения проблемы, поскольку я рассматриваю этот вариант как правильный. Практическую реализацию я сделал для того чтобы искать подсказки в построении математики метода.

У меня есть несколько потенциальных вариантов решения проблемы стремительной потери эффективности при увеличении размерности. У меня есть подозрение что нельзя упрощать распределение полученное в виде смеси нормальных распределений после триангуляуции Делоне, потому в таком случае мы будем терять точность прогноза. Основным направлением тут может быть сокращение размерности. Например при распознавании изображений можно построить иерархический классификатор, в котором будет первоначальная кластеризация признаков, потом переход в новое пространство признаков и последующая классификация. Еще один экзотический вариант рассматривать объект, в метрическом пространстве, не как точку а как множество точек в пространстве меньшей размерности.

— А.С.Солодухин 13:50, 12 июля 2010 (MSD)