Algoritmo per il calcolo della plausibilità di un metodo funzione / monte carlo
-
30-10-2019 - |
Domanda
Sto scrivendo un programma che tenta di duplicare l'algoritmo discusso all'inizio di questo articolo,
http://www-stat.stanford.edu/~cgates/persi/papers/mcmcrev.pdf
F è una funzione da char to char. Supponiamo che PL (F) sia una misura di "plausibilità" di quella funzione. L'algoritmo è:
A partire da un'ipotesi preliminare alla funzione, diciamo f e una nuova funzione f* -
- Calcola PL (F).
- Modifica in F* effettuando una trasposizione casuale dei valori F assegna a due simboli.
- Calcola pl (f*); Se questo è più grande di PL (F), accetta f*.
- In caso contrario, capovolgere una moneta PL (f)/pl (f*); Se si presenta alla testa, accetta f*.
- Se il lancio della moneta si avvicina, rimani a f.
Lo sto implementando usando il seguente codice. Sto usando C# ma ho provato a renderlo un po 'più semplificato per tutti. Se c'è un forum migliore per questo, fammelo sapere.
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 ?
}
}
}
La mia domanda è fondamentalmente se questo sembra l'approccio ottimale all'implementazione di quell'algoritmo. Sembra che potrei rimanere bloccato in alcuni massimi locali / minimi locali nonostante abbia implementato questo metodo.
MODIFICARE - Ecco essenzialmente il metodo Transpose (). Uso un dizionario / hash tabella di tipo << char, char >> che le funzioni candidate utilizzano per apparire una determinata trasformazione di char -> char. Quindi il metodo di trasposizione scambia semplicemente due valori nel dizionario che determina il comportamento della funzione.
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;
}
Tieni presente che una funzione candidata che utilizza il dizionario sottostante è fondamentalmente:
public char GetChar(char in, Dictionary<char, char> theMap)
{
return theMap[char];
}
E questa è la funzione che calcola 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;
}
Nessuna soluzione corretta