2
$\begingroup$

Computer science guy here. Fully prepared to field any collective groaning that may elicit. I have a particular problem I'm trying to solve and have gotten much closer in the past few days to figuring out a solution, but feel like I'm getting buried in a stack of concepts and need to see the light at the end of the tunnel.

The problem is as such (generalized): I have a large number of data points collected from a distributed system. Each represents a group of entities (let's label the entities A to Z) and a success or failure. I am aggregating these into a success rate (successes / (successes + failures)) associated with that group of entities. For instance, [A, B, F, J] may have a success rate of 0.95 while [B, F, M, Z] may have a success rate of 0.9991. In each individual sample that is eventually aggregated, a failure of one or more entities results in a failure for that group of entities – in other words, a success for the group is predicated on a success for each member of the group. Each group would be a small subset of the total set of entities.

I would like to take the total collection of success rates and their associated groups of entities, and derive the likelihood of any particular entity to be successful.

Here are some concepts I have found to be relevant to the problem:

  • I believe the result I am looking for can be though of as a Bernoulli distribution for each entity.
  • Each aggregated success rate recorded for a group of entities is the intersection of these Bernoulli distributions.
  • At first I though the aggregated success rates were Poisson-binomial distributions, but they are products (intersections) and not sums of the underlying distributions.
  • I may be able to get what I'm looking for through regression analysis by treating the failure rates as a dependent variable and the presence of each entity as a binary categorical variable. I don't fully understand how the sparseness of the categorical variables in this case would affect the regression or what regression technique would be most appropriate.

I've looked at and read a lot more than that (especially here on Cross Validated, and am very thankful for its existence!) but so far these are the only concepts that have stuck out as being relevant to the problem.

$\endgroup$
  • $\begingroup$ I am not certain if I understand your question correctly. Does this sound right: You have a set $C=\{A,B\}$ with probability of success $p[C]$, and success occurs only when both $A$ and $B$ succeed. If $A$ and $B$ are independent, then you should have $p[C]=p[A]p[B]$. (If correct, this immediately generalizes to $p[\bigcup_iA_i]=\prod_ip[A_i]$) $\endgroup$ – GeoMatt22 Sep 12 '16 at 23:44
  • $\begingroup$ Hey @GeoMatt22 – that is very close to the problem at hand. Your description is accurate until the parenthetical bit, if I rephrase the problem in terms of success rates instead of failure rates (which is fine). Assuming I have a large set of C's, each representing different subsets of As, Bs, etc, I'm looking for a way to estimate p[A], p[B], etc, each of which will be the individual success or failure probabilities. I would love to have some measure of confidence for that probability as well. $\endgroup$ – Adam Crane Sep 13 '16 at 22:03
  • $\begingroup$ I've reworded my question in terms of success rates in the hopes that it will be easier to grok. $\endgroup$ – Adam Crane Sep 13 '16 at 22:44
  • $\begingroup$ Are you familiar with matrix equations (systems of linear equations)? Based on my previous comment, a next step could be to take the log of my last parenthetical, which turns it into a linear equation. Then you could make a binary (boolean) matrix $M$ with one row for each set $C$, and one column for each "entity" $A$, where $M_{ij}$ indicates presence/absence (1 or 0) of entity $A_j$ in set $C_i$. Then my model implies the matrix equation $M\log p[A]=\log p[C]$. This could then be solved (in a least squares sense) to get $\log p[A]$. Not sure how to do confidence though. $\endgroup$ – GeoMatt22 Sep 13 '16 at 23:06
3
$\begingroup$

Here is one possible solution, although I not certain of its theoretical properties or assumptions.

Given a two-element collection $C=\{A,B\}$ where success occurs only when both $A$ and $B$ succeed, what is the probability of success $p[C]$?. If $A$ and $B$ are independent, then $p_C=p_Ap_B$.

For an arbitrary collection of independent elements this generalizes to $$C=\bigcup_iA_i \implies p[C]=\prod_ip[A_i]$$

Now say you have $m$ sets $C_1,\ldots,C_m$, which are subsets of the $n$ element collection $\{A_1,\ldots,A_n\}$. Then from the above equation, we have $$p[C_i]=\prod_{A_j\in C_i}p[A_j],\quad i=1,\ldots,m$$ Now define an occurence matrix by $$M_{ij}=\begin{cases} 1 & A_j\in C_i \\ 0 & A_j\notin C_i\end{cases}$$ and a set of (minus) log probabilities by $$y_i=-\log(p[C_i]),\quad x_j=-\log(p[A_j])$$

Then the constraint system above is equivalent to the system of linear equations $$\sum_{j=1}^nM_{ij}x_j=y_i,\quad i=1,\ldots,m$$ If I understand your problem correctly, then the matrix $M$ and the vector $y$ are known, and you wish to estimate the vector $x$. In this case, you could get an approximate solution to the matrix system $$Mx\approx y$$ by a standard algorithm known as non-negative least squares, which enforces the constraint $x\geq0$ (corresponding to $p[A]\in[0,1]$).

UPDATE: Towards Confidence Estimates?

Say the set $C_i=\{A_j|M_{ij}=1\}$ occurs $N_i$ times in your data set, with $K_i$ successes. Let $q_i=p[C_i]$ be the probability of success for each (independent) occurrence of $C_i$. Then $K_i$ will have a binomial distribution with parameters $q_i$ and $N_i$. However, the variable $q_i$ is not known, but must be estimated from the data. In this case, for a uniform prior (i.e. before seeing the data, $p[q]=1$), the posterior probability $p[q_i|K_i,N_i]$ will be beta distributed (with parameters $\alpha=K_i+1$, $\beta=N_i+K_i+1$).

Given this, the posterior mode is $(q_i)_{\mathrm{MAP}}=K_i/N_i$, i.e. the same as your current estimate. However the full PDF for $q_i$ should be able to be used to 1) weight the "$y_i$" equation in the estimation problem, and 2) get uncertainties for the "$x_j$" solution to the matrix problem. I am not quite certain how to do this, however. (It may be possible to formulate the problem as a Generalized linear model?)

