Amostra aleatória ponderada de itens da matriz * sem substituição *

Question

Solução específica Javascript / ECMAScript 6 desejada.

Quero gerar uma amostra aleatória de uma matriz de objetos usando uma matriz de valores ponderados para cada objeto. A lista de população contém os membros reais da população - não os tipos de membros. Uma vez que um é selecionado para uma amostra, não pode ser selecionado novamente.

Um problema análogo ao que estou trabalhando seria simular um resultado provável para um torneio de xadrez. A classificação de cada jogador seria seu peso. Um jogador só pode se classificar uma vez (primeiro, segundo ou terceiro) por torneio.

Para escolher uma lista provável dos 3 principais vencedores, pode ser assim:

let winners = wsample(chessPlayers,  // population
                      playerRatings, // weights
                      3);            // sample size

A lista ponderada pode, ou não, ser valores inteiros. Podem ser flutuantes [0.2, 0.1, 0.7, 0.3], ou inteiros [20, 10, 70, 30]. Os pesos não precisam somar um valor que represente 100%.

Peter abaixo me deu uma boa referência sobre um algoritmo geral, no entanto, não é específico para JS: https://stackoverflow.com/a/62459274/7915759 pode ser um bom ponto de referência.

Soluções para o problema que dependem da geração de uma segunda lista de população com cada membro copiado por número de peso de vezes podem não ser uma solução prática. Cada peso na matriz de pesos pode ser um número muito alto ou fracionário; basicamente, qualquer valor não negativo.

Algumas perguntas adicionais:

• Já existe uma accumulate()função disponível em JS?
• Existe uma bisect()função de tipo em JS que faz uma pesquisa binária de listas classificadas?
• Existem módulos JS eficientes e de baixo consumo de memória com funções estatísticas que incluem soluções para os itens acima?

Answer 1

Os seguintes selecciona implementação kfora de nelementos, sem reposição, com probabilidades ponderados, em O (n + k log N), mantendo-os pesos acumuladas dos restantes elementos em uma pilha de soma :

function sample_without_replacement<T>(population: T[], weights: number[], sampleSize: number) {

    let size = 1;
    while (size < weights.length) {
        size = size << 1;
    }

    // construct a sum heap for the weights
    const root = 1;
    const w = [...new Array(size) as number[], ...weights, 0];
    for (let index = size - 1; index >= 1; index--) {
        const leftChild = index << 1;
        const rightChild = leftChild + 1;
        w[index] = (w[leftChild] || 0) + (w[rightChild] || 0);
    }

    // retrieves an element with weight-index r 
    // from the part of the heap rooted at index
    const retrieve = (r: number, index: number): T => {
        if (index >= size) {
            w[index] = 0;
            return population[index - size];
        } 
        
        const leftChild = index << 1;
        const rightChild = leftChild + 1;

        try {
            if (r <= w[leftChild]) {
                return retrieve(r, leftChild);
            } else {
                return retrieve(r - w[leftChild], rightChild);
            }
        } finally {
            w[index] = w[leftChild] + w[rightChild];
        }
    }

    // and now retrieve sampleSize random elements without replacement
    const result: T[] = [];
    for (let k = 0; k < sampleSize; k++) {
        result.push(retrieve(Math.random() * w[root], root));
    }
    return result;
}

O código é escrito em TypeScript. Você pode transpilar para qualquer versão do EcmaScript que você precisa no playground do TypeScript .

Código de teste:

const n = 1E7;
const k = n / 2;
const population: number[] = [];
const weight: number[] = [];
for (let i = 0; i < n; i++) {
    population[i] = i;
    weight[i] = i;
}

console.log(`sampling ${k} of ${n} elments without replacement`);
const sample = sample_without_replacement(population, weight, k);
console.log(sample.slice(0, 100)); // logging everything takes forever on some consoles
console.log("Done")

Executado no Chrome, faz a amostragem de 5.000.000 de 10.000.000 entradas em cerca de 10 segundos.

Answer 2

