Алгоритм вычисления вероятности функции /Метод Монте-Карло

Я пишу программу, которая пытается дублировать алгоритм, описанный в начале этой статьи,

http://www-stat.stanford.edu/~cgates/PERSI/papers /MCMCRev.pdf

F - это функция от символа к символу. Предположим, что Pl (f) является мерой «правдоподобия» этой функции. Алгоритм:

Начиная с предварительного предположения о функции, скажем, f, а затем новой функции f * -

  • Вычислить Pl (f).
  • Измените на f *, сделав случайное преобразование значений f, назначенных двум символам.
  • Вычислить Pl (f *); если это больше, чем Pl (f), примите f *.
  • Если нет, переверните монету Pl (f) /Pl (f *); если дело доходит до головы, прими f *.
  • Если бросок монеты выпадает из хвоста, оставайтесь на f.

Я реализую это, используя следующий код. Я использую c #, но попытался сделать его несколько более простым для всех. Если есть лучший форум для этого, пожалуйста, дайте мне знать.

 var current_f = Initial();    // current accepted function f
 var current_Pl_f = InitialPl();  // current plausibility of accepted function f

 for (int i = 0; i < 10000; i++)
        {
            var candidate_f = Transpose(current_f); // create a candidate function

            var candidate_Pl_f = ComputePl(candidate_f);  // compute its plausibility

            if (candidate_Pl_f > current_Pl_f)            // candidate Pl has improved
            {
                current_f = candidate_f;            // accept the candidate
                current_Pl_f = candidate_Pl_f; 
            }
            else                                    // otherwise flip a coin
            {
                int flip = Flip(); 

                if (flip == 1)                      // heads
                {
                    current_f = candidate_f;        // accept it anyway
                    current_Pl_f = candidate_Pl_f; 
                }
                else if (flip == 0)                 // tails
                {
                    // what to do here ?
                }
            }
        }

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

РЕДАКТИРОВАТЬ . Вот, в сущности, метод Transpose (). Я использую словарь /хэш-таблицу типа <<char, char>> что функции-кандидаты используют для поиска любого заданного символа -> преобразование символа Таким образом, метод транспонирования просто меняет два значения в словаре, который определяет поведение функции.

    private Dictionary<char, char> Transpose(Dictionary<char, char> map, params int[] indices)
    {
        foreach (var index in indices)
        {
            char target_val = map.ElementAt(index).Value;   // get the value at the index

            char target_key = map.ElementAt(index).Key;     // get the key at the index

            int _rand = _random.Next(map.Count);   // get a random key (char) to swap with

            char rand_key = map.ElementAt(_rand).Key;

            char source_val = map[rand_key]; // the value that currently is used by the source of the swap

            map[target_key] = source_val; // make the swap

            map[rand_key] = target_val;
        }

        return map; 
    }

Имейте в виду, что функция-кандидат, которая использует базовый словарь, в основном просто:

public char GetChar(char in, Dictionary<char, char> theMap)
{
     return theMap[char]; 
}

И это функция, которая вычисляет Pl (f):

    public decimal ComputePl(Func<char, char> candidate, string encrypted, decimal[][] _matrix)
    {
        decimal product = default(decimal);

        for (int i = 0; i < encrypted.Length; i++)
        {
            int j = i + 1;

            if (j >= encrypted.Length)
            {
                break;
            }

            char a = candidate(encrypted[i]);
            char b = candidate(encrypted[j]);

            int _a = GetIndex(_alphabet, a); // _alphabet is just a string/char[] of all avl chars 
            int _b = GetIndex(_alphabet, b);

            decimal _freq = _matrix[_a][_b]; 

            if (product == default(decimal))
            {
                product = _freq;
            }
            else
            {
                product = product * _freq;
            }
        }

        return product;
    }
7 голосов | спросил Sean Thoman 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 15 Sep 2011 01:36:07 +0400 2011, 01:36:07

3 ответа


0

