Muestra aleatoria ponderada de elementos de la matriz * sin reemplazo *

Question

Se desea una solución específica de Javascript / ECMAScript 6.

Quiero generar una muestra aleatoria a partir de una matriz de objetos utilizando una matriz de valores ponderados para cada objeto. La lista de población contiene los miembros reales de la población, no los tipos de miembros. Una vez que se selecciona uno para una muestra, no se puede volver a seleccionar.

Un problema análogo al que estoy trabajando sería simular un resultado probable para un torneo de ajedrez. La calificación de cada jugador sería su peso. Un jugador solo puede colocar una vez (1º, 2º o 3º lugar) por torneo.

Para elegir una lista probable de los 3 primeros ganadores, podría verse así:

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

La lista ponderada puede ser, o no, valores enteros. Pueden ser como flotantes [0.2, 0.1, 0.7, 0.3]o enteros como [20, 10, 70, 30]. Los pesos no tienen que sumar un valor que represente el 100%.

Peter a continuación me dio una buena referencia sobre un algoritmo general, sin embargo, no es específico de JS: https://stackoverflow.com/a/62459274/7915759 puede ser un buen punto de referencia.

Las soluciones al problema que se basan en generar una segunda lista de población con cada miembro copiado un número de veces de peso pueden no ser una solución práctica. Cada peso en la matriz de pesos puede ser un número muy alto o puede ser fraccionario; básicamente, cualquier valor no negativo.

Algunas preguntas adicionales:

• ¿Ya hay una accumulate()función disponible en JS?
• ¿Existe una bisect()función de tipo en JS que realiza una búsqueda binaria de listas ordenadas?
• ¿Hay módulos JS eficientes y de baja huella de memoria disponibles con funciones estadísticas que incluyan soluciones para lo anterior?

Answer 1

La siguiente implementación selecciona kfuera de nelementos, sin reemplazo, con probabilidades ponderadas, en O (n + k log n), manteniendo los pesos acumulados de los elementos restantes en un montón suma :

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;
}

El código está escrito en TypeScript. Puede transpilarlo a cualquier versión de EcmaScript que necesite en el campo de juegos de TypeScript .

Código de prueba:

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")

Ejecutado en Chrome, muestra 5 000 000 de 10 000 000 entradas en aproximadamente 10 segundos.

Answer 2

Este es un enfoque, pero no el más eficiente.

La función de más alto nivel. Itera kveces, llamando wchoice()cada vez. Para eliminar el miembro actualmente seleccionado de la población, simplemente establezco su peso en 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];
}

La sección de código anterior que actualiza la matriz de pesos acumulados es el punto de ineficiencia en el algoritmo. En el peor de los casos, es O(n - ?)actualizar en cada pasada. Otra solución aquí sigue un algoritmo similar a este, pero usa un montón para reducir el trabajo necesario para mantener la matriz de pesos acumulados en O(log n).

wsample()llamadas wchoice()que selecciona un miembro de la lista ponderada. wchoice()genera una matriz de ponderaciones acumulativas, genera un número aleatorio desde 0 hasta la suma total de las ponderaciones (último elemento de la lista de ponderaciones acumulativas). Luego encuentra su punto de inserción en los pesos acumulativos; cual es el ganador:

/**
 * 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]];
}

Aquí hay una implementación de JS que adapté del algoritmo de búsqueda binaria 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;
}

No pude encontrar una función de acumulador preparada para JS, así que escribí una simple yo mismo.

/**
 * 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;
}