Probabilistic Models for Concurrent Chatting Activity Recognition

1 Introduction

Human social organizations often have complex structures. The organization of a group defines the roles and functions of each individual, thereby ensuing the functions of the group as a whole. Ad hoc social organization may develop during a public gathering due to common interests or goals. For example, at an academic conference, attendees tend to interact with people who share similar background or research interests. As a result, conversation patterns among the attendees can be used to map out the human networks [Gips and Pentland, 2006]. Such insights can help provide important support for timely services, e.g. sending announcements to attendees with relevant interests, or tracking conversations on hot topics at the meeting.

This research aims to develop the methodology for recognition of concurrent chatting activities from multiple audio streams. The main challenge is the existence of multiple participants involved in multiple conversations. To model the dynamic interactions, we adopt a probabilistic framework to learn and recognize concurrent chatting activities.

This paper proposes using Factorial Conditional Random Fields (FCRFs) [Sutton et al., 2007] to detect and learn from patterns of multiple chatting activities. First, we survey several related projects and technologies for chatting activity recognition. Section 3 defines the FCRFs model, and section 4 introduces its learning and decoding, combined with LBP or ICA inference methods. Finally, we present our experiments to evaluate the performance of different models and inference methods, followed by the conclusions and future work.

2 Background

It is intuitively reasonable to infer activities of daily living using dynamic probabilistic models, such as Hidden Markov Models (HMMs) and complex Dynamic Bayesian Networks (DBNs) To recognize chatting activities, researchers tried to examine the Mutual Information between each person's voicing segments as a matching measure [Basu, 2002; Choudhury and Basu, 2004]. However, since multiple conversational groups usually exist concurrently in public occasions, it is very likely that the matching result does not correspond to the actual pair of conversational partners. To avoid ambiguity, model-based methods are used to monitor the chatting activities among different social groups. To capture the turn-taking behaviors of conversations, HMMs are used to describe the transition possibility of dynamic changes among group configurations [Brdiczka et al., 2005]. Factored DBNs were introduced in [Wyatt et al., 2007] to separate speakers in a multi-person environment relying on privacy-sensitive acoustic features, where the state factorization makes it relatively simple to express complex dependencies among variables.

Conditional Random Fields (CRFs) [Lafferty et al., 2001] provide a powerful probabilistic framework for labeling and segmenting structured data by relaxing the Markov independence assumption. Various extensions of CRFs have been successfully applied to learning temporal patterns of complex human behaviors [Liao et al., 2007]. Multi-Task CRFs (MCRFs), a generalization of LCRFs, are proposed to do multitasking sequence labeling for human motion recognition [Shimosaka et al., 2007]. FCRFs are adopted by [Wu et al., 2007] to recognize multiple concurrent activities from the MIT House n dataset [Intille et al., 2006]. Researchers at MIT presented Dynamic CRFs (DCRFs) combined with factored approach to capture the complex interactions between NP and POS labels in natural-language chunking task [Sutton et al., 2007]. A hierarchical CRFs model was proposed in [Liao et al., 2007] for automatic activity and location inference from the traces of GPS data.

To solve inference problems on generalized CRFs with loops, LBP algorithm is proposed based on local messages passing [Yedidia et al., 2002]. Unfortunately, the LBP algorithm is neither an exact inference algorithm nor guaranteed to converge except when the model structure is a tree [Sutton and McCallum, 2007]. In addition, its updating procedure is very time-consuming to train and decode generalized CRFs models. Other researchers from MIT presented ICA to iteratively infer the states of variables given the neighboring variables as observed information [Neville and Jensen, 2000]. ICA inference was shown empirically to help improve classification accuracy and robustness of the LBP algorithm for graph structures with high link density [Sen and Getoor, 2007].

3 Model Design

