Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Примеры:

• Выбор модели алгоритмов из небольшого множества альтернативных вариантов

• Оптимизация параметра регуляризации, в частности:

  • параметра регуляризации в гребневой регрессии

  • параметра сокращения весов (weight decay) в нейронных сетях

  • параметра C в методе опорных векторов

• Оптимизация ширины окна в методах

  • парзеновского окна

  • ближайшего соседа

  • ядерного сглаживания

• Оптимизация числа нейронов в скрытом слое многослойной нейронной сети.

• Выбор информативного набора признаков.

• Редукция решающего дерева.

• Структурная минимизация риска.

1. Особенности поиска кратчайшего пути. Алгоритм Дейкстры

Постановка задачи:

1. Задан неориентированный или ориентированный граф G=(V,E).

2. Заданы длины рёбер ℓ(v,w)≥0. Если ребра нет, то можно считать ℓ(v,w)=+∞.

3. Длины рёбер могут не удовлетворять неравенству треугольника (не метрика).

4. Длина пути ℓ(P) равна сумме длин ребёр.

5. Требуется найти кратчайший путь между заданными вершинами s и t.

6. Длины dist(s, t) кратчайших путей – метрика.

Практические требования задачи - миллионы вершин и рёбер, задачу решать надо за миллисекунды (а значит можем просмотреть лишь пару сотен вершин).

Современные алгоритмы точного поиска кратчайшего пути: (!!! пояснения к тому, что ниже?)

• Arc flags [Lauther 04, Kohler et al. 06].

• A∗ with landmarks [Goldberg & Harrelson 05].

• Reach [Gutman 04, Goldberg et al. 06].

• Highway [Sanders & Schultes 05] and contraction [Geisberger 08] hierarchies.

• Transit nodes [Bast et al. 06].

• Combinations (pruning and directing algorithms).

Метод сканирования (1963):

1. Для каждой вершины v храним «метку» (расстояние) d(v) и статус S(v) ∈ {unreached, labeled, scanned}.

2. Сначала все вершины имеют статус unreached, расстояние от источника до них d(v) = +∞.

3. Когда d(v) уменьшается, v получает статус labeled.

4. Начинаем с уменьшения d(v) для некоторых v.

5. Пока есть вершины labeled, выбрать одну из них и обработать. Вершина получает статус scanned.

6. Обработка отмеченной вершины v: для каждой дуги (v,w), если d(w) > d(v)+ℓ(v,w), то d(w) = d(v)+ℓ(v,w).

Начинать можно по-разному.

Выбирать можно по-разному.

Критерий останова надо аккуратно определять.

Алгоритм Дейкстры (1959):

1. Ищем путь из вершины s в вершину t

2. Начинаем обработку с вершины s: d(s) = 0

3. На каждом шаге обрабатываем вершину с минимальной меткой (!!!вообще в алгоритме дейкстры обрабатываются все вершины, не только та, у которой метка меньше. Так что у меня большие сомнения по поводу того, что тут написано. Откуда это взято?)

4. Останавливаемся, когда для обработки выбрана вершина t

5. Сложность линейна относительно размера просмотренного подграфа.

Модификации алгоритма дейкстры:

1. Обратный алгоритм Дейкстры - начинаем сканировать от финальной вершины t (переориентируем ребра ориентированного графа)

(как и в обычном алгоритме дейкстры на примере просмотрены почти все вершины)

1. Двунаправленный алгоритм Дейкстры - одновременно начинаем искать от вершин s и t. Проблема - нетривиальный критерий останова:

Пусть Ds и Dt – уже достигнутый минимум для выбираемых меток от соответствующего источника. Растут от нуля. Никакая unreached/labeled далее не получит менее этих значений. Никакая scanned уже не превышает их. Когда появляется первая scanned_s И scanned_t вершина (вершина, просканированная обоими алгоритмами), это ещё не остановка.

Оценка длины кратчайшего пути через вершину v:

• Scanned_s И scanned_t => Окончательно d(s,v)+d(t,v) (≤ Ds+Dt).

• не scanned_s И не scanned_t => Достижимо ≥ Ds+Dt.

• Только scanned_s => Достижимо ≥ d(s,v)+Dt.

• Только scanned_t => Достижимо ≥ Ds+d(t,v).

M – длина уже известного кратчайшего пути. Сначала M=+∞.

Условие отсечения вершины: через неё невозможен путь < M.

Условие останова: все необработанные вершины отсечены.

(на примере в сумме просмотрена лишь четверть вершин)

Для согращения перебора нужно отбрасывать мнрожества вершин, которые нам не нужны, для этого нужны хорошие критерии отсечения.

Критерии отсечения (доказано, что все дают точные результаты):

1. Highway/contraction hierarchies (CH): кратчайший путь сначала выходит на всё более крупные магистрали, а в конце сходит на всё более мелкие.

Проводим предварительную обработку, эвристически удаляя ненужные вершины, и вставляя потерянные кратчайшие пути (некоторые пути сохранять не придётся).

1. Эвристически упорядочиваем вершины.

2. Дуги направляем от младших к старшим вершинам.

3. Пополняем граф дугами для сохранения кратчайших путей.

Идея: Старшие вершины важнее (“глобальнее”). Запрос выполняется двунаправленным Дейкстрой, каждый поиск развивается только от младших к старшим вершинам.

Пусть (V, E∪E+) – граф с дополнительными дугами. Вершины упорядочены. Пусть Gf – орграф с дугами (v,w): (v,w)∈E∪E+, v<w, а Gr – орграф с дугами (w, v): (v,w)∈E∪E+, v>w.

По заданным s и t запускаем модифицированный двунаправленный алгоритм Дейкстры, причем поиск вперёд идет в графе Gf, а поиск назад - в Gr. (Оба поиска развиваются от младших к старшим.)

