Сглаженный анализ - Википедия - Smoothed analysis

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

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

В теоретическая информатика, сглаженный анализ это способ измерения сложность алгоритма. С момента своего появления в 2001 году сглаженный анализ использовался в качестве основы для значительных исследований по проблемам, начиная от математическое программирование, числовой анализ, машинное обучение, и сбор данных.^[1] Он может дать более реалистичный анализ практических характеристик алгоритма, например времени его работы, чем при использовании сценариев наихудшего или среднего случая.

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

Несмотря на то что анализ наихудшего случая был широко успешным в объяснении практической производительности многих алгоритмов, этот стиль анализа дает вводящие в заблуждение результаты для ряда проблем. Сложность наихудшего случая измеряет время, необходимое для решения любого входного сигнала, хотя трудные для решения входные данные могут никогда не появиться на практике. В таких случаях наихудшее время работы может быть намного хуже, чем наблюдаемое время работы на практике. Например, сложность наихудшего случая решения линейная программа с использованием симплексный алгоритм экспоненциально,^[2] хотя на практике наблюдаемое количество шагов примерно линейно.^[3][4] Симплексный алгоритм на самом деле намного быстрее, чем эллипсоидный метод на практике, хотя последний полиномиальное время наихудшая сложность.

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

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

История

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

Примеры

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

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

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

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

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

при условии

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

Если время работы нашего алгоритма на данных ${ displaystyle mathbf {A}, mathbf {b}, mathbf {c}}$ дан кем-то ${ Displaystyle Т ( mathbf {A}, mathbf {b}, mathbf {c})}$ то сглаженная сложность симплекс-метода равна^[6]

${ displaystyle 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}}} + { шляпа { mathbf {A}}}, { bar { mathbf {b}}} + { hat { mathbf {b}}}, mathbf {c})] = { rm {poly}} ( d, log n, sigma ^ {- 1}).}$

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

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

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

Одним из примеров является 2-опт эвристика для задача коммивояжера. Для нахождения локально оптимального решения может потребоваться экспоненциально много итераций, хотя на практике время выполнения субквадратично по количеству вершин.^[9] В коэффициент аппроксимации, который представляет собой соотношение между длиной вывода алгоритма и длиной оптимального решения, обычно является хорошим на практике, но также может быть плохим в теоретическом худшем случае.

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

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

Смотрите также

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

Рекомендации