Let X be the set of observed variables representing acoustic feature values and Y be the set of hidden variables representing the chatting activity labels. In addition, let (x, y) denote the values assigned to the variables (X, Y ), N denote a given number of concurrent chatting activities, and T denote a given total time steps. Specifically, we use a 3-state variable Y t i ∈ Y whose value is yt i to represent the state of chatting activity i at time step t. We also use Yi = {Y t i }Tt=1 whose values are yi to represent the state sequence of chatting activity i over time. Similarly, we use one observed variable Xt i assigned with xti to denote single observed feature value related to Y t i . As for multiple feature values, each of them will be represented as an independent observed variable.

Let G = (V, E) be an undirected graph structure consisting of two vertex sets {(X, Y )} ≡ V . For any given time slice t and chatting activity i, we build edges (Y t i , Y t+1 i ) ∈ E to represent the possibility of activity state transition across time slices. We also build edges (Xt i , Y t i ) ∈ E to represent the possible relationships between activity labels and acoustic observations. Most importantly, edges (Y t i , Y t j ) ∈ E are built to represent the possibility of co-temporal relationships between any two concurrent chatting activities i and j. That is, all the hidden nodes within the same time slice are fully connected. Figure 1 shows a sample FCRFs model for the recognition of 3 concurrent chatting activities in a dynamic form by unrolling the structure of two time slices.

Secondly, we let C be the set of maximum cliques in G, where each clique c(i, j, t) ∈ C is composed of the vertices based on the indexes (i, j, t) and chatting activities i ̸= j. Figure 1 presents 3 sample cliques, where the local clique consists of (Xt i , Y t i ) ∈ C, the temporal clique consists of (Xt i , Y t i ,Xt+1 i , Y t+1 i ) ∈ C, and the co-temporal clique consists of (Xt i , Y t i ,Xt j , Y t j ) ∈ C. Meanwhile, several nonnegative potential functions are also defined on these cliques, which are shown as follows:

• We use φAi (xti , yt i , t) =

to denote the local potential function defined on every local clique, where f (p) i (. . .) is a function to indicate whether the state values are equal to the pth state combination within this clique, and w(p) i is its corresponding weight assigned to W (p) i . Particularly, f (p) i (. . .) = xti , if Xt i represents a numerical feature value.

• We use φBi (xti , yt i , xt+1 i , yt+1 i , t) =

to denote the temporal potential function defined on every temporal clique, where f (q) i (. . .) is a function to indicate whether the state values are equal to the qth state combination within this clique, and w(q) i is its corresponding weight assigned to W (q) i . Particularly, f (q) i (. . .) = |xt+1 i - xti |, if Xt i represents a numerical feature value.

• We use φΔij (xti , yt i , xtj , yt j , t) =

to denote the co-temporal potential function defined on every co-temporal clique, where f (r) ij (. . .) is a function to indicate whether the state values are equal to the rth state combination within this clique, and w(r) ij is its corresponding weight assigned to W (r) ij . Particularly, f (r) ij (. . .) = |xti - xtj |, if Xt i represents a numerical feature value.

Finally, we use W = {W (k) }Kk=1 whose assigning values are w = {w(k) }Kk=1 to denote the combined set for all of the model parameters {W A i ∪ W B i ∪ W Δ ij }Ni̸=j , where W A i =

{W (p) i }Pp=1 , W B i = {W (q) i }Qq=1 , W Δ ij = {W (r) ij }Rr=1 and K is the number of model parameters. In addition, we use D = {x(m) , y(m) }Mm=1 to denote the data set used for learning and decoding processes, where M is the number of data. Now we can formally define the mathematical formulation of FCRFs model as follows:

where Z(x) is the normalization constant.

4 Inference Methods

Before describing the necessary inference tasks in our FCRFs model, let us use f (k) (xc(i,j,t), yc(i,j,t), t) to denote either f (p) i (. . .), f (q) i (. . .) or f (r) ij (. . .) for simplification, where (xc(i,j,t), yc(i,j,t)) represents the assigning values of nodes in the specific clique c(i, j, t). The following sections describe the learning and decoding processes in detail and how we utilize the ICA inference method to improve the efficiency.