При останове dist(s, t) = minv(d(s, v)+d(v, t)).

Для графов дорог предложены эвристические способы упорядочивания, которые работают быстро и добавляют относительно мало новых дуг. Эксперименты показывают, что для графов дорог даже в худшем случае просматриваются очень маленькие подграфы.

1. Reach pruning (RE): малозначительные перекрестки вдали от начала/конца пути можно игнорировать.

Рассмотрим вершину v, которая делит путь P на части P1 и P2.

r(P,v) := min(ℓ(P1), ℓ(P2)) – расстояние до ближайшего конца для данного пути P.

r(v) := max(r(P,v)) – максимум по всем кратчайшим путям P, проходящим через v.

Reach – «радиус действия», «охват». Если s и t находятся от w далее r(w), то кратчайший путь точно не проходит через w.

Сокращение перебора в алгоритме Дейкстры:

если r(w) < min(d(s, v)+ℓ(v, w), LB(w, t)), то отсечь вершину w.

Оценку снизу LB(w, t), например, «даром» имеем при использовании двунаправленного алгоритма Дейкстры.

Добавление замыканий (делается итерационно несколько раз):

В этом графе большие Reach, трудно отсекать.

Добавим вспомогательное «замыкание».

Из двух путей одной длины предпочитаем пути из меньшего числа дуг. Reach снизился, легче отсекать.

Небольшое число замыканий обычно позволяет существенно понизить значения Reach для многих вершин.

=> Запускаем двунаправленый алгоритм Дейкстры.

1. Transit nodes (TN): Все дальние кратчайшие пути в/из некоторого региона обязательно проходят через небольшое подмножество вершин.

• Все кратчайшие маршруты в/из региона проходят только через точки доступа.

• Карты обычно удаётся разбить на регионы так, что в среднем у региона 10 точек доступа.

• Пар точек доступа из разных регионов немного, пути можно запомнить.

• Внутри каждого региона быстро ищем путь от заданной точки до всех точек доступа.

• Поиск пути между точками из разных регионов сводится к просмотру таблицы размера 10х10: D(i,j)=dist(s,TN1i)+dist(TN1i,TN2j)+dist(TN2j,t).

1. Глава 3. Часть от Сенько. (полным разумным конспектом являются слайды Сенько, в этой главе лишь некоторая вытяжка)

1. Прогнозирование по прецедентам

(Если возможность сделать искабельную версию его лекций? ctrl+f работает, но через раз, а точнее через десять =\ )

Задача прогнозирования решается для явления F.

Множество объектов, которые потенциально могут возникать в рамках F, называется генеральной совокупностью.

Генеральная совокупность обычно рассматривается как множество элементарных событий, на котором заданы алгебра событий и вероятностная мера, т.е. генеральная совокупность рассматривается как вероятностное пространство.

Каждому объекту из множества объектов генеральной совокупности - (X₁, …, X_n) соответствует прогнозируемая величина Y, она известна не для всех и задача прогнозирования - построение алгоритма, вычисляющего соответствующие Y. Зная некоторые из прогнозируемых величин для некоторых объектов.

Обучающая выборка - выборка прецедентов из генеральной совокупности с известными значениями прогнозируемой величины.

Обычающая выборка обычно рассматривается как независимая выборка объектов из генеральной совокупности.

Методы машинного обучения - методы, основанные на обучении по прецедентам.

Прогнозируемая величина может:

1. принимать значения из отрезка непрерывной оси

2. принимать значения из конечного множества - для данного случая задача называется задачей распознавания.

3. являться кривой, описывающей вероятность, возникновения некоторого критического события до различных моментов времени.

1. Способы поиска закономерностей

Один из способов поиска закономерностей - это поиск в некотором априори заданном семействе алгоритмов наилучшего. (тут получается, что поиск закономерностей == поиску наилучшего алгоритма в семействе? разве поиск закономерностей - это не разбиение на семейства алгоритмов?)

Один из способов поиска алгоритма - минимизация функционала эмпирического риска на обучающей выборке.

Средний риск = подинтегральное выражение часто обозначают Q(x, j, A(θ))

Задача в том, чтобы минимизировать средний риск относительно параметра θ. При решении задачи получаем качество (величину интеграла) и надёжность (вероятность по исходной информации найти оптимальное решающее правило).

Метод минимизации эмпирического риска – допустим определена функция среднего риска, допустим количество классов, среди которых нужно выбрать - конечно, есть выборка объектов из классов, как они выбирались:

есть совместное распределение, из которого выбирались объекты одним из 2-х способов:

1. Сначала объект, потом класс (модель учитель)

2. Сначала класс, а потом объект

После этого эмпирический риск – это средний риск, но интеграл по всем значениям заменён на сумму по выбранным объектам и классам.

Q - называется величиной потерь (он просто отражает, на сколько наш алгоритм промазал мимо правильного значения). Величину потерь можно задавать разными способами, например, как квадрат или модуль ошибки, или как булево значение - есть/нет ошибки.

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

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

1. Обобщающая способность

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

Мерой обобщающей способности явяется математическое ожидание потерь по всей генеральной совокупности.

Цель задачи прогнозирования - максимизация обобщающей способности. Но нужно понимать, что подсчитать её достаточно проблематично, т.к. обобщающая способность определяется через множество всей генеральной совокупности.

Эффект переобучения - это эффект, при котором расширение модели алгоритма и увеличение её сложности приводит к повышению точности аппроксимации на обучающей выборке, т.е. к снижению эмпирического риска, однако при этом не приводит к улучшению обобщающей способности, или приводит к её ухудшению.

Характеристики

Список файлов книги