9.2.1 Deriving the Likelihood

When source constraints are considered in the likelihood function, it is assumed that sources only claim variables they observe, and hence the probability of a source claiming a variable he/she does not have an opportunity to observe is 0. For simplicity, it is assumed that all variables are independent, then this assumption is relaxed later in Section 9.3. Under these assumptions, the new likelihood function L(θ;X,Z) that incorporates the source constraints is given by:

$\begin{array}{ll}\hfill L(\theta ;X,Z)=p(X,Z|\theta )& =\prod _{j=1}^{N}p(z_j)\times p(X_j|z_j,\theta )\hfill \\ \hfill & =\prod _{j=1}^N\prod _{i\in {\mathcal{S}}_j}p(z_j)\times p(S_i{C}_j|z_j,S_i\text{observes}{C}_j)\hfill \end{array}$

where ${\mathcal{S}}_j$: Set of sources observed C_j

$\begin{array}{ll}\hfill p(z_j)& =\left\{\begin{array}{ll}{f}_j& z_j=1\\ (1-f_j)& z_j=0\\ \end{array}\right.\hfill \\ \hfill p(S_i{C}_j|z_j,S_i\text{observes}{C}_j)& =\left\{\begin{array}{ll}{a}_i& z_j=1,S_i{C}_j=1\\ (1-a_i)& z_j=1,S_i{C}_j=0\\ b_i& z_j=0,S_i{C}_j=1\\ (1-b_i)& z_j=0,S_i{C}_j=0\\ \end{array}\right.\hfill \end{array}$

Note that, in the likelihood function, the probability contribution from sources who actually observe a variable (e.g., $i\in {\mathcal{S}}_j$ for C_j) is considered. This is an important change from the reviewed maximum likelihood estimation (MLE) model in Chapter 5. This change allows the new model to nicely incorporate the source constraints (name, source opportunity to observe) into the MLE framework.

Using the above likelihood function, the corresponding E-step and M-step of OtO EM scheme can be derived. The detailed derivations are shown in Appendix of Chapter 9.

9.2.2 The OtO EM Algorithm

In summary, the inputs to the OtO EM algorithm are (i) the claim matrix SC from social sensing data and (ii) the knowledge matrix SK describing the source constraints. The output is the MLE of source reliability and the probability of claim correctness. Compared to the regular EM algorithm from Chapter 5, source constraints are provided as a new input into the framework and imposed them on the E-step and M-step. The algorithm begins by initializing the parameter θ with random values between 0 and 1. The algorithm then performs the new derived E-steps and M-steps iteratively until θ converges. Since each observed variable is binary, variables can be classified as either true or false based on the converged value of Z(t,j). Specifically, C_j is considered true if $Z_j^c$ goes beyond some threshold (e.g., 0.5) and false otherwise. The estimated t_i of each source can also be computed from the converged values of θ^(t) (i.e., $a_i^c$, $b_i^c$, and $d_i^c$) based on Equation (9.3). Algorithm 5 provides the pseudocode of OtO EM.

9.3.1 Deriving the Likelihood

In order to derive a likelihood function that considers constraints in the form of dependencies between observed variables, N observed variables in the social sensing model are divided into G independent groups, where each independent group contains variables that are related by some local constraints (e.g., gas price of stations in the same neighborhood could be highly correlated). Consider group g, where there are k dependent variables g₁,…,g_k. Let $p(z_{g_1},\dots ,z_{g_k})$ represent the joint probability distribution of the k variables and let ${\mathcal{Y}}_g$ represent all possible combinations of values of g₁,…,g_k. For example, when there are only two variables, ${\mathcal{Y}}_g=[(1,1),(1,0),(0,1),(0,0)]$. Note that, it is assumed that $p(z_{g_1},\dots ,z_{g_k})$ is known or can be estimated from prior knowledge. The new likelihood function L(θ;X,Z) that considers the aforementioned constraints is:

$\begin{array}{ll}\hfill L(\theta ;X,Z)& =\prod _{g\in G}p(X_g,Z_g|\theta )=\prod _{g\in G}p(Z_g)\times p(X_g|Z_g,\theta )\hfill \\ \hfill & =\prod _{g\in G}\left\{\sum _{g_1,\dots ,g_k\in {\mathcal{Y}}_g}p(z_{g_1},\dots ,z_{g_k})\prod _{i\in M}\prod _{j\in c_g}p(S_i{C}_j|z_j)\right\}\hfill \end{array}$

where α_i,j is the same as defined in Equation (9.7) and c_g represents the set of variables belonging to the independent group g. Compared to the regular EM from Chapter 5, the new likelihood function is formulated with independent groups as units (instead of single independent variables). The joint probability distribution of all dependent variables within a group is used to replace the distribution of a single variable. This likelihood function is therefore more general, but reduces to the previous form in the special case where each group is composed of only one variable.

Using the above likelihood function, the corresponding E-step and M-step of DV EM and OtO+DV EM schemes can be derived. The detailed derivations are shown in Appendix of Chapter 9.

9.3.2 The OtO+DV Algorithm

In summary, the OtO+DV EM scheme incorporates constraints on both sources and observed variables. The inputs to the algorithm are (i) the claim matrix SC, (ii) the knowledge matrix SK, and (iii) the joint distribution for each group of dependent variables, collectively represented by set JD. The output is the MLE of source reliability and claim correctness. The OtO+DV EM pseudocode is shown in Algorithm 6.

9.4.1 Opportunity to Observe

In this subsection, we first evaluate the performance of the OtO EM scheme. For the OtO EM scheme, the recorded GPS traces of each vehicle were used to determine whether it actually went to a specific location or not (i.e., decide whether a source has an opportunity to observe a given variable or not). There are 54 actual traffic lights and 190 stop signs covered by the data traces collected.

Figure 9.1 compares the source reliability estimated by both the OtO EM and regular EM schemes to the actual source reliability computed from ground truth. The source IDs are sorted by the ground truth reliability. We observed that the OtO EM scheme stays closer to the actual results for most of the sources (i.e., OtO EM estimation error is smaller than regular EM for about 74% of sources).

Next, we review the accuracy of identifying traffic lights by the new scheme. It may be tempting to confuse the problem with one of classification and plot ROC curves or confusion matrices. This would not be appropriate, however, because the output of the algorithm is not a classification label, but rather a probability that the labeled entity (e.g., a traffic light) exists at a given location. Some locations are associated with a higher probability than others. Hence, what is needed is an estimate of how well the computed probabilities match ground truth.

Accordingly, Figures 9.2 and 9.3 show the accuracy of identifying traffic lights by the OtO EM scheme (Figure 9.2) and the regular EM scheme (Figure 9.3). The horizontal axis shows location IDs where lights were indicated by the respective schemes, sorted by their probability (as computed from the corresponding EM variant) from high to low. Hence, one should expect that lower-numbered locations be true positives, whereas high-numbered locations may contain increasingly more false positives as the scheme assigns a lower probability that those contain traffic lights.

Figure 9.2(a) shows the actual status of each location. A green (light gray in print versions) bar is a true positive, whereas a red (dark gray in print versions) one is a false positive. As expected, we observe that most of the traffic light locations identified by the OtO EM scheme are true positives. False positives occur only later on at higher-numbered (i.e., lower probability) locations. Additionally, it is interesting to compare the probability of finding traffic lights at the indicated locations, as computed by the algorithms, to the probability computed empirically for the same locations by counting how many of them have actual lights. Figure 9.2(b) shows this comparison. Specifically, it compares the average probability to the empirical probability, computed for the first n locations to have traffic lights, where n is the location index on the horizontal axis. We observe that the estimation results of OtO EM follow quite well the empirical ones.

Similarly, results for the regular EM scheme are reported in Figure 9.3. We observe that the OtO EM scheme is able to find five more traffic light locations compared to the regular EM scheme. We also note that the red curve (dark gray in print versions) in Figure 9.2(b) is larger than that of Figure 9.3(b) for the same location ID, which indicates a better match of the estimated credibility of the claim. The detailed comparison results between two schemes are given in Table 9.1.

The above experiments were repeated for stop sign identification, and it is observed that the OtO EM scheme achieves a more significant performance gain in both participant reliability estimation and stop sign classification accuracy compared to the regular EM scheme. The reason is: stop signs are scattered in town and the odds that a vehicle’s path covers most of the stop signs are usually small. Hence, having the knowledge of whether a source had an opportunity to observe a variable is very helpful. However, the identification of stop signs in general is found to be more challenging than that of traffic lights. There are several reasons for that. Namely, (i) the claims for stop signs are sparser because stops signs are typically located on smaller streets, so the chances of different cars visiting the same stop sign are lower than that for traffic lights, (ii) cars often stop briefly at non-stop sign locations, which the reviewed scheme mis-interpret for stop signs, and (iii) when cars want to make a turn after the stop sign, cars’ bearings are often not well aligned with the directions of stop signs, which causes errors since stop-sign claims are bearing-sensitive.

Figure 9.4 compares source reliability computed by the OtO EM and regular EM schemes. The actual reliability is computed from similar experiments as traffic lights. We observe that source reliability is better estimated by the OtO EM scheme compared to the regular EM scheme.

Figures 9.5 and 9.6 show the true positives and false positives in recognizing stop signs. We observe the OtO EM scheme actually finds twelve more correct stop sign locations and reduces one false positive location compared to the regular EM scheme. The detailed comparison results are given in Table 9.2. Additionally, we observe that, for both EM schemes, the actual probability of finding stop signs at the indicated locations stays close to but slightly less than the estimated probability by the reviewed algorithms. The reasons of such deviation can be explained by the aforementioned short wait behaviors at non-stop sign locations in real world scenarios.

9.4.2 Dependent Variables

In this subsection, we evaluate the extensions that consider dependency constraints (DV EM), and the comprehensive OtO+DV EM scheme. While the earlier discussion treated stop signs as independent variables, this is not strictly so. The existence of stop signs in different directions (bearings) is in fact quite correlated. The correlations for Urbana-Champaign were empirically computed and assumed to be known in advance. Clearly, the more “high-order” correlations are considered, the more information is given to improve performance of algorithm. To assess the effect of “minimal” information (which would be a “worst-case” improvement for the reviewed scheme), only pairwise correlations were used. Hence, the joint distribution of co-existence of (two) stop signs in opposite directions at an intersection was computed. It is presented in Table 9.3, and was used as input to the DV EM scheme.

Figure 9.7 shows the accuracy of source reliability estimation, when these constraints are used. We observe that both DV EM and DV+OtO EM scheme track the source reliability very well (the estimation error of the two EM schemes improved 9.4% and 13.4%, respectively, compared to the regular EM scheme).

The true positives and false positives for stop signs are shown in Figures 9.8 and 9.9. Observe that the DV EM scheme finds 14 more correct stop sign locations. The DV+OtO EM scheme performed the best, it finds the most stop sign locations (i.e., 19 more than regular EM, 5 more than DV EM) while keeping the false positives the least (i.e., the same as regular EM and 4 less than DV EM). The detailed comparison results are given in Table 9.2.

Additionally, we observe that, for the DV+OtO EM scheme, the estimated probability of finding stop signs is much closer to the empirically computed probability, compared to other EM schemes we discussed. Also, the red curve (dark gray in print versions) is higher for the DV+OtO EM than the DV EM. This is because the new model explicitly considered both dependency constraints and the “opportunity to observe” for sources in the DV+OtO EM scheme.

After the formulation of the new likelihood function to account for the source constraints, the likelihood function can be plugged into the Q function defined in Equation (5.8) of EM. The E-step can be derived as follows:

$\begin{array}{ll}\hfill Q(\theta |{\theta }^{(t)})& =E_{Z|X,{\theta }^{(t)}}[logL(\theta ;X,Z)]\hfill \\ \hfill & =\sum _{j=1}^N\left\{p(z_j=1|X_j,{\theta }^{(t)})\times \sum _{i\in {\mathcal{S}}_j}(log({(a_i)}^{S_i{C}_j}{(1-a_i)}^{(1-S_i{C}_j)})+log{f}_j)\right.\hfill \\ \hfill & \left.+p(z_j=0|X_j,{\theta }^{(t)})\times \sum _{i\in {\mathcal{S}}_j}(log({(b_i)}^{S_i{C}_j}{(1-b_i)}^{(1-S_i{C}_j)})+log(1-f_j))\right\}\hfill \end{array}$

where p(z_j = 1|X_j,θ^(t)) represents the conditional probability of the variable C_j to be true given the claim matrix related to the jth claim and current estimate of θ. p(z_j = 1|X_j,θ^(t)) is represented by Z(t,j) since it is only a function of t and j. Z(t,j) can be further computed as:

$\begin{array}{ll}\hfill Z(t,j)& =p(z_j=1|X_j,{\theta }^{(t)})\hfill \\ \hfill & =\frac{p(z_j=1;X_j,{\theta }^{(t)})}{p(X_j,{\theta }^{(t)})}\hfill \\ \hfill & =\frac{p(X_j,{\theta }^{(t)}|z_j=1)p(z_j=1)}{p(X_j,{\theta }^{(t)}|z_j=1)p(z_j=1)+p(X_j,{\theta }^{(t)}|z_j=0)p(z_j=0)}\hfill \\ \hfill & =\frac{\prod _{i\in {\mathcal{S}}_j}{(a_i)}^{S_i{C}_j}{(1-a_i)}^{(1-S_i{C}_j)}\times f_j^{(t)}}{\prod _{i\in {\mathcal{S}}_j}{(a_i)}^{S_i{C}_j}{(1-a_i)}^{(1-S_i{C}_j)}\times f_j^{(t)}+\prod _{i\in {\mathcal{S}}_j}{(b_i)}^{S_i{C}_j}{(1-b_i)}^{(1-S_i{C}_j)}\times (1-f_j^{(t)})}\hfill \end{array}$

Note that, in the E-step, only sources who observe a given variable are considered while computing the likelihood of reports regarding that variable.

In the M-step, the derivatives are set to 0: $\frac{\partial Q}{\partial a_i}=0$, $\frac{\partial Q}{\partial b_i}=0$, and $\frac{\partial Q}{\partial f_j}=0$. This gives us the θ* (i.e., $a_1^{*},a_2^{*},\dots ,a_M^{*}$;$b_1^{*},b_2^{*},\dots ,b_M^{*}$;$f_1^{*},f_2^{*},\dots ,f_M^{*}$) that maximizes the Q(θ|θ^(t)) function in each iteration and is used as the θ^(t+1) of the next iteration.

$\begin{array}{ll}\hfill a_i^{(t+1)}& =a_i^{*}=\frac{\sum _{j\in S{J}_i}Z(t,j)}{\sum _{j\in {\mathcal{C}}_i}Z(t,j)}\hfill \\ \hfill b_i^{(t+1)}& =b_i^{*}=\frac{\sum _{j\in S{J}_i}(1-Z(t,j))}{\sum _{j\in {\mathcal{C}}_i}(1-Z(t,j))}\hfill \\ \hfill f_j^{t+1}& =f_j^{*}=Z(t,j)\hfill \\ \hfill f_i^{t+1}& =f_i^{*}=\frac{\sum _{j\in {\mathcal{C}}_i}Z(t,j)}{|{\mathcal{C}}_i|}\hfill \end{array}$

where ${\mathcal{C}}_i$ is set of variables source S_i observes according to the knowledge matrix SK and Z(t,j) is defined in Equation (9.10). SJ_i is the set of variables the source S_i actually claims in the claim matrix SC. We note that, in the computation of a_i and b_i, the silence of source S_i regarding some variable C_j is interpreted differently depending on whether S_iobserved it or not. This reflects that the opportunity to observe has been incorporated into the M-step when the estimation parameters of sources are computed. The resulting OtO EM algorithm is summarized in the subsection below.

Derivation of E-Step and M-Step of DV and OtO+DV EM

Given the new likelihood function of the DV EM scheme defined in Equation (9.8), the E-step becomes:

$\begin{array}{ll}\hfill Q(\theta |{\theta }^{(t)})& =E_{Z|X,{\theta }^{(t)}}[logL(\theta ;X,Z)]\hfill \\ \hfill & =\sum _{g\in G}p(z_{g_1},\dots ,z_{g_k}|X_g,{\theta }^{(t)})\hfill \\ \hfill & \times \left\{\sum _{i\in M}\sum _{j\in c_g}logp(S_i{C}_j|z_j)+logp(z_{g_1},\dots ,z_{g_k})\right\}\hfill \end{array}$

where $p(z_{g_1},\dots ,z_{g_k}|X_g,{\theta }^{(t)})$ represents the conditional joint probability of all variables in independent group g (i.e., g₁,…,g_k) given the observed data regarding these variables and the current estimation of the parameters. $p(z_{g_1},\dots ,z_{g_k}|X_g,{\theta }^{(t)})$ can be further computed as follows:

$\begin{array}{ll}\hfill p(z_{g_1},\dots ,z_{g_k}|X_g,{\theta }^{(t)})& =\frac{p(z_{g_1},\dots ,z_{g_k};X_g,{\theta }^{(t)})}{p(X_g,{\theta }^{(t)})}\hfill \\ \hfill & =\frac{p(X_g,{\theta }^{(t)}|z_{g_1},\dots ,z_{g_k})p(z_{g_1},\dots ,z_{g_k})}{\sum _{g_1,\dots ,g_k\in {\mathcal{Y}}_g}p(X_g,{\theta }^{(t)}|z_{g_1},\dots ,z_{g_k})p(z_{g_1},\dots ,z_{g_k})}\hfill \\ \hfill & =\frac{\prod _{i\in M}\prod _{j\in c_g}p(S_i{C}_j|z_j)p(z_{g_1},\dots ,z_{g_k})}{\sum _{g_1,\dots ,g_k\in {\mathcal{Y}}_g}\prod _{i\in M}\prod _{j\in c_g}p(S_i{C}_j|z_j)p(z_{g_1},\dots ,z_{g_k})}\hfill \end{array}$

We note that p(z_j = 1|X_j,θ^(t)) (i.e., Z(t,j)), defined as the probability that C_j is true given the observed data and the current estimation parameters, can be computed as the marginal distribution of the joint probability of all variables in the independent claim group g that variable C_j belongs to (i.e., $p(z_{g_1},\dots ,z_{g_k}|X_g,{\theta }^{(t)})j\in c_g$). We also note that, for the worst case where N variables fall into one independent group, the computational load to compute this marginal grows exponentially with respect to N. However, as long as the constraints on observed variables are localized, the reviewed approach stays scalable, independently of the total number of estimated variables.

In the M-step, as before, θ* is chosen to maximize the Q(θ|θ^(t)) function in each iteration to be the θ^(t+1) of the next iteration. Hence:

$\begin{array}{ll}\hfill a_i^{(t+1)}& =a_i^{*}=\frac{\sum _{j\in S{J}_i}Z(t,j)}{\sum _{j=1}^{N}Z(t,j)}\hfill \\ \hfill b_i^{(t+1)}& =b_i^{*}=\frac{\sum _{j\in S{J}_i}(1-Z(t,j))}{\sum _{j=1}^N(1-Z(t,j))}\hfill \\ \hfill f_j^{t+1}& =f_j^{*}=Z(t,j)\hfill \end{array}$

where Z(t,j) = p(z_j = 1|X_j,θ^(t)). We note that for the estimation parameters, a_i and b_i, the same expression as for the case of independent variables is obtained. The reason is that sources report variables independently of the form of constraints between these variables.

Next, the two EM extensions (i.e., OtO EM and DV EM) derived so far are combined to obtain a comprehensive EM scheme (OtO+DV EM) that considers constraints on both sources and observed variables. The corresponding E-step and M-step are shown below:

$\begin{array}{ll}\hfill p(z_{g_1},\dots ,z_{g_k}|X_g,{\theta }^{(t)})& =\frac{p(z_{g_1},\dots ,z_{g_k};X_g,{\theta }^{(t)})}{p(X_g,{\theta }^{(t)})}\hfill \\ \hfill & =\frac{p(X_g,{\theta }^{(t)}|z_{g_1},\dots ,z_{g_k})p(z_{g_1},\dots ,z_{g_k})}{\sum _{g_1,\dots ,g_k\in {\mathcal{Y}}_g}p(X_g,{\theta }^{(t)}|z_{g_1},\dots ,z_{g_k})p(z_{g_1},\dots ,z_{g_k})}\hfill \\ \hfill & =\frac{\prod _{i\in {\mathcal{S}}_j}\prod _{j\in c_g}p(S_i{C}_j|z_j,S_i\text{observes}{C}_j)\times p(z_{g_1},\dots ,z_{g_k})}{\sum _{g_1,\dots ,g_k\in {\mathcal{Y}}_g}\prod _{i\in {\mathcal{S}}_j}\prod _{j\in c_g}p(S_i{C}_j|z_j,S_i\text{observes}{C}_j)\times p(z_{g_1},\dots ,z_{g_k})}\hfill \end{array}$

where ${\mathcal{S}}_j$: Set of sources observes C_j

$\begin{array}{ll}\hfill a_i^{(t+1)}& =a_i^{*}=\frac{\sum _{j\in S{J}_i}Z(t,j)}{\sum _{j\in {\mathcal{C}}_i}Z(t,j)}\hfill \\ \hfill b_i^{(t+1)}& =b_i^{*}=\frac{\sum _{j\in S{J}_i}(1-Z(t,j))}{\sum _{j\in {\mathcal{C}}_i}1-Z(t,j))}\hfill \\ \hfill f_j^{t+1}& =f_j^{*}=Z(t,j)\hfill \\ \hfill f_i^{t+1}& =f_i^{*}=\frac{\sum _{j\in {\mathcal{C}}_i}Z(t,j)}{|{\mathcal{C}}_i|}\hfill \end{array}$

where ${\mathcal{C}}_i$ is set of variables source S_i observes.