4.1 Learning and Decoding Processes

The purpose of the learning process is to determine the weight w(k) corresponding to each feature function f (k) . To do this, we can maximize the log-likelihood relying on the training data set D, where the log-likelihood function is shown as follows:

which is the log value of P(D|w) defined as follows:

where ∏Mm=1 P(x(m) |w) is constant and can be ignored, because we reasonably assume that P(X|W) is a uniform distribution. As a result, we can derive the partial derivative of log-likelihood with respect to w(k) from Eq. (1) and Eq. (2) as follows:

In this way, we can learn the weights w by satisfying the equation ∂L(D|w)/∂w(k) = 0. To solve such an optimization problem, we use L-BFGS method to conduct the learning process [Sutton and McCallum, 2007]. Noticeably, the marginal probability P(y(m) c(i,j,t) |x(m) ,w) in Eq. (3) can be difficult to calculate. However, we cannot use the ForwardBackward Algorithm (FBA) [Rabiner, 1989] to efficiently compute it, because such a DP method can only be used in linear-chain graph structures like HMMs and LCRFs models. Therefore, we decide to use LBP sum-product algorithm with random schedule strategy to approximate the marginal probability [Yedidia et al., 2002]. Although LBP simply conducts approximate inference, it has often been used for loopy CRFs inference [Sutton et al., 2007; Vishwanathan et al., 2006; Liao et al., 2007].

Unfortunately, as for the objective value of log-likelihood required by the L-BFGS optimization process, it is infeasible for LBP algorithm to calculate the normalization constant Z(x) in Eq. (1). Therefore, we decide to use Bethe free energy [Yedidia et al., 2005] to approximate the normalization constant. Furthermore, to avoid the over-fitting problem, what we actually do is to maximize the penalized loglikelihood L(w|D) = L(D|w) + ∑Kk=1 logP(w(k) ) by taking into consideration a zero-mean Gaussian prior distribution P (w(k) ) = exp(-(w(k) )2 /2σ2 ) with variance σ = 1.5 for each parameter W (k) . As a result, the original partial derivative in Eq. (3) becomes a new penalized form which is shown as follows:

As regards the decoding process, LBP algorithm can be also used for performing the MAP (Maximum A Priori) inference which can decode the most possible sequences of activity states [Yedidia et al., 2002]. To conduct the MAP inference, we simply propagate the max value during the message updating procedure in the original LBP sum-product algorithm. After such an LBP max-product algorithm converges and the MAP probability of each hidden variable is estimated, we can label every hidden variable by choosing the most likely value according to the MAP probability.

4.2 Decomposition

Another interpretation for the FCRFs model is to separate the factored graph structure into several linear-chain structures. That is, the original FCRFs model is considered to being composed of several LCRFs models, where each of them represents single chatting activity. To further maintain the co-temporal relationships, each hidden node Y t i depends not only on its own observed node Xt i but also on other hidden nodes Y t j as observations. As a result, the new form for each LCRFs model is expressed as follows:

where oti is a value set assigned to new observed variables Ot i = Xt i ∪ {Y t j }Ni̸=j , oi is a value set assigned to Oi = {Ot i }Tt=1 , and wi is a value set assigned to the LCRFs model parameters Wi = W A i ∪ W B i only for chatting activity i. Noticeably, {Y t j }Ni̸=j represents the neighbor nodes of Y t i in the same time slice t. In this way, the learning process for the original FCRFs structure is to train individual LCRFs models, where each LCRFs model considers other activity states as additional observations. As a result, the main inference tasks, including the calculation of marginal probability P (y(m) c(i,j,t) |o(m) i ,wi) and the normalization constant Z(o(m) i ), can be efficiently obtained through the use of FBA, such that the exact inference is still likely to be applied in FCRFs learning.

