Building relational models for the structured output classication problem of sequence labeling has been recently explored in a few research works. The models built in such a manner are interpretable and capture much more information about the domain (than models built directly from basic attributes), resulting in accurate predictions. On the other hand, discovering optimal relational features is a hard task, since the space of relational features is exponentially large. An exhaustive search in this exponentially large feature space is infeasible. Therefore, often the feature space is explored using heuristics. Recently, we proposed a Hierarchical Kernels-based feature learning approach (StructHKL) for sequence labeling [?], that optimally learns emission features in the form of conjunctions of basic inputs at a sequence position. However, StructHKL cannot be trivially applied to learn complex relational features derived from relative sequence positions. In this paper, we seek to learn optimal relational sequence labeling models by leveraging a relational kernel that computes the similarity between instances in an implicit space of relational features. To this end, we employ relational subsequence kernels at each sequence position (over a time window of observations around the pivot position) for the classi cation model. While this method of modeling does not result in interpretability, relational subsequence kernels do e ciently capture relational sequential information on the inputs. We present experimental comparison between approaches for explicit learning and implicit modeling of relational features and explain the trade-o s therein.
Structured output classi cation has gathered signi cant interest in the machine learning community during the last decade [?,?,?,?].The goal of such works is to classify complex output structures such as sequences, trees, lattices or graphs, in which the class label at each node/position of the structure has to be inferred based on observed evidence data. The possible space of structured outputs tends to be exponential and thus structured output classi cation is a challenging research area. We, in our research work, focus on a speci c structured output classi cation problem, popularly known as sequence labeling. As in any classi cation setting, the sequence labeling domain is also characterized by complex relationships among entities and uncertainties in their relationships. E cient models can be constructed by exploiting these relationships. However, discovering relationships that enhance the discriminative power of classi ers is a hard task, since the relationship space is often too large. Therefore, most of the research in sequence labeling and other structured output space classi cation, either ignore the complex relationships or use heuristics to learn the relationships. In this work, we focus on exploiting complex relationships in both the input as well as the output space in an e cient way to improve sequence labeling models. We begin with a brief introduction to the task of sequence labeling.
The objective in sequence labeling is to assign a state (class label) to every instance of a sequence of observations. Typical sequence labeling algorithms learn probabilistic information about the neighboring states along with the probabilistic information about the observations. Hidden Markov Models (HMM) [?], Conditional Random Fields (CRF) [?] and StructSVM [?] are three models used popularly for sequence labeling problems. The training objective can be posed as learning feature weights that make the score F (F : X Y ! R), of the true output sequence Y greater than any other possible output sequence, given an input sequence X. The score is de ned as:
F (X; Y ; f ) = hf ; (X; Y )i
(
F (X; f ) = arg max F (X; Y ; f )
Y 2Y
(
Recent works have shown that learning the relational structure between input features improves the e ciency of sequence labeling models [?,?,?]. However, the space of relational features is exponential in the number of basic observations, making the discovery of useful features a di cult task. For instance, the simple case of learning features that are conjunctions of basic observations at any single sequence position results in a feature space that is exponential. The problem is further exacerbated if we consider complex relational features built from observations at di erent relative positions. An exhaustive search in this exponentially large feature space is infeasible. Therefore, most systems that learn relational features follow a greedy search strategy based on heuristics to select useful features. These approaches start with an initial (possibly empty) set of features and iteratively search (using some ordering of the feature space) for re nements that improve the heuristic score.
In our previous work [?], we propose and develop a Hierarchical Kernels based approach for optimally learning features which are conjunctions of basic features at a particular sequence position (simple conjuncts or SCs) for each label. The approach is referred to as Hierarchical Kernel Learning for Structured Output Spaces (StructHKL) 4. Although it optimally learns the most discriminative SCs, its applicability in learning complex relational features that are derived from observations at di erent relative positions in a sequence, is nontrivial and challenging. To address this issue, our follow-up work [?], determines simple feature classes that can be composed to yield complex ones, with the goal of formulating e cient yet e ective relational feature learning procedures. We identify feature classes called absolute features (AF ) and composite features (CF ) in increasing order of their complexity respectively 5. It is posited that optimal relational features can be learned by enumerating AF s and discovering their useful compositions (CF ) using StructHKL. However, the space of AF s is prohibitively large and it is not feasible to enumerate all of them in a domain. To circumvent this issue, we propose to selectively enumerate AF s based on some relevance criteria such as the support of AF s in the training set.
An AF is formed by combining one or more predicates which share variables. The partial ordering of AF s does not comply with the requirement of StructHKL that the descendant kernels should be summable in polynomial time. This limits the possibility of leveraging StructHKL to optimally learn features in the space of AF s (and its super-space of CF s). For this reason, in the current piece of work, we leverage a relational kernel that computes the similarity between instances in an implicit feature space of CF s. To this end, we employ the relational subsequence kernel [?] at each sequence/pivot position (over a time window of observations around it) for the classi cation model. We would like to learn composite features which capture relational information about basic observations at positions relative to the pivot position for every sequence step. This sequence information would provide a rich feature space for the algorithm to learn a more expressive model. However, explicitly enumerating such a feature space is not feasible due to the high dimensionality of the feature space. Relational subsequence kernels implicitly capture the e ectiveness of this rich feature space. We also show that the feature space of CF s (explicit features) are captured by the relational subsequence kernels (implicit features). While this way of modeling does not result in interpretability, relational subsequence kernels do e ciently capture the relational sequential information on the inputs.
We evaluate the performance of our approaches on publicly available activity recognition datasets. Our experiments show improvements over other standard and state-of-the-art sequence labeling techniques. The paper is organized as follows.
Section 2 discusses background work. We discuss our approach in Section 3. Experimental setup and results are discussed in Section 4 and we conclude the paper in Section 5. 4 StructHKL is derived from StructSVM in which we use sparsity inducing hierarchical regulariser for observation features. 5 For the de nitions and examples of AF , CF and other feature classes, please refer to [?].
Approaches to learning relationships for sequence labeling could be based on basic input features at a single sequence step or input features at multiple sequence steps and/or relationships among output variables. Some of these approaches are discussed below.
McCallum [?] as well as Nair et. al [?] propose feature induction methods that iteratively construct feature conjunctions that increase an objective. These approaches start with an initial set of features (conjunctions or atomic) and at each step, consider a set of candidate features that are re nements of the current set of features. Features whose inclusion will lead to maximum increase in the objective are selected. Weights for the new features are trained. The steps are iterated until convergence. While McCallum trains a CRF model and uses conditional log-likelihood as the objective for the greedy induction, Nair et. al train an HMM and use prediction accuracy on a held out dataset (part of the training data) as the objective. This e ectively solves the problem of incorrect assumption, that individual observations are independent, while not dealing with exponential observation space. Although these greedy feature induction approaches have been shown to improve performance, they cannot guarantee an optimal solution. An exhaustive search to nd the optimal solution is expensive due to the exponential size of the search space.
Kersting et. al. [?] discusses the Logical Hidden Markov Model which is a relational representation of HMM. However, this work does not investigate learning the input structure. Thon et. al ([?], [?]) elaborate on relational markov processes which are concerned with e cient parameter learning and inference. They assume that a structure has been provided upfront. Similarly, a relational bayesian network learning is discussed in [?] with the goal of learning the parameters given the structure of the bayes-net.
Hierarchical Kernel Learning for Structured Output Spaces (StructHKL) [?], optimally and e ciently learns discriminative features for multi-class structured output classi cation problems such as sequence labeling. StructHKL builds on the Support Vector Machines for Structured Output Spaces (StructSVM) model [?] for sequence prediction problems, wherein, all possible SCs form the input features while the transition features are constructed from all possible transitions between state labels. A -norm hierarchical regularizer is employed to select a sparse set of SCs. Since there is a need to preserve all possible transitions, a conventional 2-norm regularizer is employed for state transition features. The exponentially large observation feature space is searched using an active set algorithm and the exponentially large set of constraints is handled using a cutting plane algorithm.
In our follow-up work [?], we learn complex relational features derived from relative sequence positions. We propose to enumerate AF s and leverage StructHKL to learn their compositions, which are CF s. However, it is noted that the space of AF s is prohibitively large and therefore it is not feasible to enumerate all AF s in a domain. As a solution we selectively enumerate AF s based on some relevance criteria such as support of the AF in the training set. A feature is considered to be strongly relevant if it helps the classi cation model to discern classes optimally. On the other hand, a feature is weakly relevant if it covers atleast a threshold percentage of examples. As discovering strongly relevant AF s is a hard task, the focus is on discovering weakly relevant AF s using Inductive Logic Programming tools. Pattern mining approaches are employed to discover a relevant set of AF s. Speci cally, a relational pattern miner called Warmr [?] is used. Warmr uses a modi ed version of Apriori algorithm [?] to nd frequent patterns (AF s) which have minimum support, as speci ed by the user. Once a set of relevant AF s are enumerated, StructHKL is used to learn useful compositions of AF s and their parameters to get the nal model. This can be viewed as projecting the space of complex relational features such as CF s into the space of SCs and leveraging StructHKL.
TildeCRF [?] has an objective similar to our approach, where the relational structure and parameters of a CRF for sequence labeling are learned. TildeCRF uses relational regression trees and gradient tree boosting for learning the structure and parameters. Unlike in TildeCRF, in this work, we derive convex formulations for learning relational models.
In this paper, we provide operative de nitions of the feature classes such as AF and CF . For a more detailed exposition of the feature classes and the relationships between them, the reader is pointed to our previous work [?]. 3
Implicit Modeling of Features for Sequence Labeling In Section 1, we have stated our objective as exploiting complex relationships among input variables in sequence labeling problems to improve the e ciency of classi cation. We now formalize our intuitions and present our proposed approach in detail.
We have presented the training and inference objectives of sequence labeling
problems in equations (
In the previous sections, we have identi ed CF s as the class of features that explicitly capture complex relationships among input variables at relative sequence positions. We have also de ned CF s as compositions of AF s and that, since the partial ordering of AF s does not comply with the requirements of StructHKL, it is not feasible to leverage StructHKL for learning features in the space of AF s (and its super-space of CF s). For this reason, in the sequence labeling model, we leverage a relational kernel that computes the similarity between instances in an implicit feature space of CF s. To this end, we employ the relational subsequence kernel [?] at each sequence position (over a time window of observations around the pivot position) for the classi cation model. We now brie y discuss about relational subsequence kernels in the following paragraph.
Subsequence kernels have been used to extract relations between entities in natural language text [?], where the relations are between protein names in biomedical texts. The features are (possibly non-contiguous) sequences of word and word classes anchored by the protein names at their ends. They extend the string kernels [?] for this task.
We have de ned CF s as explicit features that capture the subset of features at the current position as well as its relative positions. To implicitly capture this feature space, we employ a relational subsequence kernel at each position of the input sequence, with the current position as the pivot position. Suppose we consider an input xip at position p for example i. Let the previous k positions relative to p have inputs xip 1; : : : xip k and next l positions relative to p have inputs xip+1; : : : xip+l. Let there be N basic features at a time-step t denoted by x1t : : : xNt :6 Essentially our sequence for the particular time-step pivoted at p, denoted by Qp, is as follows:
Qp = fx1p k ; : : : xNp k g; : : : ; fx1p 1 ; : : : xNp 1 g; fx1p ; : : : xNp g; fx1p+1 ; : : : xNp+1 g : : : fx1p+l ; : : : xNp+l g Given two sequences Qp and Qq, we de ne the relational subsequence kernel SSK(Qp; Qq) as elaborated in [?]. This kernel will implicitly enumerate all possible common subsequences between Qp and Qq. We now show that the feature space of CF s are captured by our relational subsequence kernel. Claim: Relational subsequence kernels implicitly enumerate all the features in the feature space de ned by Composite Features (CF ) given a constant context window.
Proof. By their de nition the relational subsequence kernel SSK(Qi; Qj ) will implicitly enumerate all possible common subsequences between Qi and Qj . CF s are conjunctions of features in the present time-step with features present in time-steps before and after the current time-step, which can be represented by AF s. Since we are considering all the sub-sequences in the given context (time) window in the relational kernel, we implicitly enumerate space of CF s.
We now de ne the kernel for StructSVM framework below, which represents the kernel resulting from the di erence in values for the original and the candidate sequences. This stands for the inner product, h i (Y ); i (Y 0 )i with i (Y ) de ned as: i (Y ) = (Xi; Yi) (Xi; Y ). The kernel, which is a combination of transition ( T ) and emission ( E ) kernels, is de ned as follows: 6 Ignoring the example number i for simplicity where (Xi; Yi; Y ); (Xj; Yj; Y 0 ) = T (Yi; Y; Yj; Y 0 ) + E (Xi; Yi; Y ); (Xj; Yj; Y 0 ) T Yi; Y; Yj; Y 0 ) = T (Yi; Yj) + T (Y; Y 0 ) T (Yi; Y 0 )
T (Yj; Y );
li 1 lj 1
T (Yi; Yj) = X X
p=1 q=1
li lj
= X X
(
li lj E (Xi; Yi; Y ); (Xj; Yj; Y 0 ) = X X p=1 q=1
E(xip; xjq) (yip; yjq) + (yp; y0q) (yip; y0q) (yp; yjq) In our setting of subsequence kernels for StructSVM, the kernel E (xip; xjq) is the relational subSequence kernel, where we may be considering some window time steps before and after p and q, with p and q as pivots.
The dual of the primal SVM formulation as de ned by Tsochantaridis et. al. [?] for structured output spaces with the new kernel can be written as, max X X i Y 2Si 8i; s:t: 8i; 8Y 2 Si; m X iY Y 2Si where is the Lagrange dual variable, is the loss function, Si and Sj are the active constraint sets for example i and j respectively.
Now the margin violation cost function for a candidate output sequence Y for example i (for the cutting plane algorithm) can be written as, H(Y ) = 1
(Yi; Y ) : : = 1 = 1 h i (Y ); f i X X j y0 2Sj X X j y0 2Sj jY 0 h i (Y ); j (Y 0 )i
(Yi; Y )
jY 0 (Xi; Yi; Y ); (Xj; Yj; Y 0 )
(Yi; Y )
(
iY jY 0
T (Yi; Y; Yj; Y 0 ) + E (Xi; Yi; Y ); (Xj; Yj; Y 0 )
The dual objective and the margin violation cost function can be plugged into the cutting plane algorithm to solve the objective. While this way of modeling does not result in interpretability, relational subsequence kernels do e ciently capture the relational sequential information on the inputs.
As in typical sequence labeling systems, we perform inference using a dynamic programming approach called the Viterbi algorithm [?].
The next section discusses our experiments and results. 4
Our entire implementation is in Java. Our experiments are carried out on two publicly available activity recognition datasets. The rst is the data provided by [?]. The dataset is extracted from a household tted with 14 binary sensors. Eight activities have been annotated for 4 weeks. Activities are daily house hold activities like sleeping, usingT oilet, preparingDinner, preparingBreakf ast, leavingOut, etc. A data instance is recorded for a time interval of 60 seconds and there are 40006 such data instances. Since the authors of the dataset are from the University of Amsterdam, we will refer to the dataset as the UA data. The second data is the relational activity recognition data provided by [?] of Katholieke University, Leuven. We refer to the data as KU data. The data has been collected from a kitchen environment with 25 sensors/RFID attached to objects. There are 19 activities annotated. The data has been divided into 20 sequences. In this data, we perform our experiments in a leave one out crossvalidation setup and report average of the accuracies returned from each fold.
In UA data, We use 25% of data for training and the rest for testing and report all accuracies by average across the four folds (the dataset is split into di erent sequences and each sequence is treated as an example). We report both micro-average and macro-average prediction accuracies. The micro-average accuracy is referred to as time-slice accuracy by [?], and is the average of perclass accuracies, weighted by the number of instances of the class. Macro-average accuracy, referred to as class accuracy by [?], is simply the average of the perclass accuracies. Micro-averaged accuracy is typically used as the performance evaluation measure. However, in data that is biased towards some classes, too worse macro-average is an indicator of a bad prediction model.
As we discussed previously, we leverage a relational kernel that computes the similarity between instances in an implicit feature space of CF s. To this end, we employ the relational subsequence kernel [?] at each sequence position (over a time window of observations around the pivot position) for the classi cation model. We refer to this approach as Relational Subsequence Kernels for StructSVM approach (SubseqSVM).
We have compared our approach against TildeCRF [?], StructSVM [?] and enumAF [?]. While we treat StructSVM as a baseline for our experiments, TildeCRF is a state-of-the-art approach for learning relational features for sequence labeling, and operates in the same feature space that we are interested in. In our experiments with StructSVM, individual basic features are assumed to be conditionally independent given the label.
The comparison of results on the UA dataset is outlined in Table 1. Results show that enumAF and our approach for learning complex features for sequence labeling viz. SubseqSVM performed better than the baseline approach (StructSVM) and the state-of-the-art approach (TildeCRF). Although enumAF optimally nds CF s as conjunctions of (selectively enumerated) AF s, the step for selectively enumerating AF s is based on heuristics. In contrast, SubseqSVM works on a convex formulation and learns an optimal model. This explains the better performance of SubseqSVM.
The comparison of results on the KU dataset is outlined in Table 2. As a single sequence step in this data has only one input feature, the feature space is not rich enough to evaluate the e ciency of our approach. The baseline reported the best performance. While the performance of SubseqSVM approach is slightly inferior to the baseline and the state-of-the-art, enumAF performed poorly on this dataset.
In the case of the UA dataset, both enumAF and SubseqSVM took 24 hours approximately to train the model. In comparison, TildeCRF and StructSVM took 0.5 hours and 20 hours, respectively. On the KU data, enumAF took around 24 hours and SubseqSVM took approximately 1.5 hours to train the model. In comparison, TildeCRF and StructSVM took 10 minutes and 15 hours, respectively. We now present an analysis of the progression of results on UA data, using di erent categories of features we have experimented with.
Micro avg. Macro avg. tildeCRF 56.22( 12.08) 35.36 ( 6.55) StructSVM 58.02 ( 11.87) 35.00 ( 05.24) enumAF 60.36 ( 6.99) 30.39 ( 4.31)
SubseqSVM 65.25( 4.81) 29.34 ( 2.78) Table 1: Micro average accuracy and macro average accuracy of classi cation in percentage using various approaches on UA data.
Micro avg. Macro avg. tildeCRF 66.04 ( 13:50) 84.01 ( 8.76) StructSVM 66.35 ( 17.16) 66.64 ( 16.04) enumAF 33.24 ( 15:72) 23.02 ( 11.13) SubseqSVM 64.66 ( 8.42) 63.08 ( 7.05) Table 2: Micro average accuracy and macro average accuracy of classi cation in percentage using various approaches on KU data.
The progression on experiments on UA data based on feature categories is shown in Table 3. The baseline for sequence labeling can be one among the approaches that assume conditional independence among individual features, given the label. HMM, CRF, and StructSVM falls into this category. These approaches consider input features at a sequence step and assumes conditional independence among them given the label. Since StructSVM is the state-of-theart in this category, we use StructSVM results for comparison. The next level of features is the set of simple conjuncts SC, which are conjunctions of input features at a single sequence step. SCs capture relationships among co-occurring features. We present the StructHKL results for this. Next is the category of CF s, which are capable of capturing input relationships across time steps in sequence labeling. We present the results of SubseqSVM in this category. Recent works have shown the importance of learning the input structure, in the form of relational features, for sequence labeling problems [?,?,?]. Most of the existing feature learning approaches employ greedy search techniques to discover relational features. In this work, we discussed approaches that looked into learning optimal relational features for sequence labeling. We identify that the relational feature space is exponentially large and therefore, learning explicit features of arbitrary complexity in our most general feature subspace, is a hard task. To this end, we presented an approach that learns relational sequence labeling models (capturing the richness of relational features implicitly) by leveraging relational subsequence kernels in the dual objective of the StructSVM framework. From our discussions and empirical analysis, we conclude that it is desirable to use powerful kernels that capture the relational features implicitly, although the resulting model may not be interpretable.