10.3.1 The Derivation

In estimation theory, a recursive formula of the EM scheme estimates parameters of the model in consecutive time intervals as follows [91]:

$\begin{array}{l}\hfill {\widehat{\theta }}_{k+1}=\widehat{{\theta }_k}+{\{(k+1)I_c(\widehat{{\theta }_k})\}}^{-1}{V}_n(X_{k+1},\widehat{{\theta }_k})\end{array}$

where $\widehat{{\theta }_k}$ is the estimation parameter by observing the data up to the time interval k, $I_c(\widehat{{\theta }_k})$ represents the “complete” Fisher information matrix, which is the expected value of Fisher information matrix average over the missing data at time k. In this work, we take the asymptotic CRLB from Chapter 6, which is slightly different than the inverse of the “complete” Fisher information matrix. This is one of the key distinctions of the approach in [91] vice using the actual Fisher information. $V_n(X_{k+1},\widehat{{\theta }_k})$ is the score function (defined in Equation (3.10)) of the observed data at time interval k + 1 w.r.t. the estimation parameter $\widehat{{\theta }_k}$. Authors in [91] state that we can take expectation of the score function over the missing data instead of the score function itself. The above formula basically provides us a recursive way to compute the estimation parameter in the new time interval (i.e., ${\widehat{\theta }}_{k+1}$) based on its estimation value in the previous time interval (i.e., ${\widehat{\theta }}_k$), the complete CRLB of the estimation (i.e., $I_c^{-1}(\widehat{{\theta }_k})$) and the score function of the updated data observed in the new interval (i.e., $V_n(X_{k+1},\widehat{{\theta }_k})$). Based on the results are from Chapter 6 (under the assumption that the number of sources is sufficiently large to reach this asymptotic results) of the EM scheme, $\widehat{{\theta }_k}$ is the estimation vector defined as $\widehat{{\theta }_k}=({â}_1^k,{â}_2^k,\dots ,{â}_M^k;{\widehat{b}}_1^k,{\widehat{b}}_2^k,\dots ,{\widehat{b}}_M^k)$. $I_c^{-1}(\widehat{{\theta }_k})$ and $\psi (X_{k+1},\widehat{{\theta }_k})$ are given by the asymptotic CRLB from Chapter 6 (see Equation (6.16)):