Ориентировочно, codereview.stackexchange.com может быть лучшим форумом для этого ".
> Тем не менее, я сделаю быстрый удар:

  • На первый взгляд показанный фрагмент кода является правильной реализацией алгоритма.
  • Будет ли алгоритм «зависать» в локальных минимумах - это проблема, относящаяся к алгоритму , а не к реализации . (см. обсуждение ниже)
  • Ваш поиск " оптимального подхода ", по-видимому, направлен на изменения в алгоритме (отклонение от исходного алгоритма), а не на изменения в реализации (для сделать это быстрее и /или устранить некоторые возможные недостатки). Что касается алгоритма, см. Обсуждение ниже; Для обсуждения относительно реализации рассмотреть следующее:
    • убедитесь, что метод Flip () является справедливым
    • убедитесь, что ComputePl () верен: некоторые ошибки часто возникают из-за проблем с арифметической точностью в функции значения.
    • обеспечить справедливость (равновероятность) с помощью метода Transpose ().
    • Повышение производительности, скорее всего, связано с оптимизацией в методе ComputePl () (не показан), а не в основном цикле.

Обсуждение алгоритма как такового и его применимости к различным проблемам.
В двух словах, алгоритм представляет собой управляемый стохастический поиск, в результате чего [огромное] пространство решения отбирается двумя случайными устройствами: метод Transpose (), который (очень незначительно каждый раз) изменяет текущую функцию-кандидат, и метод Flip (), который решает должно ли выжить [локально] субоптимальное решение. Поиск осуществляется с помощью целевой функции ComputePl (), которая сама основана на матрице перехода первого порядка в некотором эталонном корпусе.

В этом контексте можно избежать локальных минимумов «ямок смол», увеличивая вероятность выбора «неоптимальных» функций: вместо справедливого 50–50 Flip (), возможно, попытайтесь с вероятностью сохранения «неоптимальных» решений в 66% или даже 75%. Этот подход обычно увеличивает количество поколений, необходимых для достижения оптимального решения, но, как уже было сказано, может избежать застревания в локальных минимумах.

Еще один способ обеспечить применимость алгоритма - обеспечить лучшую оценку правдоподобности данных функций. Вероятные объяснения относительного успеха и общности алгоритма:

  • Распределение переходов первого порядка в английском языке не очень равномерно (и, следовательно, довольно хорошо моделирует правдоподобие данной функции, вознаграждая ее за совпадения и наказывая за несоответствия). Этот вид многомерной статистики более устойчив к отклонению от эталонного корпуса, чем, скажем, распределение символов "порядка 0" на данном языке /корпусе.
  • Распределение переходов первого порядка, хотя и зависит от языка, обычно одинаково для разных языков и /или в контексте словарей жаргона [на основе указанных языков]. Вещи действительно ломаются в случае коротких ручных жаргонов, из-за которых такие буквы, как гласные, как правило, опускаются.

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

ответил mjv 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 15 Sep 2011 02:17:47 +0400 2011, 02:17:47
0

Из описания в статье ваша реализация кажется правильной (часть, которую вы помечаете как «что делать здесь», действительно не должна быть ничем).

Если у вас возникли проблемы с локальными максимумами (что, как утверждает статья, следует избегать при подбрасывании монет), убедитесь, что ваши реализации Initial, Transpose, ComputePl и Flip верны.

Вы также можете попробовать сделать монету смещенной (увеличение вероятности Flip () == 1 сделает это ближе к случайной прогулке и менее подвержено застреванию).

Вот немного более узкая версия вашего кода:

var current_f = Initial();    // current accepted function f
var current_Pl_f = ComputePl(current_f);  // current plausibility of accepted function f

for (int i = 0; i < 10000; i++)
{
    var candidate_f = Transpose(current_f); // create a candidate function
    var candidate_Pl_f = ComputePl(candidate_f);  // compute its plausibility

    if (candidate_Pl_f > current_Pl_f  ||  Flip() == 1)
    {
        // either candidate Pl has improved,
        // or it hasn't and we flipped the coin in candidate's favor
        //  - accept the candidate
        current_f = candidate_f;            
        current_Pl_f = candidate_Pl_f; 
    }
}
ответил Stjepan Rajko 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 15 Sep 2011 02:15:43 +0400 2011, 02:15:43
0

Этот алгоритм, похоже, связан с http://en.wikipedia.org/wiki/Simulated_annealing. В этом случае этому поведению может помочь изменение вероятности, с которой вы принимаете более слабые альтернативы текущему решению, особенно если вы уменьшаете эту вероятность с течением времени.

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

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

ответил mcdowella 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 15 Sep 2011 07:48:46 +0400 2011, 07:48:46

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132