Esta é uma abordagem, mas não a mais eficiente.

A função de nível mais alto. Ele itera kvezes, chamando a wchoice()cada vez. Para remover o membro atualmente selecionado da população, apenas defini seu peso como 0.

/**
 * Produces a weighted sample from `population` of size `k` without replacement.
 * 
 * @param {Object[]} population The population to select from.
 * @param {number[]} weights    The weighted values of the population.
 * @param {number}   k          The size of the sample to return.
 * @returns {[number[], Object[]]} An array of two arrays. The first holds the
 *                                 indices of the members in the sample, and
 *                                 the second holds the sample members.
 */
function wsample(population, weights, k) {
    let sample  = [];
    let indices = [];
    let index   = 0;
    let choice  = null;
    let acmwts  = accumulate(weights);

    for (let i=0; i < k; i++) {
        [index, choice] = wchoice(population, acmwts, true);
        sample.push(choice);
        indices.push(index);

        // The below updates the accumulated weights as if the member
        // at `index` has a weight of 0, eliminating it from future draws.
        // This portion could be optimized. See note below.
        let ndecr = weights[index];
        for (; index < acmwts.length; index++) {
            acmwts[index] -= ndecr;
        }
    }
    return [indices, sample];
}

A seção de código acima que atualiza a matriz de pesos acumulados é o ponto de ineficiência do algoritmo. Na pior das hipóteses, é O(n - ?)para atualizar a cada passagem. Outra solução aqui segue um algoritmo semelhante a este, mas usa um heap para reduzir o trabalho necessário para manter a matriz de pesos acumulados em O(log n).

wsample()chamadas wchoice()que seleciona um membro da lista ponderada. wchoice()gera uma matriz de pesos cumulativos, gera um número aleatório de 0 à soma total dos pesos (último item na lista de pesos cumulativos). Em seguida, encontra seu ponto de inserção nos pesos cumulativos; qual é o vencedor:

/**
 * Randomly selects a member of `population` weighting the probability each 
 * will be selected using `weights`. `accumulated` indicates whether `weights` 
 * is pre-accumulated, in which case it will skip its accumulation step.
 * 
 * @param {Object[]} population    The population to select from.
 * @param {number[]} weights       The weights of the population.
 * @param {boolean}  [accumulated] true if weights are pre-accumulated.
 *                                 Treated as false if not provided.
 * @returns {[number, Object]} An array with the selected member's index and 
 *                             the member itself.
 */
function wchoice(population, weights, accumulated) {
    let acm = (accumulated) ? weights : accumulate(weights);
    let rnd = Math.random() * acm[acm.length - 1];

    let idx = bisect_left(acm, rnd);

    return [idx, population[idx]];
}

Aqui está uma implementação JS que adaptei do algoritmo de pesquisa binária de https://en.wikipedia.org/wiki/Binary_search_algorithm

/**
 * Finds the left insertion point for `target` in array `arr`. Uses a binary
 * search algorithm.
 * 
 * @param {number[]} arr    A sorted ascending array.
 * @param {number}   target The target value.
 * @returns {number} The index in `arr` where `target` can be inserted to
 *                   preserve the order of the array.
 */
function bisect_left(arr, target) {
    let n = arr.length;
    let l = 0;
    let r = n - 1;
    while (l <= r) {
        let m = Math.floor((l + r) / 2);
        if (arr[m] < target) {
            l = m + 1;
        } else if (arr[m] >= target) {
            r = m - 1;
        } 
    }
    return l;
}

Não consegui encontrar uma função de acumulador pronta para JS, então escrevi uma simples.

/**
 * Generates an array of accumulated values for `numbers`.
 * e.g.: [1, 5, 2, 1, 5] --> [1, 6, 8, 9, 14]
 * 
 * @param {number[]} numbers The numbers to accumulate.
 * @returns {number[]} An array of accumulated values.
 */
function accumulate(numbers) {
    let accm  = [];
    let total = 0;
    for (let n of numbers) {
        total += n;
        accm.push(total)
    }
    return accm;
}