$\begin{array}{l}\hfill I_c^{-1}{(\widehat{{\theta }_k})}_{i,j}=\left\{\begin{array}{ll}0& i\ne j\\ \frac{{â}_i^k\times (1-{â}_i^k)}{\sum _j{Z}_j}& i=j\in [1,M]\\ \frac{{\widehat{b}}_i^k\times (1-{\widehat{b}}_i^k)}{\sum _j(1-Z_j)}& i=j\in (M,2M]\end{array}\right.\end{array}$

and the score function is:

$\begin{array}{l}\hfill V_n{(X_{k+1},\widehat{{\theta }_k})}_j=\left\{\begin{array}{ll}\sum _{j=1}^N{\widehat{Z_j}}^{k+1}\left(\frac{X_{i,j}}{{â}_i^k}-\frac{1-X_{i,j}}{1-{â}_i^k}\right)& i=j\text{for}i\in [1,M]\\ \sum _{j=1}^N(1-{\widehat{Z_j}}^{k+1})\left(\frac{X_{i,j}}{{\widehat{b}}_i^k}-\frac{1-X_{i,j}}{1-{\widehat{b}}_i^k}\right)& i=j-M\text{for}i\in [M+1,2M]\end{array}\right.\end{array}$

where ${\widehat{Z_j}}^{k+1}$ is the probability of the jth claim to be true in the k + 1 time interval. Plugging Equations (10.7) and (10.8) into (10.6), the recursive formula to update the estimation parameters is given by:

$\begin{array}{ll}\hfill {\widehat{a_i}}^{k+1}& ={\widehat{a_i}}^k+\frac{1}{Nd(k+1)}\times \left[\sum _{j\in S{J}_i^{k+1}}{\widehat{Z_j}}^{k+1}(1-{\widehat{a_i}}^k)-\sum _{j\in {\stackrel{-}{S{J}_i}}^{k+1}}{\widehat{Z_j}}^{k+1}{\widehat{a_i}}^k\right]\hfill \\ \hfill {\widehat{b_i}}^{k+1}& ={\widehat{b_i}}^k+\frac{1}{Nd(k+1)}\times \left[\sum _{j\in S{J}_i^{k+1}}(1-{\widehat{Z_j}}^{k+1})(1-{\widehat{b_i}}^k)-\sum _{j\in {\stackrel{-}{S{J}_i}}^{k+1}}(1-{\widehat{Z_j}}^{k+1}){\widehat{b_i}}^k\right]\hfill \end{array}$

From above equations, one can observe that the estimation of the parameters related with reliability of each source in current time interval can be computed from their estimations in the past and the observed data in the new interval. Moreover, ${\widehat{Z_j}}^{k+1}$ is unknown and can be estimated by its approximation ${\widetilde{Z_j}}^{k+1}$, which can be computed as follows:

$\begin{array}{ll}\hfill {\widetilde{Z_j}}^{k+1}& =f({\widetilde{a_i}}^{k+1},{\widetilde{b_i}}^{k+1},X_{k+1})\hfill \\ \hfill & =\frac{A_j^{k+1}\times d}{A_j^{k+1}\times d+B_j^{k+1}\times (1-d)}\hfill \end{array}$

where

$\begin{array}{ll}\hfill A_j^{k+1}& =\prod _{i=1}^M{({\widetilde{a_i}}^{(k+1)})}^{{X_{i,j}}^{k+1}}{(1-{\widetilde{a_i}}^{(k+1)})}^{(1-X_{i,j}^{k+1})}\hfill \\ \hfill B_j^{k+1}& =\prod _{i=1}^M{({\widetilde{b_i}}^{(k+1)})}^{{X_{i,j}}^{k+1}}{(1-{\widetilde{b_i}}^{(k+1)})}^{(1-X_{i,j}^{k+1})}\hfill \\ \hfill {\widetilde{a_i}}^{k+1}& ={\widehat{a_i}}^k\times \frac{s_i^{k+1}}{s_i^k}{\widetilde{b_i}}^{k+1}={\widehat{b_i}}^k\times \frac{s_i^{k+1}}{s_i^k}\hfill \end{array}$

where $s_i^{k+1}$ and $s_i^k$ are the frequencies of source S_i reports a claim after iteration k + 1 and k (i.e., at time k + 1 and k). Note that $s_i^k$ can be computed as the percentage of all claims made by S_i relative to the total number of claims that it could have made, which is known from the observed data. For the above equation to hold, it is assumed that source reliability changes slowly over time and can be treated unchanged over two consecutive time intervals.

Based on the definition of ${\widetilde{Z_j}}^{k+1}$, it can be further represented as a function of ${\widehat{a_i}}^k,{\widehat{b_i}}^k,X_k,X_{k+1}$, the values of which are known at time interval k + 1:

$\begin{array}{ll}\hfill {\widetilde{Z_j}}^{k+1}& =g({\widehat{a_i}}^k,{\widehat{b_i}}^k,X_k,X_{k+1})\hfill \\ \hfill & =\frac{C_j^{k+1}\times d}{C_j^{k+1}\times d+D_j^{k+1}\times (1-d)}\hfill \end{array}$

where

$\begin{array}{ll}\hfill C_j^{k+1}& =\prod _{i=1}^M{\left({\widehat{a_i}}^k\times \frac{s_i^{k+1}}{s_i^k}\right)}^{{X_{i,j}}^{k+1}}{\left(1-{\widehat{a_i}}^k\times \frac{s_i^{k+1}}{s_i^k}\right)}^{(1-X_{i,j}^{k+1})}\hfill \\ \hfill D_j^{k+1}& =\prod _{i=1}^M{\left({\widehat{b_i}}^k\times \frac{s_i^{k+1}}{s_i^k}\right)}^{{X_{i,j}}^{k+1}}{\left(1-{\widehat{b_i}}^k\times \frac{s_i^{k+1}}{s_i^k}\right)}^{(1-X_{i,j}^{k+1})}\hfill \end{array}$

Plugging Equation (10.11) into Equation (10.9), the following recursive computation of the estimation parameters can be obtained:

$\begin{array}{ll}\hfill {\widehat{a_i}}^{k+1}& ={\widehat{a_i}}^k+\frac{1}{Nd(k+1)}\hfill \\ \hfill & \times \left[\sum _{j\in S{J}_i^{k+1}}g({\widehat{a_i}}^k,{\widehat{b_i}}^k,X_k,X_{k+1})(1-{\widehat{a_i}}^k)\right.\hfill \\ \hfill & \left.-\sum _{j\in {\stackrel{-}{S{J}_i}}^{k+1}}g({\widehat{a_i}}^k,{\widehat{b_i}}^k,X_k,X_{k+1}){\widehat{a_i}}^k\right]\hfill \\ \hfill {\widehat{b_i}}^{k+1}& ={\widehat{b_i}}^k+\frac{1}{Nd(k+1)}\hfill \\ \hfill & \times \left[\sum _{j\in S{J}_i^{k+1}}(1-g({\widehat{a_i}}^k,{\widehat{b_i}}^k,X_k,X_{k+1}))(1-{\widehat{b_i}}^k)\right.\hfill \\ \hfill & \left.-\sum _{j\in {\stackrel{-}{S{J}_i}}^{k+1}}(1-g({\widehat{a_i}}^k,{\widehat{b_i}}^k,X_k,X_{k+1})){\widehat{b_i}}^k\right]\hfill \end{array}$

Additionally, the updated correctness of claims (i.e., ${\widehat{Z_j}}^{k+1}$) can also be computed as follows:

$\begin{array}{l}\hfill {\widehat{Z_j}}^{k+1}=f({\widehat{a_i}}^{k+1},{\widehat{b_i}}^{k+1},X_{k+1})\end{array}$

where function f is the same as the one in Equation (10.10).

This gives us the recursive equations to compute the estimation parameters of the model in the current time interval based on the estimations from the previous time interval and the observed data up to now. Therefore, Equation (10.12) can be utilized to keep track of the estimation parameter of the sources that report new observations consecutively over time. We also note that the estimation parameter change of the updated sources will affect the credibility of claims they report, which in turn will affect the credibility of other sources asserting the same claim. We call this credibility update propagation “ripple effect.” To capture such an effect, a simple trick was designed: only run one EM iteration after applying the recursive formula (as compared to running the full version of EM from scratch). This turns out to be an efficient heuristic based on the following observations: (i) the recursive estimation already offers us a reasonably good initialization on the estimation parameter; (ii) the credibility change of sources by a few updates in a short time interval is usually slight. This allows the recursive EM to converge much faster than the batch algorithm that starts from a random point.

10.3.2 The Recursive EM Algorithm

In summary of the recursive EM algorithm derived above, the pseudocode of the algorithm is given in Algorithm 7. The algorithm runs when a new update X_k+1 arrives and it first computes the recursive update on the estimation parameter (i.e., ${\widehat{a_i}}^{k+1},{\widehat{b_i}}^{k+1}$) based on Equation (10.12). The correctness of claims are consequently updated from the estimation parameters based on Equation (10.13). The recursive algorithm runs one EM iteration to capture the “ripple effect” of the credibility prorogation as we discussed in the previous subsection. Thus the iteration only consider who are making the claims as the current time. After that, once can decide the truthfulness of each claim C_j at current time slot based on the updated value of ${\widehat{Z_j}}^k$ (i.e., $Z_j^r$). One can also compute the reliability of each source from the updated values of ${\widehat{a_i}}^{k+1},{\widehat{b_i}}^{k+1}$ (i.e., $a_i^r$ and $b_i^r$) based on Equation (10.3).

10.4.1 Simulation Study

We begin by reviewing the evaluation of the performance of the proposed recursive EM algorithm in simulation by measuring (i) the accuracy of source reliability estimation, (ii) the false positive and false negative rates (i.e., claims misclassified as true or false), and (iii) the average time the algorithm takes to process an update in different conditions.

A similar simulator as the one we discussed in Chapter 5 was built to generate a random number of sources and measured (Boolean) variables. A random probability P_i is assigned to each source S_i representing his/her reliability (i.e., the ground truth probability that they report correct observations). A “reporting rate” of a source is defined as the probability that the source reports an observation at a given time slot, reflecting the source’s willingness to report. At a given time slot, for each source S_i, the simulator decides whether or not the source reports an observation based on its reporting rate. If a measured variable is true, the S_i reports with probability P_i ×reporting rate and if it is false then S_i speaks with (1 − P_i) ×reporting rate. P_i is uniformly distributed between 0.5 and 1 in the experiments.* The fact-finder is executed as reports arrive to update estimates of source reliability and truth values of reported data. Each point on the following curves is an average of 50 experiments.

The first experiment evaluated the performance of recursive EM, the batch EM, and other baselines while varying the number of sources in the system. The total number of reported variables was set to 2000, half of which were reported correctly. The reporting rate of sources was fixed at 0.5. The number of sources was varied from 60 to 150. 100 time slots were simulated for the data stream generation. The observation updates of the last 20 slots were used to evaluate the algorithm performance. Reported results were averaged 50 experiments that differ in source reliability distributions. Results are shown in Figure 10.1. Observe that the recursive EM algorithm takes the shortest time to process an update while keeping the estimation accuracy (in terms of both source reliability estimation and claim classification) only slightly worse than the batch EM algorithm.

The second experiment compares the recursive EM to baseline algorithms when the source reporting rate changes from 0.1 to 1. Reported results are averaged over 50 experiments. The results are shown in Figure 10.2. We observe that the recursive EM algorithm continues to achieve a better trade-off between estimation accuracy and execution time: it runs fastest while offering comparable quality to the batch algorithm. Note also that both estimation accuracy and execution time of the studied algorithms improve as the source reporting rate increases. The reason is that a higher reporting rate leads to more data, which eventually allows faster convergence of the algorithm to a more accurate point.

The third and last experiment examined the effect of changing the claim mix on the performance of all algorithms. The total number of claims to was fixed at 2000 and the ratio of the number of correctly reported claims to the total number of reported variables was varied from 0.1 to 0.6. The number of sources is set to 120 and source reporting rate is fixed at 0.5. Reported results are averaged over 50 experiments. The results are shown in Figure 10.3. As before, one can observe that the recursive EM algorithm has the shortest execution time and does almost as well as the batch EM algorithm.

The simulation results show that the proposed recursive EM algorithm succeeds at offering similar estimation accuracy to its best batch counterpart while running significantly faster.

10.4.2 A Real World Case Study

In this section, we review the evaluation of the performance of the proposed recursive EM algorithm compared to the batch EM algorithm through a real world social sensing application. The application targets at finding the free parking lots on the campus of University of Illinois at Urbana-Champaign (UIUC). The “free parking lots” are defined as the parking lots that are free of charge after 5pm daily in this application. The goal here was to see if the recursive EM algorithm can track the performance of the batch EM algorithm and correctly find the real locations of free parking lot on campus. Specially, 106 parking lots on campus were selected and volunteers were asked to mark the ones they believe as “Free.” Sources marked those parking lots they have been to or are familiar with. Various types of parking lots were observed to exist on campus: enforced parking lots with time limits, parking meters, permit parking, street parking, etc. Different parking lots have different regulations for free parking. Moreover, instructions and permit signs often read similar and easy to miss. Hence, sources are prone to make mistakes in their marks. For the purpose of evaluation, the ground truth were manually collected.

In the experiment, 30 sources were invited to provide their “free parking lot” marks on the 106 parking lots (46 of which are indeed free). There were 340 marks collected from sources in total. Both the recursive and batch EM algorithms were ran on the collected marks and their performance on identifying the correct free parking lots were compared. Results are shown in Figure 10.4. Once can observe that the recursive EM algorithm is able to track the performance of the batch EM algorithm and converge to the number of free parking lots found by the batch algorithm as the amount of marks used by the algorithm increases. This result verified the nice convergence property of the developed recursive EM algorithm using real world data.

It should be emphasized that the choice of application of the reviewed work is intended to be a proxy for other more pertinent uses of the reviewed fact-finding tool that are harder to experiment with in a paper (due to absence of ground truth). For example, “free parking lots” may stand for “operational gas stations” in a post-disaster scenario (such as the New York gas crisis in the aftermath of recent hurricane Sandy).

It should also highlight that the reviewed evaluation chose an application where ground truth does not change. This is claimed to be intentional, in order to favor their competition (the batch algorithms) that operate on the entire data set at once and hence have difficulty handling dynamic changes. It is expected the advantages of the recursive algorithm to be more pronounced if ground truth did change during the experiment (e.g., a gas station runs out of gas), since it is easy to adapt them to give more weight to more recent measurements.

Finally, one should note that the reviewed work kept its data sets small enough such that running the batch algorithm upon every update remained feasible (for evaluation purposes, where each point needs 50 runs). The real advantage of the recursive scheme, however, becomes clear when the input volume is scaled up. For example, hundreds of thousands of tweets may be received in the aftermath of real disaster events. Interpreting individual tweets as claims, a recursive fact-finder can rank the claims by credibility in real-time as events unfold, which would be much less time consuming than if a batch fact-finder is re-run continuously as new tweets arrive.