4.3 ICA Inference

Most importantly, ICA provides another inference approach in an iterative fashion for decoding process. The basic idea of ICA is to decode every target hidden variable based on the assigning labels of its neighbor variables, where the labels might be dynamically updated throughout the run of iterative process. Compared with LBP algorithm, ICA does the inference not only based on observed variables but also based on hidden variables as observations. After a given number of iterative cycles, the classification process will eventually terminate and all the hidden variables will be assigned with fixed labels.

Therefore, we can use the ICA inference method to label multiple concurrent sequences, as long as we priorly follow the decomposition procedure, letting the LCRFs model parameters Wi for every chatting activity i be learned as wi. Algorithm 1 formally provides the detailed ICA procedure for our FCRFs decoding, where an upper limit Λ = 103 for the number of iterations is set to avoid infinite repeat, followed by an ICA example with 2 concurrent chatting activities as shown in Figure 2. Noticeably, since the LCRFs model provides an efficient FBA, the ICA inference method also has an opportunity to help accelerate the decoding process.

5 Experiments

Before carrying out the experiments, we asked every participant to wear an audio recorder around his or her neck to collect the audio data. During a given period of time, the participants can randomly determine their conversational partners

Algorithm 1 Iterative Classification Algorithm (Λ)

• 1: repeat
• 2: {Decode new labels}
• 3: for all Yi ⊆ Y do
• 4: Store yi ← arg maxyi P (yi|oi, wi)
• 5: end for
• 6: {Update new labels}
• 7: for all Yi ⊆ Y do
• 8: Assign yi to Yi as new labels
• 9: end for
• 10: until yi = yi, for all Yi ⊆ Y

and the audio recorders can record their conversations. As a result, the collected audio recordings can be used for the annotation of participants' conversational states as well as the extraction of acoustic feature values. To do annotation, researchers should listen very carefully to the audio recordings to know who has spoken with whom, relying on the content of what was said.

To evaluate the performance, we used the cross-validation method to test the experimental data. However, to deal with sequential data, this method suffers from the problem that the important activities to be recognized may only occur in specific time periods, such that the possible patterns in the testing data cannot be learned in the training data, or the learned results in training data cannot help recognize the testing data. To address the problem, the sequential data should be fragmented into several small segments and each of the adjacent segments along the temporal axis will be systematically reassigned to each fold. In practice, we define the time duration between two consecutive time steps as 1 second and each segment contains 10 time slices (T = 10).

Finally, we measure the recognition accuracy as the percentage of correctly predicted conversations by applying the 10-fold cross-validation to compare the performance of the various types of models and inference methods. More specifically, the comparisons for recognition accuracy include accuracy, recall, precision and F-score. In addition, to analyze the efficiency of FCRFs learning and decoding by using different inference methods, including LBP and ICA inferences, we measure the learning time as the accumulated training time during the process of cross-validation on an Xeon 5130 2.0G PC, and measure the decoding time as the accumulated decoding time in a similar way. The following sections present several experiments to verify the advantages of our FCRFs models with ICA inference method.

5.1 FCRFs Models vs. PCRFs Models

In this experiment, the primary purpose is to analyze the recognition accuracy of two different FCRFs models by using LBP and ICA inference methods respectively. In addition, another Parallel CRFs (PCRFs) model is also trained for comparison, which is composed of several LCRFs models parallelly and no co-temporal connections between hidden nodes are built. That is, the co-temporal relationships among chatting activities in FCRFs model are eliminated. As a result, we calculate the accuracy, recall, precision and F-score for each chatting activity and then average them respectively. We've designed 2 common scenarios to collect auditory data for experiments, which are shown as follows:

