Рандомизированые Алгоритмы

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

    Рандомизированые Алгоритмы от обычных отличаются тем, что используют случайность (source of randomness) в своей работе. В первую очередь нам надо четко различать слова «случайный» (random) и «произвольный» (arbitrary). Если в первом случае, мы делаем равновероятностный выбор, то во втором — не важно какой выбор мы делаем.

    Пример 1: Нам нужно выбирать число от 1 до 10.
    Если выбор «случайный», то каждый раз мы выбираем число с вероятностью 1/10. т. е. Сделав выбор N раз, каждое число будет выбрано примерно N/10 раз.
    Если выбор «произвольный», то выбирать только число «5», это тоже хорошо. Иными словами, «произвольный» выбор хорош там, где выбор не влияет на результат. Скажем DFS проход по дереву позволяет «произвольный» выбор потомка.

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

    Чем же они хороши, эти рандомизированые алгоритмы?

    • Зачастую, они заметно проще. (см. пример 4)
    • Позволяют решать задачи, не разрешимые классическими. (см. пример 2)
    • Позволяют контролировать размер ошибки.
    • Наверное есть что-то еще.


    Монте-Карло

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

    Пример 2.
    Нам нужно написать профайлер, можно в каждую функцию втюхать таймер и смотреть сколько времени занимает ее вызов, а можно воспользоваться методом Монте-Карло. Время от времени останавливать процесс и смотреть на стэк вызовов (call stack). Конечно, ответ мы получим приблизительный, но если замерять будем достаточно часто и достаточно много, то отклонение от истины не будет большим.

    Лас-Вегас

    Другая известная парадигма – метод Лас-Вегас (наверное по аналогии с предидущим методом назвали). Суть его заключается в том, что алгоритм возвращает правильный результат, но за неопределенное время. Дальше включается теория вероятности, которая доказывает что скорее всего это время будет небольшим.

    Пример 3.
    У нас есть монета на которой решка выпадает с вероятностью 1/3, а орел, соответственно, с вероятностью 2/3. Нам нужна монета с вероятностями ½ на каждую сторону.

    Подбросим монету два раза.
    • Если выпали “орел, решка” — скажем орел.
    • Если выпали “решка, орел” — скажем решка.
    • Если выпали два орла или две решки, повторим опыт.


    Вероятность увидить два орла или две решки 1/9+4/9 = 5/9. Значит, вероятность что наш алгоритм не остановится за (скажем) 10 ходов меньше 0.003.

    Основной закон органической химии

    Иногда, у нас есть алгоритм который показывает хорошие результаты на случайных данных и плохие на упорядоченых (например бинарное несбалансированое дерево). Наша задача, из существующих данных, сделать однородно распределенные данные, и тут нам поможет «основной закон органической химии». Применительно к нашему вопросу он звучит так:
    Пусть А случайный бинарный вектор так что каждый бит равен 1 с вероятностью одна вторая.
    Тогда если взять «произвольный» бинарный вектор B и посчитать (A xor B), то вероятность каждого бита в результате, тоже будет одна вторая. Иными словами (A xor B) «случайный» вектор.

    Пример 4. Желаем хранить в обычном дереве двоичные строки длинны k. Для этого генерируем случайную строку нужной длины, и делаем с ней xor всем данным с которые кладем или ищем в дереве.

    Как бороться с ошибкой (Amplification)

    Для простоты, предположим что наша задача может иметь только два ответа: «да» или «нет».
    По большому счету, есть 2 варианта ошибки. Одностороння и двух сторонняя.
    В первом случае, алгоритм ошибается только с ответами «да» или только с «нет».

    Пример: Наш алгоритм проверяет число на простоту. Если оно простое, он говорит «да».
    Если число составное, он говорит «нет» с вероятностью ½.
    Запустим алгоритм N раз и скажем «число составное» если, хотя бы раз, алгоритм сказал «нет».

    Как вы видите, если изначально на составных числах вероятность ошибки была ½, то после N запусков она 2^(-N).

    Во втором случае, наш алгоритм ошибается не зависимо от того, какой же правильный ответ.
    Например он верно определяет простоту числа с вероятностью 2/3. Тогда запустим его N раз, и выбирем тот ответ, который встретился чаще. Теорема Чернова подтвердит нам, что вероятность ошибки убывает экспоненциально от N.

    В заключение

    Если перед вами стоит муторная задача с замысловатым алгоритмом для ее решения, то может стоит рассмотреть вариант с рандомизацией? И багов меньше, и нервы крепче.

    УПД 1: В коментариях TheHorse справедливо замечает, что «Монте-Карло» и «Лас-Вегас» это не алгоритмы а методы. Наверное будет уместно обозвать их классами алгоритмов и заметить что один алгоритм может принадлежать обоим классам одновременно.

    УПД 2: Нашел топик, где kelj подробно рассписывает использование метода Монта-Карло для нахождения площади фигуры.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 32

      +9
      Как-то рвано и про все. Так и не понял, на какой вопрос ответила статья?
        0
        Пытался ответить на вопрос «что такое рандомальные алгоритмы и кому они нужны».
        +3
        На запрос «Основной закон органической химии» Гугл выдает немного другое:
        Основной закон органической химии: Если 1 килограмм повидла смешать с 1 килограммом говна, то получится 2 килограмма говна.
        и
        При неограниченном времени протекания реакции конечным продуктом, независимо от исходных препаратов является спирт.
          +4
          Я имел ввиду первое. xor с рандомальной датой дает рандомальную дату.
            +1
            Здесь автор приводил аналогию с первым утверждением.
            +1
            Хотел дать ссылку на детальное разъяснение разницы между терминами «Алгоритм» и «Метод», но не нашел.

            Суть в том, что метод Монте-Карло — метод, а не алгоритм. И вообще, всё что тут описано больше на методологию похоже, чем на алгоритмы.

            P. S. статья хорошая, понятная, полезная. Одобряю).
              0
              Спасибо, подправил.
                +1
                Позволю себе добавить. Метод, алгоритм и класс алгоритмов — разные вещи, хотя точную формальную разницу между методом и алгоритмом Вы, боюсь, не найдете. Метод в общем случае не относится к конкретной задаче, а скорее определяет подход к решению как таковой. Метод, примененный к задаче, может привести к алгоритму, например, алгоритм численного интегрирования (он же — нахождения площади фигуры) по методу Монте-Карло.
              0
              Метод Монте-Карло — это не то, что Вы написали в примере. У вас в примере от «Монте-Карло» только сбор статистики. «Профайлер» работал бы на основе метода Монте-Карло, если бы он собирал статистику не с запускаемой программы, а со «случайного набора callstack-ов», распределение которого совпадает с распределением, которое получается при реальной работе приложения (причем, «случайный набор callstack-ов» должен генерировать сам «профайлер», а не приложение). Только вот это уже не профайлер получается, а фигня какая-то, недаром я его в кавычки взял.
                0
                Наверное я не ясно выражаюсь. Если вы запускаете приложение, и через рандомальные промежутки времени смотрите на callstack, чем это не Монте-Карло? Просто рандомизация в том, когда вы смотрите на стэк.

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

                ПС: Добавлю линк на классический пример с площадью.
                  0
                  Это называется сэмплингом, а не методом Монте-Карло
                    0
                    Также, в примере с площадью вы сами бросаете «точку». Если кто-то за вас будет бросать точку (программа будет сама выбирать пути выполнения), то не факт что вы правильно посчитаете площадь фигуры (в данном случае считался бы объём кода).
                      0
                      В роли фигуры выступает программа, в роли точек — моменты времени когда происходит измерение. Посмотрите ниже, я Wyrd ответил.

                      PS: Все-таки надо было классический пример брать, а не «отсебятину» придумывать. Сейчас бы возражений не было.
                      +1
                      Ну, во первых профайлеры смотрят далеко не через рандомный промежуток, а через равный, иначе смысла бы это не имело (точнее статистика бы накапливалась на порядок больше, и ошибка была бы значительно выше).

                      Наверное, надо пояснить.

                      Возьмем пример с монеткой.

                      Представим себе белый ящик, который имеет манипулятор для переворачивания монетки.
                      Этот ящик через некие, понятные ему одному промежутки времени, переворачивает монетку.
                      Белый ящик будет играть роль программы а «значение» (орел/решка) монетки — текущий каллстек. Операция «перевернуть монетку» — вызов функции (монетку, всегда переворачивают, т.к. невозможно войти внутрь функции не изменив каллстек). Наша задача — оптимизировать белый ящик, чтобы он переворачивал монетки быстрее, для этого нам надо знать, какой из сторон монетка дольше лежит к верху (т.е. конкретный каллстек, который «тормозит»). При этом все что мы можем — это периодически смотреть на то, какой стороной монетка лежит к верху в данный момент времени. Особо отметим, что проведя два измерения мы не можем определить, переворачивали ли монетку между ними (вызывались ли функции между измерениями [на самом деле, технически это возможно, но требует много ресурсов]).

                      Вернемся к задаче определния времени, которая монетка проводит в каждом из своих положений.

                      Допустим, что проверяем мы ее положение через случайные промежутки времени, подчиняющиеся нормальному распределению. Допустим, что монетка проводит 50% времени вверх решкой и 50% времени вниз. Допустим, что ящик переворачивает ее все время через одно и то же время. Тогда, проведя несколько сеансов «профайлинга», мы получим, что монетка в среднем была 50% времени вверх, а результаты распределяться согласно нормальному распределению (это потому что мы меряли положение монетки через случайные промежутки времени). Отсюда вывод, лучше мерять через равные промежутки времени, тогда мы получим реальный результат: точно 50% +- 1/(количество измерений). Это в простейшем случае, когда монетка проводит на обоих сторонах одинаковое количество времени. В более сложном случае будет еще хуже.

                      Надеюсь, я доступно объяснил, почему стек смотрят через равные промежутки времени.

                      Большинство профайлеров, кстати работает по другому — инструментирует код. Стохастический метод обычно доступен, но используется только тогда, когда инструментация что-то случайно ломает, приводя к краху приложения. Причина — он менее удобен (необходимо загрузить приложение одной и той же задачей на минут 10 хотя бы).

                      Более того, даже если бы время между измерениями было рандомным, это все равно был бы не Монте-Карло, потому как Монте-Карло — это когда не просто «рандомно», а с такими же вероятностными характеристиками, как и у изучаемого процесса (пример с таким «профайлером» в моем сообщении выше).
                        0
                        Написал длинный коментарий, но стер. Сейчас проще объясню.

                        Программа бежит детерменировано (так по русски?) и меняет состояние callstack-а. Мы в случайно выбраных точках замеряем это состояние. Затем строим гистограмму и выдаем ее за верный ответ.

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

                        Теперь, почему не «через равные промежутки времени». Наверное при написании настоящего профайлера это было бы правильнее, но:
                        1. Это не было бы МК (хотя возможно было бы квази-МК)
                        2. Нельзя было бы усилить результат с помощью прогона программы через профайлер несколько раз. Особенно если программа короткая и без инпута (считает корень из двух).

                        Все таки цель топика, рассказать о базовых принципах РА простым языком, а не предложить новый метод профайлинга.

                          0
                          Ненене! :)

                          Я просто прокомментирую Ваше высказывание выше:
                          «В роли фигуры выступает программа, в роли точек — моменты времени когда происходит измерение.»

                          Дело в том, что МК подразумевает, что одна и та же случайная последовательность на входе МК ВСЕГДА генерирует одну и ту же случайную последовательность на выходе. В Вашем примере с профайлером это условие выполняется только на идеальном компьютере (потому как путь, который «пробегает» программа он детерменирован, а вот скорость с которой она его «пробегает» на реальном компьютере нифига не детерминирована), т.е. даже подавая на вход такого профайлера одну и ту же последовательность случайных промежутков времени Вы каждый раз будете получать разные результаты.

                          Вы можете сказать, что входом МК в данном случае являются не только ГСЧ для промежутков времени, но и все те факторы, которые влияют на скорость выполнения, поэтому разные результаты — это нормально. Однако, так можно сказать, только в том случае, если Вы знаете характер случайного распределения факторов, влияющих на скорость выполнения. А Вы этого распределения не знаете.

                          Иными словами, вы ничего не симулируете таким профайлером, только вносите «погрешность измерений». Хотите из профайлера МК — полностью эмулируйте работу программы в профайлере на виртуальном процессоре со строго контролируемой скоростью выполнения.

                          по поводу (2): результат как раз «усиливается» даже при одинаковых промежутках времени, именно потому, что скорость выполнения недетерменирована.

                          В общем, я бы взял более адекватный пример, их сотни. То же моделирование распада частиц на МК основано (виртуальные модели коллайдеров)
                            +1
                            Ну вот мы и добрались до сути. Я имел ввиду что программа бежит детерминировано и в плане результатов и в плане скорости. Сейчас допишу. Теперь мне понятны ваши возражения по поводу МК.
                    +1
                    Учите русский
                      0
                      Учим. Как его еще учить, если не писать на нем?
                      +1
                      А как же «замечательная» сортировка Bogosort?
                        0
                        Пример 4, ИМХО, не самый удачный. A xor B хоть и случайный вектор, а совокупность всех полученных векторов будет не случайна. Если A и C различались на 1 бит, то они и после изменения будут отличаться на тот же бит. В двоичном дереве поиска это может негативно сказаться.

                        Последний пример — рандомизированный тест простоты Миллера-Рабина. Похожая идеология работы у многих других алгоритмов. Вот, например, что запомнилось: дано 3 матрицы A, B, C, проверить, что A * B = C за O(n^2) (Простое перемножение даст O(n^3)). Для этого случайный генерируем вектор D из 0 и 1 и проверяем равенство A * (B * D) = C * D (а это O(n^2)). Если выполняется, то с вероятностью 1/2 исходное равенство верно. Повторяем это для получения необходимой точности
                          0
                          глубина дерева зависит порядка в котором данные запихивают в дерево. Если в дерево запихнуть восходящую (нисходящую) последовательность, то дерево выдет длинной сосиской и никакого удовольствия. XOR с рандом датой, позволяет как бы перемешать последовательность и вы перестаете зависить от инпута. посмотрите на это так:
                          есть два ключа s1 и s2. Есть самый левый бит i где они отличаются. Этот бит и определяет s1 > s2 или s1 < s2.
                          В тот момент когда вы xor-ите ключи с рандомальным s, то если s[i] = 0, знак сохраняется. Если s[i] = 1, знак переворачивается.

                          — Про три матрицы я помню задачу, но хотелось своих примеров придумать для разнообразия. И желательно не сложных, для людей из другой области.
                          — И да, ключи не становятся «независимыми», но нам это и не нужно. Можно кстати сделать их попарно независимыми с помощью двух случайных векторов или n-независимыми с помощью n случайных векторов.
                          0
                          На самом деле. примеры очень слабые.
                          Вот задача из жизни. Есть много-много 64-битовых строк. A и B похожи, если они отличаются не более чем, например, в 8 битах. Строки A1 и A2 называются эквивалентными, если в нашем множестве есть строки B1, B2, ..., Bn, такие, что A1 и B1, B1 и B2, ..., B(n-1) и Bn, Bn и A2 эквивалентны.
                          Задача: разбить строки на группы эквивалентности.
                            0
                            Ответ белым написать не могу, так что напишу завтра (если до того не появится).
                              0
                              > Строки A1 и A2 называются эквивалентными, если в нашем множестве есть строки B1, B2, ..., Bn, такие, что A1 и B1, B1 и B2, ..., B(n-1) и Bn, Bn и A2 эквивалентны.

                              Рекурсивненько.
                                0
                                Посмотрите на время написания комментария:)
                                Естественно, имелось в виду «такие, что A1 и B1, B1 и B2, ..., B(n-1) и Bn, Bn и A2 похожи».
                                Или, что то же самое, отношение эквивалентности есть транзитивное замыкание отношения похожести.

                                Или лучшая формулировка: наши слова — вершины графа, ребра проводятся между близкими словами, надо разбить граф на компоненты связности.
                                  0
                                  Задача интересная, рассказывайте уже ответ :) С наскока решить не удалось, а сильно углубляться времени, к сожалению, нет.
                                    +1
                                    Для начала — детерменированный вариант.
                                    Пусть для похожести отличие должно быть не более чем в трех битах. Тогда возьмем 4 группы, состоящие из битов с номерами 0-15, 16-31, 32-47 и 48-64. Если два слова отличаются не более чем в 3х битах, то они совпадают хотя бы в одной из этих групп.
                                    Для каждой из этих групп сделаем разобьем строки на 6536 множеств, в зависимости от значений битов этой группы. При этом в естественном случае — когда непохожие строки как правило отличаются довольно сильно — в каждом множестве окажется примерно одинаковое количество элементов. После этого можно уже внутри группы сделать попарные сравнения. В итоге, попарные сравнения проводятся в 2^18 групп, размер каждой из которых есть 2^{-16} от размера всего множества. Т.е. в 2^{-14} раз меньше сравнений.
                                    Но если мы возьмем скажем 8 бит то при точной аналогии нам понадобится брать группы по 7 бит, что мало. Поэтому будем использовать группы большего размера.
                                    При этом они, естественно, будут пересекаться (т.е. различие в определенном бите может запороть проверку сразу по нескольким группам), но это нестрашно. Главное — это чтобы любой набор из 8 бит не пересекался с хотя бы одной группой.
                                    Берем случайную группу из k бит, она не пересекает данный фиксированный набор из 8 бит с вероятностью C_56^k/C_64^k. Значит, все N групп пересекают данный набор с вероятностью (1 — C_56^k/C_64^k)^N. Вероятность того, что все N групп пересекают хотя бы один из C_64^8 наборов не превосходит 1 — C_64^8 * (1 — C_56^k/C_64^k)^N (на самом деле, эту оценку можно сильно улучшить, но и в таком виде работает неплохо).
                                    Так, для отличия в 8 битах, k=18 и вероятности 10^{-6} получаем число групп, равное 592. Т.е. ускорение почти в тысячу раз. Что, согласитесь, довольно неплохо.
                                    Проблема остается только в том, что если 2^k близко к общему количеству строк, то распределение по группам сильно неравномерное. Иначе всё было бы просто: для k=24 — 2055 групп (ускорение почти в 8 тысяч раз) и так далее.
                                      0
                                      Любопытно. С Вашего позволения, буду использовать этот пример, действительно выразительный. И если не секрет, где эта задача применялась?
                                        0
                                        Поиск почти-дупликатов. Из текста делаем вектор (шинглинг+simhash, например), причем если тексты похожие, то вектора отличаются слабо. А далее группируем.
                                        0
                                        Ссылкой на «бумагу» поделитесь?
                                          0
                                          Нет, к сожалению.
                                          Мне статью дали почитать примерно год назад (т.е. я не сам ее нашел), так что ни авторов, ни названия не помню. Единственное, что помню — у одного из авторов email был на google.com.

                              Only users with full accounts can post comments. Log in, please.