이게 뭐야?

가중치 랜덤 복원 추출 알고리즘인 Walker's Alias ​​Method 정보

가중치 랜덤 복원 추출

요소별로 추첨 될 확률이 다르며 (가중)
선택한 요소를 매번 모집단으로 되돌리는 추출 방법 (복원 추출)
것.
솔직하게 구현하면
무게를 달고 무작위로 뭔가를 내고 싶다.
가중치 랜덤
같아요.
선형 탐색으로 구현하면 계산량은 추첨 1회마다 O(n)
바이너리 검색이라면 준비에 O(n), 추첨 1회마다 O(log n)

Walker's Alias ​​Method

준비에 O(n)로, 추첨 1회마다 무려 O(1)라고 하는 알고리즘.
같은 큰 집단에 대해 여러 번 추첨해야 하는 용도용.
(GA라든지 입자 필터라든지.)
구그라면 알기 쉬운 설명이 나옵니다.



그림 위와 같은 가중치 목록에서,
난수가 3~4일 때 어느 요소를 추출할지를 최고로 2회 판정할 필요가 있습니다.
이것을 아래와 같은 리스트로 재정렬했다고 하면(임계치 리스트와 별명 리스트를 생성한다),
난수의 정수 부분과 소수 부분을 사용하여 한 번의 비교만으로 추출할 수 있게 됩니다.
예를 들어 아래 목록에서
1.1을 뺀 경우, 정수부가 1이므로 임계치 리스트의 요소 1:p[1]을 보고,
소수 부분 0.1은 p[1]을 초과하지 않으므로 요소 1을 선택합니다.
2.5를 뺀 경우, 정수부가 2이므로 임계치 리스트의 요소 1:p[2]를 보고,
소수 부분 0.5는 이것을 초과하므로 별칭 목록 a[2]의 내용인 요소 0을 선택합니다.

적절한 구현 (C #)

public class WalkersAliasMethod
{
    private double[] probList;
    private int[] aliasList;
    private double[] weightList;
    private Random rnd;

    public WalkersAliasMethod()
    {
        rnd = new Random();
    }

    public WalkersAliasMethod(int seed)
    {
        rnd = new Random(seed);
    }

    //準備
    public void UpdateList(double[] weightList)
    {
        probList = new double[weightList.Length];
        aliasList = new int[weightList.Length];
        this.weightList = weightList;
        int size = weightList.Length;
        double[] norWeightList = new double[size];
        weightList.CopyTo(norWeightList, 0);
        double sum = weightList.Sum();
        double[] v = new double[size];//0~要素数で正規化された確率リスト
        for (int i = 0; i < size; i++)
        {
            norWeightList[i] /= sum;
            v[i] = norWeightList[i] * size;
        }

        List<int> small = new List<int>();
        List<int> large = new List<int>();

        for (int i = 0; i < size; i++)
        {

            if (v[i] < 1)
                small.Add(i);
            else
                large.Add(i);
        }

        int g, l;
        while (small.Count > 0 && large.Count > 0)
        {
            l = small[0];
            g = large[0];
            small.RemoveAt(0);
            large.RemoveAt(0);

            probList[l] = v[l];
            aliasList[l] = g;
            v[g] += -1.0 + v[l];
            if (v[g] < 1)
                small.Add(g);
            else
                large.Add(g);
        }
        while (large.Count > 0)
        {
            g = large[0];
            large.RemoveAt(0);
            probList[g] = 1;
        }
        while (small.Count > 0)
        {
            l = small[0];
            small.RemoveAt(0);
            probList[l] = 1;
        }
    }

    //重みを元にランダムに復元抽出してインデックスを返す
    public int Resampling()
    {
        double v = rnd.NextDouble() * (double)weightList.Length;
        int k = (int)v;
        double u = 1 + k - v;
        if (u < probList[k])
        {
            return k;
        }
        return aliasList[k];
    }
}