在 Bonferroni 不等式的 JS 实现中避免多重循环

Question

我正在尝试实现 "Bonferroni inequality"，它使用 Javascript UDF 为 GCP BigQuery 上的数据科学用例的许多独立事件的联合概率建模。但是我对 JS 很陌生，不知道好的做法。

要应用的公式如下：

P(U Ai) = SUM(P(Ai)) - SUM(P(Ai)*P(Aj)) + SUM(P(Ai)*P(Aj)*P(Ak) - ... i != j != k

我对此函数的输入是单个事件概率的数组：

[P(A1), P(A2), P(A3), ...]

我本能地在行中制作了 "for loops" 来获得结果，但是，看到如此丑陋的代码让人心痛，所以想知道你们中的任何人是否有关于如何以更优雅和优化的方式实现它的想法方式？

这是我为 4 级 Bonferroni 不等式编写的函数：

function unionBoundProbability(probList){

  var intersection2 = 0;
  var intersection3 = 0;
  var intersection4 = 0;
  var i = 0;
  var j = 0;
  var k = 0;
  var l = 0;
  var sum = 0;
  var product = 1;

  var sum = probList.reduce((a, b) => a + b, 0);

  for(i = 0; i < probList.length; i++){
    product *= probList[i];
    for(j = i+1; j < probList.length; j++){
      intersection2 += probList[i]*probList[j];
      for(k = j+1; k < probList.length; k++){
        intersection3 += probList[i]*probList[j]*probList[k];
        for(l = k+1; l < probList.length; l++){
          intersection4 += probList[i]*probList[j]*probList[k]*probList[l];
        }
      }
    }
  }

  switch (probList.length) {
    case 0:
      return 0;
      break;
    case 1:
      return probList[0];
      break;
    case 2:
      return sum - product;
      break;
    case 3:
      return sum - intersection2 + product;
      break
    case 4:
      return sum - intersection2 + intersection3 - product;
    case 5 :
      return sum - intersection2 + intersection3 - intersection4 + product;
    default:
      return Math.max((sum - intersection2 + intersection3  - intersection4), Math.max.apply(Math, probList));
  }
}

我想做的是计算作为输入传递的所有概率的并集概率的近似值。

如果我的概率小于 5，则 switch 语句应用确切的公式。否则，默认情况下应用 Bonferroni 近似，（因为我正在模拟接收信号的机会，如果估计小于最好天线的概率，那么我保留最好的天线）。

感谢您的帮助

Answer 1

此示例遵循 https://www.probabilitycourse.com/chapter6/6_2_1_union_bound_and_exten.php

中的以下等式

P(⋃(i=1 => n)Ai)=∑(i=1 => n) P(Ai) − ∑(i<j) P(Ai ∩ Aj) + ∑(i<j<k) P(Ai ∩ Aj ∩ Ak) − ... +(−1)^n−1 P(⋂(i=1 => n) Ai)

我不知道你在给出的例子中包含阶乘的原因，但我没有包含阶乘，因为它们不在上面的等式中。

// Recursive function to update sums of each level
function updateSums(sums, probList, maxLevel, currentLevel = 1, currentProduct = 1, lastIndex = -1) {
  // Example case: maxLevel = 4, curentLevel = 3, path = { 1: 0, 2: 1 }, currentProduct = probList[0] * probList[1]
  // Loops through all entries except 0 and 1 and adds the products to sums[2], for each entry also calculates level 4 sums

  for (let i = lastIndex + 1; i < probList.length; i++) {
    const nextProduct = currentProduct * probList[i];
    sums[currentLevel - 1] += nextProduct;

    if (currentLevel < maxLevel) {
      // get the next level product sums for current product
      updateSums(sums, probList, maxLevel, currentLevel + 1, nextProduct, i);
    }
  }
}

// Main function
function inequality(probList) {
  probList = probList.sort((a, b) => b - a).slice(0, 4);

  // Calculate maxLevel
  const maxLevel = probList.length;
  if (!maxLevel) return 0;

  // create am array of sums, each entry represents 1 level
  const sums = (new Array(maxLevel)).fill(0);
  updateSums(sums, probList, maxLevel);

  return sums.reduce((a, c, i) => {
    return a + ((i % 2) ? -1 : 1) * c;
  }, 0);
}

console.log(inequality(probList));

PS: This is written in ES6

Answer 2

我们可以避免再次发生

说 A 大小 n

根据你的公式我们可以考虑

我们从 A 中取出 1 个元素：C_n^1
我们从 A 中取出 2 个元素：C_n^2
我们从 A 中取出 3 个元素：C_n^3

不是重新计算每个k-utuple（无序元组），我们可以简单地保留上一层的(k-1)-utuples 例如，让我们采用数组 [1,2,3,4,5]

第一层：1,2,3,4,5
第二层：1-2, 1-3, 1-4, 1-5, 2-3, 2-4, ..., 4-5
第三层：1-2-{i}（i代表3到5），1-3-{i}，...

对于我们的案例：我们真的不需要整个元组：只需要它的最后一个 idx 和它的值（它的元素的乘积）

算法像

function bonferroni(A, nlev){
    let lv = 0;
    let tot = 0;
    //i refers to the index of the last element added to the tuple
    //s refers to its value
    //here we initialize with i=-1 just so the first while loop builds an equivalent of "A"
    let layer = [{i:-1, s:1}];
    while(lv < nlev){
        let sum = 0;
        let next = [];
        layer.forEach(utuple=>{

            for(let i = utuple.i+1; i<A.length; ++i){
                let s = utuple.s * A[i];
                sum += s;
                next.push({i, s});
            }
        })
        layer = next;
        if((lv % 2)==0){
            tot += sum;
        }else{
            tot -= sum;
        }
        lv++;
    }
    return tot;
}

详细版本为：

function bonferroniVerbose(A, nlev){
    let lv = 0;
    let tot = 0;
    //i refers to the index of the last element added to the tuple
    //s refers to its value
    //here we initialize with i=-1 just so the first while loop builds an equivalent of "A"
    let layer = [{t:[], i:-1, s:1}];
    while(lv < nlev){
        console.log('--------------layer', lv);
        let sum = 0;
        let next = [];
        layer.forEach(utuple=>{

            for(let i = utuple.i+1; i<A.length; ++i){
                let s = utuple.s * A[i];
                sum += s;
                let t = utuple.t.concat(A[i]);
                next.push({t, i, s});
                console.log('summing', t.join('*'), '->', s);
            }
        })
        layer = next;
        if((lv % 2)==0){
            tot += sum;
        }else{
            tot -= sum;
        }
        lv++;
    }
    return tot;
}
console.log(bonferroniVerbose([1,2,3,4,5], 3))

在 Bonferroni 不等式的 JS 实现中避免多重循环

Avoid multiple loops in JS implementation of Bonferroni inequality

javascript

algorithm

loops

bonferroni