Редактирование: МОТП, Билеты (2009)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
= Часть 1 (Ветров) = | = Часть 1 (Ветров) = | ||
- | == | + | == Линейная регрессия == |
- | + | http://www.nsu.ru/mmf/tvims/chernova/ms/lec/node60.html | |
- | + | ||
- | + | == Скрытая марковская модель == | |
- | + | [http://ru.wikipedia.org/wiki/%D0%A1%D0%BA%D1%80%D1%8B%D1%82%D0%B0%D1%8F_%D0%BC%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D1%8C На википедии] | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | == | + | == Байесовская сеть == |
- | + | [http://ru.wikipedia.org/wiki/%D0%91%D0%B0%D0%B9%D0%B5%D1%81%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%B5%D1%82%D1%8C_%D0%B4%D0%BE%D0%B2%D0%B5%D1%80%D0%B8%D1%8F На википедии] | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
= Часть 2 (Рудаков) = | = Часть 2 (Рудаков) = | ||
Строка 318: | Строка 21: | ||
''' Детерминированные признаки''' – это признаки, принимающие конкретные числовые значения, которые могут быть рассмотрены как координаты точки, соответствующей данному объекту, в n-мерном пространстве признаков. | ''' Детерминированные признаки''' – это признаки, принимающие конкретные числовые значения, которые могут быть рассмотрены как координаты точки, соответствующей данному объекту, в n-мерном пространстве признаков. | ||
- | |||
- | '''Вероятностные признаки''' – это признаки, случайные значения которых распределены по всем классам объектов, при этом решение о принадлежности распознаваемого объекта к тому или другому классу может приниматься только на основании конкретных значений признаков данного объекта, определенных в результате проведения соответствующих опытов. Признаки распознаваемых объектов следует рассматривать как вероятностные и в случае, если измерение их числовых значений | ||
- | производится с такими ошибками, что по результатам измерний невозможно с полной определенностью сказать, какое числовое значение данная величина приняла. | ||
- | |||
- | '''Логические признаки''' распознаваемых объектов можно рассматривать как элементарные высказывания, принимающие два значения истинности (истина – ложь) с полной определенностью. К логическим признакам относятся прежде всего признаки, не имеющие количественного выражения. Эти признаки представляют собой суждения качественного характера типа наличия или отсутствия некоторых свойств или некоторых элементов у распознаваемых объектов или явлений. В качестве логических признаков можно рассматривать, например, такие симптомы в медицинской диагностике, как боль в горле, кашель и т.д. К логическим можно отнести также признаки, у которых важна не величина признака у распознаваемого объекта, а лишь факт попадания или непопадания ее в заданный интервал. В пределах этих интервалов появление различных значений признаков у распознаваемых объектов предполагается равновероятным. На практике логические признаки подобного рода имеют место в таких ситуациях, когда либо ошибками измерений можно пренебречь, либо интервалы значений признаков выбраны таким образом, что ошибки измерений практически не оказывают влияния на | ||
- | достоверность принимаемых решений относительно попадания измеряемой величины в заданный интервал. | ||
- | |||
- | |||
- | '''Решающее правило''' | ||
- | Decision Rule | ||
- | |||
- | В Data Mining это правила вида «Если …, то…», которые позволяют принять решение о принадлежности объекта или наблюдения к определенному классу, например, «Если ‘Годовой доход’ больше 200000, то ‘Кредитный рейтинг’ = ‘Высокий’. Основное применение решающих правил – деревья решений. В каждом узле дерева решений содержится решающее правило, разбивающее множество примеров в узле на подмножества, ассоциированные с классами. | ||
- | |||
- | Кроме этого, решающие правила применяются в методах покрытия, когда формируются наборы правил, которые последовательно относятся ко всем наблюдениям. | ||
- | |||
- | |||
- | Остаток можно взять из файла lekcii_ama_zhuravlev.doc страница 17. | ||
== Проблемы формирования логических признаков. Оценки качества признаков и их совокупностей. == | == Проблемы формирования логических признаков. Оценки качества признаков и их совокупностей. == | ||
- | |||
- | Пусть <math>\varphi : X \rightarrow \{0, 1\}</math> - некоторый предикат, определённый на множестве объектов X. Говорят, что предикат <math>\varphi</math> <u>''выделяет''</u> или <u>''покрывает''</u> (cover) объект x, если | ||
- | <math>\varphi(x) = 1</math>. Предикат называют <u>''закономерностью''</u>, если он выделяет достаточно много объектов какого-то одного класса <math>c</math>, и практически не выделяет объекты других классов. | ||
- | |||
- | Пример: Решается вопрос о целесообразности хирургической операции. Закономерность: если возраст пациента выше 60 лет и ранее он перенёс инфаркт, то операцию не делать - риск отрицательного исхода велик. | ||
- | |||
- | Всякая закономерность классифицирует лишь некоторую часть объектов. Объединив определённое количество закономерностей в композицию, можно получить | ||
- | алгоритм, способный классифицировать любые объекты. <u>''Логическими алгоритмами классификации''</u> будем называть композиции легко интерпретируемых закономерностей. При построении логических алгоритмов возникают три основных вопроса: | ||
- | * Каков критерий информативности, позволяющий называть предикаты закономерностями? | ||
- | * Как строить закономерности? | ||
- | * Как строить алгоритмы классификации на основе закономерностей? Наиболее распространённые типы логических алгоритмов: Голосование правил (алгоритм Кора), Алгоритмы вычисления оценок. | ||
- | |||
- | Теперь поговорим об '''информативности''' (или качестве) признака. | ||
- | Своими словами: предикат <math>\varphi</math> тем более информативен, чем больше он выделяет объектов "своего класса" <math>c \in Y</math> по сравнению с объектами всех остальных "чужих" классов. Свои объекты называют также <u>''позитивными''</u> (positive), а чужие <u>''негативными''</u> (negative). Введём следующие обозначения: | ||
- | * <math>P_c</math> - число объектов класса c в выборке X | ||
- | * <math>p_c(\varphi)</math> - из них число объектов, для которых выполняется условие <math>\varphi(x) = 1</math>; | ||
- | * <math>N_c</math> - число объектов всех остальных классов Y \ {c} в выборке X | ||
- | * <math>n_c(\varphi)</math> - из них число объектов, для которых выполняется условие <math>\varphi(x) = 1</math> | ||
- | |||
- | Введем ещё два обозначения: | ||
- | * <math>E_c ( \varphi , X ) = \frac {n_c(\varphi)}{p_c(\varphi)+ n_c(\varphi)}</math> - <u>''доля негативных объектов''</u> среди всех выделяемых объектов (доля тех объектов, в которых наш логический предикат ошибся - причислил их к "своему" классу, хотя они туда и не относились) | ||
- | * <math>D_c ( \varphi , X ) = \frac {p_c(\varphi)}{l}</math>, где l есть это количество элементов в выборке X - это <u>''доля выделенных позитивных объектов''</u>. | ||
- | |||
- | Существует несколько способов определения информативности: статическое определение, энтропийное. Также существует такое понятие как ''многоклассовая информативность'', когда приходится оценивать информативность не только таких предикатов, которые отделяют один класс от остальных, но и таких, которые отделяют некоторую группу классов от остальных. | ||
== Методы голосования по конъюнкциям. Алгоритмы типа "Кора". == | == Методы голосования по конъюнкциям. Алгоритмы типа "Кора". == | ||
- | |||
- | Для начала, поговорим об '''алгоритмах голосования'''. Пусть для каждого класса <math>c \in Y</math> построено множество логических закономерностей (правил), специализирующихся на различении объектов данного класса: | ||
- | <math>R_c = \{ \varphi_c^t : X \rightarrow \{0, 1\} | t = 1, . . . , T_c\}</math>, где <math>T_c</math> - количество классов свойств. | ||
- | |||
- | Считается, что если <math>\varphi_c^t (x) = 1</math>, то правило <math>\varphi_c^t</math> относит объект <math>x \in X</math> к классу c. Если же <math>\varphi_c^t(x) = 0 </math>, то правило <math>\varphi_c^t</math> воздерживается от классификации объекта x. | ||
- | * <u>Алгоритм простого голосования</u> | ||
- | ** подсчитывает долю правил в наборах <math>R_c</math>, относящих объект x к каждому из классов: <math>\Gamma_c(x) = \frac 1 {T_c} \sum_{t=1}^{T_c} \varphi_c^t (x) , c \in Y </math> | ||
- | ** относит объект x к тому классу, за который подана наибольшая доля голосов: <math>a(x) = arg \max_{c \in Y} \Gamma_c (x) </math> | ||
- | ** если максимум достигается одновременно на нескольких классах, выбирается тот, | ||
- | для которого цена ошибки меньше. | ||
- | * <u>Алгоритм взвешенного голосования</u> | ||
- | ** Каждому правилу <math>\varphi_c^t</math> приписывается вес <math>\alpha_t^c \geqslant 0 </math> | ||
- | ** при голосовании берётся взвешенная сумма голосов: <math>\Gamma_c(x) = \frac 1 {T_c} \sum_{t=1}^{T_c} \alpha_t^c \varphi_c^t (x) , c \in Y </math> | ||
- | ** веса принято нормировать на единицу: <math> \sum_{t=1}^{T_c} \alpha_c^t = 1 </math> | ||
- | |||
- | При построении алгоритмов взвешенного голосования правил возникает | ||
- | четыре основных вопроса: | ||
- | * Как построить много правил по одной и той же выборке? | ||
- | * Как избежать повторов и построения почти одинаковых правил? | ||
- | * Как избежать появления непокрытых объектов и обеспечить равномерное покрытие всей выборки правилами? | ||
- | * Как определять веса правил при взвешенном голосовании? | ||
- | |||
- | '''Алгоритм Кора''' | ||
- | * <u>Дано</u> | ||
- | ** множество элементарных предикатов <math>\Beta</math> | ||
- | ** обучающая выборка X | ||
- | * <u>Хотим получить</u> | ||
- | ** набор конъюктивных закономерностей (т.е. множество конъюнкций элементарных предикатов <math>\Beta</math>, которые являлись бы закономерностями для нашей обучающей выборки X) ранга не более чем K (как правило берется число 3) | ||
- | ** доля ошибок <math>E_c ( \varphi ) </math> (см. предыдущий билет) для каждой из полученных конъюнкций не должна превышать <math>E_{max}</math> | ||
- | ** доля позитивных объектов <math>D_c ( \varphi ) </math> для каждой из полученных конъюнкций должна быть не меньше <math>D_{min}</math> | ||
- | * <u>Реализация</u> | ||
- | ** перебираем все возможные конъюнкции ранга от 1 до K методом поиска в глубину: | ||
- | ** в процессе перебора: | ||
- | *** конъюнкция перестает наращиваться (и отбрасывается), если она выделяет слишком мало объектов своего класса, т.е. <math>D_c ( \varphi ) < D_{min} </math> | ||
- | *** конъюнкция перестает наращиваться (и запоминается), если она уже удовлетворяет критериям отбора, т.е. <math>D_c ( \varphi ) > D_{min} </math> и <math>E_c ( \varphi ) < E_{max}</math> | ||
- | * <u>Достоинства алгоритма</u> | ||
- | ** Короткие конъюнкции легко интерпретируются в терминах предметной области. Алгоритм способен не только классифицировать объекты, но и объяснять свои решения на языке, понятном специалистам. | ||
- | ** При малых K (не больше 3) алгоритм очень эффективен | ||
- | ** Если короткие информативные конъюнкции существуют, они обязательно будут найдены, так как алгоритм осуществляет полный перебор. | ||
- | * <u>Недостатки алгоритма</u> | ||
- | ** При неудачном выборе множества предикатов <math>B</math> коротких информативных конъюнкций может просто не существовать. В то же время, увеличение числа K приводит к экспоненциальному падению эффективности. | ||
- | ** Алгоритм не стремится обеспечивать равномерность покрытия объектов. Это отрицательно сказывается на обобщающей способности (вероятности ошибки) алгоритма. | ||
- | |||
- | Пример применения данного алгоритма - motp.pdf, страница 5 | ||
== Тесты, представительные наборы, проблемы перебора. == | == Тесты, представительные наборы, проблемы перебора. == | ||
- | Матрица эталонов <math>T_{nmi}</math>: Каждый столбец соответсвует определенному признаку. Каждая строка - эталонному объекту. Последовательно идущий набор строк - определяет класс. | ||
- | |||
- | Подмножество столбцов матрицы эталонов называется тестом, если в подтаблице, образованной данным подмножеством столбцов, все строки, относящиеся к разным классам, различны. | ||
- | |||
- | Тупиковый тест - минимальная подсистема признаков(столбцов), разделяющая эталонные объекты разных классов. | ||
- | |||
- | Пример - алгоритм Кора, файл motp.pdf 5 страница. Фактически, характеристики классов строятся при помощи тестов. | ||
- | |||
- | Пусть объект <math>S_v \in K_j</math>. Набор признаков <math>u = \{x_{i1}(S_v),..., x_{i_n}(S_v)\}</math> называется <math>\epsilon</math>-представительским (или просто представительским), если <math>\forall S_p \in T_{nmi} </math> и не лежащих в классе <math>K_j</math> система неравенств <math>|x_{i}(S_p) - x_{i}(S_v)|< \varepsilon, i = i_1,...,i_n </math>несовместна. | ||
- | |||
- | Существуют эффективные алгоритмы поиска тупиковых тестов. Тем не менее, задача нахождения множества всех тупиковых тестов является вычислительно сложной комбинаторной задачей и не может быть решена на современных компьютерах даже для относительно небольших таблиц обучения (сотни объектов и признаков). Поэтому при решении практических задач вычисляют и используют в процедурах голосования обычно лишь часть тупиковых тестов. | ||
== Пространства объектов для АВО. Обучающие и контрольные объекты. Метрические описания объектов в АВО. == | == Пространства объектов для АВО. Обучающие и контрольные объекты. Метрические описания объектов в АВО. == | ||
- | |||
- | ''' Алгоритмы вычисления оценок ''' | ||
- | |||
- | <u>Дано:</u> | ||
- | * <math>S = \{s_i\},~~ i \in [1, m]</math> -- множество объектов. ''' обучающая выборка ''' | ||
- | * <math>\| a_{ij} \|_{m \times n}</math> -- совокупность из <math>m</math> объектов, каждый из <math>n</math> признаки | ||
- | * области определения признаков -- метрические пространства <math>M_t</math> с метриками <math>\rho_t:M^2_t \rightarrow \mathbb{R^+},~~ t \in [1, n]</math> | ||
- | * <math>K = \{K_i\}~,~~i \in [1, l]</math> -- можество классов, на которые разделяются объекты | ||
- | * <math>\| \alpha_{ij} \|_{m \times l}</math> -- информационная матрица (таблица), с указанием того, какой из каждых <math>m</math> объектов каким классам принадлежит | ||
- | |||
- | ''' Описание класса ''' -- список объектов из обучающей выборки, которые входят в класс, и список тех, которые не входят | ||
- | |||
- | ''' Контрольная выборка ''' -- набор из q объектов, предназначенных для определения разных параметров алгоритма: | ||
- | * <math>\varepsilon</math> -- параметры близости | ||
- | * <math>\{\Omega\}</math> -- опорные множества | ||
- | * <math>p_w</math> -- веса опорных множеств | ||
- | * <math>x_1, x_2</math> -- коэффициентов для формулы вычисления оценок | ||
- | * <math>\gamma_j</math> -- веса обучающих объектов | ||
- | |||
- | Так как пространство признаков не обязательно является числовым, то имеет смысл задавать объект через меры близости к объектам обучающей выборки ('''метрическое описание объектов''') : <math>\| \rho(a^'_{j}, a_{ij}) \|_{m \times n}</math>, где | ||
- | * <math>a^'_j</math> -- j-тый признак описываемого объект | ||
- | * <math>a_{ij}</math> -- j-тый признак i-того объекта базовой выборки <math>S</math> | ||
== Опорные множества в АВО. Функции близости. Веса объектов и признаков. == | == Опорные множества в АВО. Функции близости. Веса объектов и признаков. == | ||
- | |||
- | ''' Система опорных множеств ''' -- любое множество, элементы которого - непустые подмножества признаков {1,2...n}. При этом каждый признак должен входить хотя бы в одно множество: | ||
- | * <math>\{\Omega\}_A ~ : ~ \Omega_j = \{u_1, u_2, \dots, u_k\},~ u_k \in [1,n]</math> -- совокупность опорных множеств, задающих алгоритм распознавания A | ||
- | * <math>\forall i \in [1,k] ~~ \exists j : i \in \Omega_j</math>, каждый признак хотя бы в одном опорном множестве. | ||
- | * вместо <math>\Omega_j</math> можем рассматривать характеристический вектор <math>\tilde w_j = \{\sigma_1 \dots \sigma_n\}~:~~\sigma_{u_1} = \sigma_{u_2} = \dots = \sigma_{u_k} = 1</math>, а остальные координаты равны нулю | ||
- | |||
- | <u>Примеры опорных множеств</u>: | ||
- | * совокупность всех непустых подмножеств признаков {1,2...n}. его мощность: <math>2^n-1</math> | ||
- | * совокупность из всех подмножеств из k элементов. его мощность: <math>C^n_k</math> | ||
- | |||
- | ''' Функция близости ''' <math>\mathcal{N}_{\tilde\Omega}(S_i, S_j)</math> -- задает расстояние между проекциями объектов <math>S_i</math> и <math>S_j</math> на <math>\tilde\Omega \in \Omega</math>. В дальнейшем рассматриваются только такие функции <math>\mathcal{N}_{\tilde \Omega}</math>, которые принимают значения 0 или 1 (бинарные). | ||
- | |||
- | <u>Три вида функции близости:</u> | ||
- | # Введем неотрицательные параметры <math>\varepsilon_i > 0 ~,~ i \in [1,n]</math>. Пусть <math>\tilde\Omega=\{u_1, \dots, u_k\}</math>. Тогда <math>\mathcal{N}_{\tilde\Omega}(S_i, S_j) = | ||
- | \begin{cases} | ||
- | 1,~~\rho(\alpha_{i,u_l}, \alpha_{j,u_l}) \leqslant \varepsilon_{u_l}~~\forall l \in [1,k]\\ | ||
- | 0,~~otherwise | ||
- | \end{cases}</math> | ||
- | # Введем дополнительно к п.1 параметр <math>\nu</math> такой, что функция близости будет определятся как <math>\mathcal{N}_{\tilde\Omega}(S_i, S_j) = 1</math>, если не выполнено не больше, чем <math>\nu</math> описанных неравенств. при этом имеет смысл брать <math>0 \leqslant \nu \leqslant \left[\frac{k}{2} - 1\right] </math> | ||
- | # Вместо <math>\nu</math> определяем <math>\nu'</math> и функцию близости так, что <math>\mathcal{N}_{\tilde\Omega}(S_i,S_j) = 1</math>, если из k неравенств не выполнены r, причем <math>\frac{r}{k} < \nu'</math> | ||
- | * К билету был вопрос: какие сколько возможных выборок<math>\varepsilon_i</math> стоит рассматривать. Вообще говоря <math>\varepsilon</math> -действительно так-что континуум. Но смысл будут нести только l*m*n вариантов. где l - число признаков(колчисетво этих <math>\varepsilon</math> ),m - число компонент обучающей выборки, n - число компонент контрольной выборки. Другими словами мы <math>\varepsilon_i</math> задаем какое хотим, но обычно его задают между значениями признаков на выборке, при этом всего у нас m*n сравнений и таким образом m*n вариантов его задать(для одного <math>\varepsilon</math> ) | ||
== Формулы вычисления оценок. Эвристические обоснования. == | == Формулы вычисления оценок. Эвристические обоснования. == | ||
- | |||
- | ''' Формула вычисления оценок: ''' | ||
- | |||
- | <math>\Gamma_1^j (S) = \sum_{\tilde \Omega \in \Omega} \sum_{k : P_j(S_k) = 1} \gamma_k \cdot P_{\tilde \Omega} \cdot \mathcal{N}_{\tilde \Omega}(S, S_k)</math>, где: | ||
- | * <math>\tilde \Omega \in \Omega</math> -- опорные множества | ||
- | * <math>P_j(S_k) = 1</math> если объект <math>S_k</math> входит в класс <math>j</math>. | ||
- | * <math>\gamma_k</math> -- вес объекта <math>S_k</math>. | ||
- | * <math>P_{\tilde \Omega}</math> -- вес опорного множества. | ||
- | |||
- | <math>\Gamma_0^j (S) = \sum_{\tilde \Omega \in \Omega} \sum_{k : P_j(S_k) = 0} \gamma_k \cdot P_{\tilde \Omega} \cdot \mathcal{N}_{\tilde \Omega}(S, S_k)</math>, где: | ||
- | * <math>P_j(S_k) = 0</math> если объект <math>S_k</math> не входит в класс <math>j</math>. | ||
- | |||
- | Итоговая формула для оценки принадлежности объекта <math>S</math> классу <math>j</math>: | ||
- | |||
- | <math>\Gamma^j(S) = x_1 \cdot \Gamma_1^j (S) + x_2 \cdot \Gamma_0^j (S)</math>, где <math>x_1, x_2</math> -- коэффициенты, которые определяют работу с соответствующими характеристиками. | ||
== Задачи оптимизации АВО. Совместные подсистемы систем неравенств. == | == Задачи оптимизации АВО. Совместные подсистемы систем неравенств. == | ||
- | |||
- | * [http://www.cmcspec.ru/ipb/index.php?showtopic=536&view=findpost&p=15844 lekcii_ama_zuravlev.doc], пункт 2.4 | ||
- | * [http://www.mipt.ru/nauka/51conf/dokl/In_prac_fupm/m_3rhk32/m_3rhknp.html Оптимизация АВО по метрикам] | ||
== Функционалы качества. Сложность моделей алгоритмов и проблема переобучения. == | == Функционалы качества. Сложность моделей алгоритмов и проблема переобучения. == | ||
- | |||
- | '''Функционал качества''' алгоритма. | ||
- | Пусть задана таблица контрольных объектов (множество объектов, на которых мы будет проверять качество работы нашего алгоритма распознавания). Для контрольных объектов мы должны знать, к какому классу свойств относится каждый из объектов (иначе как мы будет проверять корректность работы нашего алгоритма). Подаем контрольные объекты на вход алгоритму. Доля правильных ответов, выданных алгоритмов - это и есть ''функционал качества'' (в простейшем случае). | ||
- | |||
- | |||
- | '''Обобщающая способность''' (generalization ability, generalization performance). Говорят, что алгоритм обучения обладает способностью к обобщению, если вероятность ошибки на тестовой выборке достаточно мала или хотя бы предсказуема, то есть не сильно отличается от ошибки на обучающей выборке. Обобщающая способность тесно связана с понятиями переобучения и недообучения. | ||
- | |||
- | '''Переобучение, переподгонка''' (overtraining, overfitting) — нежелательное явление, возникающее при решении задач обучения по прецедентам, когда вероятность ошибки обученного алгоритма на объектах тестовой выборки оказывается существенно выше, чем средняя ошибка на обучающей выборке. Переобучение возникает при использовании избыточно сложных моделей. | ||
- | |||
- | '''Недообучение''' — нежелательное явление, возникающее при решении задач обучения по прецедентам, когда алгоритм обучения не обеспечивает достаточно малой величины средней ошибки на обучающей выборке. Недообучение возникает при использовании недостаточно сложных моделей. | ||
== Общие пространства начальных и финальных информаций. Задачи синтеза корректных алгоритмов. == | == Общие пространства начальных и финальных информаций. Задачи синтеза корректных алгоритмов. == | ||
- | [http://www.ccas.ru/frc/thesis/RudakovDocDisser.pdf Диссертация Рудакова], пункт 1.1 | ||
- | |||
- | В самой общей постановке задача синтеза алгоритмов преобразования информаций состоит в следующем. Имеется множество начальных информаций <math>\Im_i</math> и множество конечных информаций <math>\Im_j</math>. Требуется построить алгоритм реализующий отображение из <math>\Im_i</math> в <math>\Im_j</math>, удовлетворяющее заданной системе ограничений. | ||
- | |||
- | Одним из частных случаев является задача обучения по прецедентам, в которой система ограничений задаётся следующим образом. Фиксируется последовательность <math>I_q = \{x_k\}_{k=1}^{q}</math> элементов множества <math>\Im_i</math> и последовательность <math>\bar{I_q} = \{y_k\}_{k=1}^{q}</math> элементов множества <math>\Im_j</math>. Искомый алгоритм <math>A</math> должен точно или приближённо удовлетворять системе из <math>q</math> равенств <math>A(x_k)= y_k,\,k=1,. . .,q</math>, которую мы будем сокращённо записывать как <math>A(\Im_q) = \bar{\Im_q}</math>. Ограничения такого типа называются локальными или прецедентными. | ||
- | |||
- | Кроме того,обычно требуется, чтобы искомый алгоритм удовлетворял некоторым дополнительным ограничениям, которые в общем случае выражаются условием <math> A \in W^u</math> где <math>W^u</math> заданное множество отображений из <math>\Im_i</math> в <math>\Im_j</math>. Алгоритм, удовлетворяющий локальным и дополнительным ограничениям, называют корректным. Итак, рассматриваемые задачи обучения по прецедентам определяется пятёркой <math>Z = \langle \Im_i, \Im_j, W^u, I_q, \bar{I_q} \rangle </math>. | ||
- | |||
- | Различие между локальными и дополнительными ограничениями заключается в том, что первые относятся к конечному набору точек и допускают эффективную проверку, в то время как вторые накладываются на всёотображение «в целом» и не допускают эффективной проверки. В частности, это могут быть ограничения непрерывности, гладкости, монотонности, унимодальности, и т. д. На практике дополнительные ограничения учитываются на этапе построения параметрического семейства алгоритмов,а локальные при последующей настройке параметров алгоритма на заданные прецеденты | ||
== Разрешимость и регулярность задач распознавания. Регулярность по Ю.И. Журавлёву == | == Разрешимость и регулярность задач распознавания. Регулярность по Ю.И. Журавлёву == | ||
- | |||
- | [http://www.ccas.ru/frc/thesis/RudakovDocDisser.pdf Диссертация Рудакова], пункт 1.5 | ||
- | |||
- | '''Разрешимые''' задачи - это задачи, для которых множество допустимых отображений их <math>\mathfrak{I}_i</math> в <math>\mathfrak{I}_f</math> непусто, т.е. существуют семейства алгоритмов, содержащие их решения. | ||
- | Задача Z из множества задач <math>\mathfrak{Z} </math> называется ''полной'' относительно семейства <math>\mathfrak{M} </math> отображений из <math>\mathfrak{I}_i</math> в <math>\mathfrak{I}_f</math>, если в <math>\mathfrak{M} </math> содержатся допустимые отображения для всех задач из класса эквивалентности, содержащего Z. | ||
- | Задача Z называется '''регулярной''', если для нее существует семейство отображений <math>\mathfrak{M} </math>, относительно которого она полна. | ||
- | |||
- | '''Регулярность по Журавлеву''': | ||
- | Пусть есть <math>q</math> объектов и <math>l</math> классов и | ||
- | <math>\hat{I}=||I_{ij}||_{q \times l}</math> - матрица информации и <math> \hat {\tilde I} = || {\tilde I}_{ij}||_{q \times l}</math> - матрица правильных ответов. | ||
- | Задаче Z соответствует пара матриц: <math> Z \leftrightarrow (\hat I , \hat{\tilde I})</math>. | ||
- | Определение ''окрестности задачи по Журавлеву'' <math>O(Z)=\{Z^' |Z^' \leftrightarrow (\hat I , \hat{\tilde I}^')\}</math> - т.е. это множество задач <math>Z^'</math>, получающихся всевозможным варьированием матрицы правильных ответов. | ||
- | |||
- | * Разбиваем множество задач на классы эквивалентности. Задача называется регулярной если она разрешима и разрешимы все задачи из класса эквивалентности который она порождает. | ||
== Операции над алгоритмами. Расширение моделей. == | == Операции над алгоритмами. Расширение моделей. == | ||
- | http://www.ict.edu.ru/ft/004700/VoronCanDisser.pdf | ||
- | |||
- | Пункт 1.2 | ||
== Пространства оценок. Алгоритмы как суперпозиции. == | == Пространства оценок. Алгоритмы как суперпозиции. == | ||
- | http://www.ict.edu.ru/ft/004700/VoronCanDisser.pdf | ||
- | |||
- | Пункт 1.2 | ||
== Понятие полноты моделей алгоритмов и семейств корректирующих операций. == | == Понятие полноты моделей алгоритмов и семейств корректирующих операций. == | ||
- | Диссертация Рудакова 1.3 + 1.5 пункты. | ||
- | Диссертация Рудакова, пункт 3.5 | ||
- | |||
- | |||
- | Модель алгоритмов <math>\mathfrak{M}</math> категории <math>\Phi_0</math> называется полной, если любая регулярная задача <math>Z</math> из множества <math>\mathfrak{Z}_{[R]}</math> полна относительно <math>\mathfrak{M}</math>, т.е. если для любой регулярной задачи <math>Z</math> модель алгоритмов от любой матрицы исходных информаций этой задачи приводит в множество конечных информаций. | ||
- | (т.е. в модели алгоритмов <math>\mathfrak{M}</math> для каждой регулярной задачи из множества <math>\mathfrak{Z}_{[R]}</math> содержится корректный алгоритм) | ||
== Дополнительные к прецедентам ограничения. Пример: перестановочность строк и столбцов в матрицах информации. == | == Дополнительные к прецедентам ограничения. Пример: перестановочность строк и столбцов в матрицах информации. == | ||
- | Прецедентная (локальная) информация - описания объектов и данные о принадлежности объектов к классам. | ||
- | Дополнительные к прецедентным (универсальные) ограничения - формальные ограничения на вид допустимых отображений. | ||
- | |||
- | === '''Задачи с однородными классами''' === | ||
- | |||
- | Пусть рассматривается задача, в которой имеется информация о том, что порядок, в котором анализируются классы несущественен, и кроме прецедентных данных нет сведений о различии классов. | ||
- | Универсальные ограничения, выражающие однородность классов, состоят в том, что отображение, реализуемое корректным алгоритмом, должно коммутировать со всеми подстановками столбцов (при любой перстановке столбцов в матрице информации точно так же должны переставляться столбцы в матрице, порожденной алгоритмом). | ||
== Задачи с непересекающимися классами. == | == Задачи с непересекающимися классами. == | ||
- | Диссертация Рудакова, пункт 2.5 | ||
== Класс поэлементных операций и отображений. Условия регулярности и полноты. == | == Класс поэлементных операций и отображений. Условия регулярности и полноты. == | ||
== Полнота моделей АВО. == | == Полнота моделей АВО. == | ||
- | Диссертация Рудакова, пункт 3.5 | ||
== Полнота полиномиальных семейств корректирующих операций. == | == Полнота полиномиальных семейств корректирующих операций. == | ||
- | Корректирующие операции по сути - операции над матрицами. Один из самых мощных и применяемых на практике - корректирующие полиномы некоторой степени, от матриц с Адамаровым умножением. | ||
- | |||
- | Основной вопрос - степень полинома, который может задать любую матрицу (и обеспечить таки образом полноту системы корректирующих операций). Было доказано, что при размерах матрицы информации <math>q * l</math>, система из полиномов степени <math>q * l - 1</math> - полна, <math>q * l - 2</math> - не полна. | ||
== Логарифмическая граница степени корректирующих полиномов. == | == Логарифмическая граница степени корректирующих полиномов. == | ||
- | + | == Проблема построения набора базовых операторов для конкретных задач. Дефекты различимости и монотонности. Сходимость методов синтеза мультиалгоритмических конструкций. == | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + |