Сглаженный анализ - 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 ({\hat {\mathbf {A} }},{\hat {\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 T(\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} }}+{\hat {\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 e^{\Omega (n)}}$ итераций в худшем случае для поиска локально оптимального решения. Однако если предположить, что точки имеют независимые Гауссовы распределения, каждый с ожиданием в ${\displaystyle [0,1]^{d}}$ и стандартное отклонение ${\displaystyle \sigma }$, ожидаемое количество итераций алгоритма ограничено полиномом от ${\displaystyle n}$, ${\displaystyle d}$ и ${\displaystyle \sigma }$.^[10]

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

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

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

1. Спилман, Дэниел; Тэн, Шан-Хуа (2009), «Сглаженный анализ: попытка объяснить поведение алгоритмов на практике» (PDF), Коммуникации ACM, ACM, 52 (10): 76–84, Дои:10.1145/1562764.1562785
2. Амента, Нина; Циглер, Гюнтер (1999), «Деформированные произведения и максимальные тени многогранников», Современная математика, Американское математическое общество, 223: 10–19, CiteSeerX  10.1.1.80.3241, Дои:10,1090 / conm / 223, ISBN  9780821806746, МИСТЕР  1661377
3. Шамир, Рон (1987), "Эффективность симплекс-метода: обзор", Наука управления, 33 (3): 301–334, Дои:10.1287 / mnsc.33.3.301
4. Андрей, Некулай (2004), «Андрей, Некулай.« О сложности пакета MINOS для линейного программирования », Исследования в области информатики и управления, 13 (1): 35–46
5. Спилман, Дэниел; Тэн, Шан-Хуа (2001), «Сглаженный анализ алгоритмов: почему симплексный алгоритм обычно занимает полиномиальное время», Материалы тридцать третьего ежегодного симпозиума ACM по теории вычислений, ACM: 296–305, arXiv:cs / 0111050, Bibcode:2001cs ....... 11050S, Дои:10.1145/380752.380813, ISBN  978-1-58113-349-3
6. Дадуш, Даниил; Хьюбертс, Софи (2018), «Удобный сглаженный анализ симплекс-метода», Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений: 390–403, arXiv:1711.05667, Дои:10.1145/3188745.3188826, ISBN  9781450355599
7. Боргвардт, Карл-Хайнц; Дамм, Ренате; Дониг, Рудольф; Joas, Gabriele (1993), "Эмпирические исследования средней эффективности симплексных вариантов при симметрии вращения", Журнал ORSA по вычислительной технике, Американское общество исследования операций, 5 (3): 249–260, Дои:10.1287 / ijoc.5.3.249
8. Боргвардт, Карл-Хайнц (1987), Симплексный метод: вероятностный анализ, Алгоритмы и комбинаторика, 1, Springer-Verlag, Дои:10.1007/978-3-642-61578-8, ISBN  978-3-540-17096-9
9. Энглерт, Матиас; Рёглин, Хейко; Фёкинг, Бертольд (2007), «Наихудший случай и вероятностный анализ алгоритма 2-Opt для TSP», Материалы восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, 68: 190–264, Дои:10.1007 / s00453-013-9801-4
10. Артур, Дэвид; Манти, Бодо; Рёглин, Хайко (2011), "Сглаженный анализ метода k-средних", Журнал ACM, 58 (5): 1–31, Дои:10.1145/2027216.2027217