1. Meeting activity The data is a set of 80-minute audio streams recorded by 3 participants who are sitting in fixed seats and holding discussion on a project. During the period, they can switch their conversational partners and no others would interrupt their meeting. Noticeably, the audio recorders simply record the voices from the participants rather than other non-human noises, so we choose the volume features as our primary observations. Although most of the time only one person is speaking, the lack of voice recognition makes it relatively difficult to disambiguate the speakers. The recognition accuracy is summarized in Table 1.
2. Public occasion The data is a set of 45-minute audio streams recorded by 3 participants who can walk around and chat with others in a real-world laboratory. Noticeably, not only these participants who wear audio recorders are involved in our experimental environment, but also other occupants who do not wear audio recorders are allowed to exist. In this way, all of them can randomly chat with each other or choose to do their personal activities, thereby creating a naturalistic scenario varies in background noise. Therefore, in addition to the feature values of volume and MI, we consider extra features used for human voice detection. The recognition accuracy is summarized in Table 2.

In both the above scenarios, we can observe a consistent phenomenon that all the FCRFs models significantly outperform the PCRFs model in the comparison of F-score. This result provides us the conclusion that it is helpful to utilize the co-temporal relationship for chatting activity recognition. However, the FCRFs model with LBP inference performs even more badly than the PCRFs model in the comparison of precision, while the FCRFs model with ICA inference still performs the best.

5.2 CRF-like Models vs. HMM-like Models

In this experiment, two DBN models, Parallel HMMs (PHMMs) [Vogler and Metaxas, 2001] and Coupled HMMs (CHMMs) [Brand et al., 1997], are trained for comparison. PHMMs model is very similar to the PCRFs model, where all of the multiple chatting activities are independent temporal processes and each of them is modeled as a linear-chain HMMs. Furthermore, the CHMM model assumes that each hidden variable is conditionally dependent on all hidden variables in the previous time slice. Therefore, the CHMMmodel also has the ability to capture the interactive relationships among chatting activities, which can be compared with the FCRFs model. By analyzing the audio data collected in the public occasion, the recognition accuracy of HMM-like models is summarized in Table 3.

Taken as a whole, we can discover that all the CRF-like models significantly outperform the HMM-like models in all the comparisons of recognition accuracy, which concludes that the CRF-like models indeed have the ability to accommodate overlapping features and are much more powerful to capture complex co-temporal relationships among multiple chatting activities.

5.3 LBP Efficiency vs. ICA Efficiency

The efficiency analysis based on the audio data collected in the public occasion is summarized in Table 4, which compares the learning time and decoding time by using the various types of CRFs models as well as inference methods.

In this experiment, we can come to an important conclusion that the FCRFs model with ICA inference takes much less time than LBP method to complete the learning and decoding processes. Especially in the comparison of learning time, we can observe that there is even no significant difference between the PCRFs model and the FCRFs model with ICA inference. Given the difference in convergence property of LBP and ICA in various conversation contexts, we chose to compare them when effective convergence is reached - just to be fair. Additional experiments may indeed offer potentially interesting observations by stopping LBP early at increasing rounds of message passing.

6 Conclusion and FutureWork

This paper proposes the FCRFs model for joint recognition of multiple concurrent chatting activities by using the ICA inference method. We designed the experiments based on the collected auditory data to compare our FCRFs model with other dynamic probabilistic models, including PCRFs model and HMMs-like models. The initial experiment showed that the FCRFs model with ICA inference method, which is capable of accommodating the co-temporal relationships, can help improve the recognition accuracy in the presence of coexisting conversations. Most importantly, the FCRFs model using ICA inference approach significantly takes much less time to conduct the learning and decoding processes than the LBP inference method. FCRF with ICA can be generalized to recognize more general conversations or activities among a larger group of participants with properly designed FCRF graph structure capturing co-temporal relationships.

Acknowledgements

This research was supported by grants from the National Science Council NSC 96-2628-E-002-173-MY3, Ministry of Education in Taiwan 97R0062-06, and Intel Corporation.