Сглаженный анализ

Случайно сгенерированное растровое изображение не похоже на типичные изображения.

Типичное изображение не похоже на случайное растровое изображение.

В информатике теоретической сглаженный анализ — это способ измерения сложности алгоритма . С момента своего появления в 2001 году сглаженный анализ использовался в качестве основы для обширных исследований для решения самых разных задач: от математического программирования , численного анализа , машинного обучения и интеллектуального анализа данных . Он может дать более реалистичный анализ практической производительности (например, времени работы, вероятности успеха, качества аппроксимации) алгоритма по сравнению с анализом, в котором используются сценарии наихудшего или среднего случая.

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

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

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

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

История

ACM и Европейская ассоциация теоретической информатики вручили премию Гёделя 2008 года Дэниелу Спилману и Шанхуа Тэну за разработку сглаженного анализа. Название «Сглаженный анализ» было придумано Аланом Эдельманом . В 2010 году Спилман получил премию Неванлинны за разработку сглаженного анализа. Статья Спилмана и Тенга в JACM «Сглаженный анализ алгоритмов: почему симплексный алгоритм обычно занимает полиномиальное время» также стала одним из трех победителей премии Фулкерсона 2009 года , спонсируемой совместно Обществом математического программирования (MPS) и Американским математическим обществом (AMS). .

Примеры

Симплексный алгоритм линейного программирования

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

Для модели возмущений мы предполагаем, что входные данные возмущены шумом из гауссова распределения . В целях нормализации мы предполагаем невозмущенные данные ${\bar {\mathbf {A} }}\in \mathbb {R} ^{n\times d},{\bar {\mathbf {b} }}\in \mathbb {R} ^{n},\mathbf {c} \in \mathbb {R} ^{d}$ удовлетворяет $\|({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})\|_{2}\leq 1$ для всех строк $({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})$ матрицы $({\bar {\mathbf {A} }},{\bar {\mathbf {b} }}).$ Шум $({\hat {\mathbf {A} }},{\hat {\mathbf {b} }})$ имеет независимые записи, выбранные из распределения Гаусса со средним значением $0$ и стандартное отклонение $\sigma$. Мы устанавливаем $\mathbf {A} ={\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},\mathbf {b} ={\bar {\mathbf {b} }}+{\hat {\mathbf {b} }}$. Сглаженные входные данные представляют собой линейную программу

максимизировать

$\mathbf {c^{T}} \cdot \mathbf {x}$

при условии

$\mathbf {A} \mathbf {x} \leq \mathbf {b}$.

Если время работы нашего алгоритма на данных $\mathbf {A} ,\mathbf {b} ,\mathbf {c}$ дается $T(\mathbf {A} ,\mathbf {b} ,\mathbf {c} )$ тогда сглаженная сложность симплекс-метода равна

$C_{s}(n,d,\sigma ):=\max _{{\bar {\mathbf {A} }},{\bar {\mathbf {b} }},\mathbf {c} }~\mathbb {E} _{{\hat {\mathbf {A} }},{\hat {\mathbf {b} }}}[T({\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},{\bar {\mathbf {b} }}+{\hat {\mathbf {b} }},\mathbf {c} )]={\rm {poly}}(d,\log n,\sigma ^{-1}).$

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

Локальный поиск для комбинаторной оптимизации

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

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

Один класс примеров проблем можно определить следующим образом: $n$ очки в поле $[0,1]^{d}$, где их попарные расстояния взяты из нормы . Уже в двух измерениях эвристика с двумя вариантами может потребовать экспоненциально много итераций, пока не будет найден локальный оптимум. В этом случае можно проанализировать модель возмущений, в которой вершины $v_{1},\dots ,v_{n}$ выбираются независимо в соответствии с распределениями вероятностей с функцией плотности вероятности $f_{1},\dots ,f_{n}:[0,1]^{d}\rightarrow [0,\theta ]$. Для $\theta =1$, точки распределены равномерно. Когда $\theta >1$ велик, у злоумышленника больше возможностей увеличить вероятность возникновения серьезных проблем. В этой модели возмущений ожидаемое количество итераций 2-opt эвристики, а также коэффициенты аппроксимации результирующего результата ограничены полиномиальными функциями $n$ и $\theta$.

Еще один алгоритм локального поиска, для которого сглаженный анализ оказался успешным, — это метод k-средних . Данный $n$ указывает на $[0,1]^{d}$, NP-трудно найти хорошее разбиение на кластеры с небольшими попарными расстояниями между точками в одном кластере. Алгоритм Ллойда широко используется и очень быстр на практике, хотя для этого может потребоваться $e^{\Omega (n)}$ итерации в худшем случае для поиска локально оптимального решения. Однако, предполагая, что точки имеют независимые гауссовы распределения , каждая из которых имеет математическое ожидание в $[0,1]^{d}$ и стандартное отклонение $\sigma$, ожидаемое число итераций алгоритма ограничено полиномом от $n$, $d$ и $\sigma$.

См. также

• Средняя сложность
• Псевдополиномиальное время
• Наихудшая сложность