$\endgroup$
  • $\begingroup$ Thanks! You definitely nailed the problem. One assumption that we have to make is that the product of Bernoulli distributions is also a Bernoulli distribution – and from what I've read this happens to be true. $\endgroup$ – Adam Crane Sep 14 '16 at 7:49
  • $\begingroup$ The log transformation was what I needed to get from my last bullet point to the regression. I believe a key to getting some kind of confidence measure is to also include the success and failure counts in my data to compute something like a Wilson score interval for each $p[A_j]$. $\endgroup$ – Adam Crane Sep 14 '16 at 7:57
  • $\begingroup$ But we don't need confidences for probabilities of groups, we need confidences for probabilities of entities. The posterior $p(A_j \mid M)$ is not guaranteed to be Beta-distributed, moreover, the joint $p(A_1, ..., A_N \mid M)$ does not seem to factorize. $\endgroup$ – Artem Sobolev Sep 16 '16 at 3:21
  • $\begingroup$ Barmaley, I agree that is the end goal. In the first instance, the uncertainty of $p(q|K,N)$ would be needed to account for the different confidences in my "$Mx\approx y$" system, i.e. rows $i$ corresponding to "big" $N_i$ would be more important to fit, compared to "small' $N_i$ (comparable to something like "heteroskedasticity"). In the second instance, after posting the last update, I realized if the priors on the $p_j$'s are at all close to uniform, and they are independent, then the prior on $q_i$ must depend on $m_i=\sum_jM{ij}=|C_i|$, i.e. becoming more positively skewed for "big" sets. $\endgroup$ – GeoMatt22 Sep 16 '16 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.