Year: 2019

Abstract:
In this paper, a Gaussian conditional random field model for structured binary classification (GCRFBC) is proposed. The model is applicable to classification problems with undirected graphs, intractable for standard classification CRFs. The model representation of GCRFBC is extended by latent variables which yield some appealing properties. Thanks to the GCRF latent structure, the model becomes tractable, efficient, and open to improvements previously applied to GCRF regression. Two different forms of the algorithm are presented: GCRFBCb (GCRGBC Bayesian) and GCRFBCnb (GCRFBC non-Bayesian). The extended method of local variational approximation of sigmoid function is used for solving empirical Bayes in GCRFBCb variant, whereas MAP value of latent variables is the basis for learning and inference in the GCRFBCnb variant. The inference in GCRFBCb is solved by Newton-Cotes formulas for one-dimensional integration. Both models are evaluated on synthetic data and real-world data. It was shown that both models achieve better prediction performance than relevant baselines. Advantages and disadvantages of the proposed models are discussed.

heading: 1 INTRODUCTION
text: Increased quantity and variety of sources of data with correlated outputs, so called structured data, created an opportunity for exploiting additional information between dependent outputs to achieve better prediction performance. One of the most successful probabilistic models for structured output classification problems are conditional random fields (CRF) (Sutton & McCallum, 2006). The main advantages of CRFs lie in their discriminatory nature, resulting in the relaxation of independence assumptions and the label bias problem that are present in many graphical models. Aside of many advantages, CRFs also have many drawbacks mostly resulting in high computational cost or intractability of inference and learning. A wide range of different approaches of tackling these problems has been proposed, and they motivate our work, too.
One of the popular methods for structured regression based on CRFs – Gausian conditional random fields (GCRF) – has the form of multivariate Gaussian distribution (Radosavljevic et al., 2010). The main assumption of the model is that the relations between outputs are presented in quadratic form. It has convex loss function and, consequently, efficient inference and learning, and expensive sampling methods are not used.
In this paper, a new model of Gaussian conditional random fields for binary classification is proposed (GCRFBC). GCRFBC builds upon regression GCRF model which is used to define latent variables over which output dependencies are defined. The model assumes that discrete outputs yi are conditionally independent conditioned on continuous latent variables zi which follow a distribution modeled by a GCRF. That way, relations between discrete outputs are not expressed directly. Two different inference and learning approaches are proposed in this paper. The first one is based on evaluating empirical Bayes by marginalizing latent variables (GCRFBCb), whereas MAP value of latent variables is the basis for learning and inference in the second model (GCRFBCnb). In order to derive GCRFBCb model and its learning procedure the variational approximation of Bayesian logistic regression (Jaakkola & Jordan, 2000) is generalized.
Compared to CRFs and structured SVM classifiers, the GCRFBC models have some appealing properties:
• The model is applicable to classification problems with undirected graphs, intractable for standard classification CRFs. Thanks to the GCRF latent structure, the model becomes tractable, efficient and open to improvements previously applied to GCRF regression models.
• Defining correlations directly between discrete outputs may introduce unnecessary noise to the model (Tan et al., 2010). This problem can be solved by defining structured relations on a latent continuous variable space.
• In case that unstructured predictors are unreliable, which is signaled by their large variance (diagonal elements in the covariance matrix), it is simple to marginalize over latent variable space and obtain better results.
GCRFBC model is relying on the assumption that the underlying distribution of latent variables is multivariate normal distribution, due to that in the case when this distribution cannot be fitted well to the data (e.g. when the distribution of latent variables is multimodal) the model will not perform as well as it is expected. The proposed models are experimentally tested on both synthetic and real-world datasets in terms of predictive performance and computation time. In experiments with synthetic datasets, the results clearly indicate that the the empirical Bayes approach (GCRFBCb) better exploits output dependence structure, more so as the variance of the latent variables increases. We also tested both approaches on real-world datasets of predicting ski lift congestion, gene function classification, classification of music according to emotion and highway congestion. Both GCRFBC models outperformed ridge logistic regression, lasso logistic regression, neural network, random forest, and structured SVM classifiers, demonstrating that the proposed models can exploit output dependencies in a real-world setting.

heading: 2 RELATED WORK
text: An extensive review of binary and multi-label classification with structured output is provided in Su (2015). A number of different studies related to graph based methods for regression can be found in the literature (Fox, 2015). CRFs were successfully applied on a variety of different structured tasks (Cotterell & Duh, 2017; Zhang et al., 2015; Masada & Bunescu, 2017; Zia et al., 2018) and different model adaptations can be found in literature Kim (2017); Maaten et al. (2011). Recently, successful unifications of deep learning and CRFs have been proposed Chen et al. (2016); Kosov et al. (2018). Moreover, implementation of deep neural networks as potential functions is presented in form of structure prediction energy networks (SPEN) Belanger & McCallum (2016); Belanger et al. (2017). Adaptation of normalazing flows in SPEN structure is presented in Lu & Huang (2019).
An extensive review on topic of binary and multi-label classification with structured output is provided in Su (2015). Large number of different studies related to graph based methods for regression can be found in the literature (Fox, 2015). CRFs were successfully applied on a variety of different structured tasks, such as: low-resource named entity recognition (Cotterell & Duh, 2017), image segmentation (Zhang et al., 2015), chord recognition (Masada & Bunescu, 2017) and word segmentation (Zia et al., 2018). The mixture of CRFs capable to model data that come from multiple different sources or domains is presented in Kim (2017). The method is related to the well known hidden-unit CRF (HUCRF) (Maaten et al., 2011). The conditional likelihood and expectation minimization (EM) procedure for learning have been derived there. The mixtures of CRF models were implemented on several real-world applications resulting in prediction improvement. Recently, a model based on unification of deep learning and CRF was developed by Chen et al. (2016). The deep CRF model showed better performance compared to either shallow CRFs or deep learning methods on their own. Similarly, the combination of CRFs and deep convolutional neural networks was evaluated on an example of environmental microorganisms labeling (Kosov et al., 2018). The spatial relations among outputs were taken in consideration and experimental results have shown satisfactory results.
The GCRF model was first implemented for the task of low-level computer vision (Tappen et al., 2007). Since then, various different adaptations and approximations of GCRF were proposed (Radosavljevic et al., 2014). The parameter space for the GCRF model is extended to facilitate joint modelling of positive and negative influences (Glass et al., 2016). In addition, the model is extended by bias term into link weight and solved as a part of convex optimization. Semi-supervised
marginalized Gaussian conditional random fields (MGCRF) model for dealing with missing variables was proposed by Stojanovic et al. (2015). The benefits of the model were proved on partially observed data and showed better prediction performance than alternative semi-supervised structured models.A comprehensive review of continuous conditional random fields (CCRF) was provided in Radosavljevic et al. (2010). The sparse conditional random fields obtained by l1 regularization are first proposed and evaluated by Wytock & Kolter (2013). Additionaly, Frot et al. (2018) presented GCRF with the latent variable decomposition and derived convergence bounds for the estimator that is well behaved in high dimensional regime. An adaptation of GCRF on discrete output was briefly discussed in Radosavljevic (2011), as a part of future work. This discussion motivates our work, but our approach is different in technical aspects.

heading: 3 METHODOLOGY
text: In this section we first present already known GCRF model for regression and then we propose GCRFBC model for binary classification and two approaches to inference and learning.

heading: 3.1 BACKGROUND MATERIAL
text: GCRF is a discriminative graph-based regression model (Radosavljevic et al., 2010). Nodes of the graph are variables y = (y1, y2, . . . , yN ), which need to be predicted given a set of features x. The attributes x = (x1,x2, . . . ,xN ) interact with each node yi independently of one another, while the relations between outputs are expressed by pairwise interaction function. In order to learn parameters of the model, a training set of vectors of attributes x and real-valued response variables y are provided. The generalized form of the conditional distribution P ( y|x,α,β ) is:
P ( y|x,α,β ) =
1
Z (x,α,β) exp − N∑ i=1 K∑ k=1 αk ( yi −Rk (xi) )2 −∑ i 6=j L∑ l=1 βlS l ij(yi − yj)2  (1)
First sum models relations between outputs yi and corresponding input vector xi and the second one models pairwise relations between nodes. Rk(xi) represents an unstructured predictor of yi for each node in the graph and Slij is value that expresses similarity between nodes i and j in graph l. Unstructured predictor can be any regression model that gives prediction of output yi for given attributes xi. K is the total number of unstructured predictors. L is the total number of graphs (similarity functions). Graphs can express any kind of binary relations between nodes e.g., spatial and temporal correlations between outputs. Z is a partition function and vectors α and β are learnable parameters. One of the main advantages of GCRF is the ability to express different relations between outputs by variety of graphs and ability to learn which graphs are significant for prediction. The quadratic form of interaction and association potential enables conditional distribution P (y|x,α,β) to be expressed as multivariate Gaussian distribution (Radosavljevic et al., 2010):
P (y|x,α,β) = 1 (2π) N 2 |Σ| 12
exp ( −1
2 (y − µ)TΣ−1(y − µ)
) (2)
Precision matrix Σ−1 = 2Q and distribution mean µ = Σb are defined as, respectively:
Q =
{∑K k=1 αk + ∑N h=1 ∑L l=1 βlS l ih, if i = j
− ∑L l=1 βlS l ij , if i 6= j
(3)
bi = 2  K∑ k=1 αkRk(xi)  (4) Due to concavity of multivariate Gaussian distribution, the inference task argmax
y P (y|x,α,β) is
straightforward. The maximum posterior estimate of y is the distribution expectation µ.
The objective of the learning task is to optimize parameters α and β by maximizing conditional log likelihood argmax
α,β
∑ y logP (y|x,α,β). One way to ensure positive definiteness of the covariance
matrix of GCRF is to require diagonal dominance (Strang et al., 1993). This can be ensured by imposing constraints that all elements of α and β be greater than 0 (Radosavljevic et al., 2010).

heading: 3.2 GCRFBC MODEL REPRESENTATION
text: One way of adapting GCRF to classification problem is by approximating discrete outputs by suitably defining continuous outputs. Namely, GCRF can provide dependence structure over continuous variables which can be passed through sigmoid function. That way the relationship between regression GCRF and classification GCRF is similar to the relationship between linear and logistic regression, but with dependent variables. Aside from allowing us to define a classification variant of GCRF, this may result in additional appealing properties: (i) The model is applicable to classification problems with undirected graphs, intractable for standard classification CRFs. Thanks to the GCRF latent structure, the model becomes tractable, efficient and open to improvements previously applied to GCRF regression models. (ii) Defining correlations directly between discrete outputs may introduce unnecessary noise to the model (Tan et al., 2010). We avoid this problem by defining structured relations on a latent continuous variable space. (iii) In case that unstructured predictors are unreliable, which is signaled by their large variance (diagonal elements in the covariance matrix), it is simple to marginalize over latent variable space and obtain better results.
It is assumed that yi are discrete binary outputs and zi are continuous latent variables assigned to each yi. Each output yi is conditionally independent of the others, given zi.
The conditional probability distribution P (yi|zi) is defined as Bernoulli distribution:
P (yi|zi) = Ber(yi|σ(zi)) = σ(zi)yi(1− σ(zi))1−yi (5)
where σ(·) is sigmoid function. Due to conditional independence assumption, the joint distribution of outputs yi can be expressed as:
P (y1, y2, . . . , yN |z) = N∏ i=1 σ(zi) yi(1− σ(zi))1−yi (6)
Furthermore, the conditional distribution P (z|x) is the same as in the classical GCRF model and has canonical form defined by multivariate Gaussian distribution. Hence, joint distribution of continuous latent variables z and outputs y given x and θ = (α1, . . . , αK , β1, . . . , βL) is is the general form of the GCRFBC model defined as:
P (y, z|x,θ) = N∏ i=1 σ(zi) yi(1− σ(zi))1−yi ·
1 (2π)N/2 ∣∣Σ(x,θ)∣∣1/2
· exp ( −1
2 (z − µ(x, θ))TΣ−1(x,θ)(z − µ(x, θ))
) (7)
We consider two ways of inference and learning in GCRFBC model: (i) GCRFBCb - with conditional probability distribution P (y|x,θ), in which variables z are marginalized over, and (ii) GCRFBCnb - with conditional probability distribution P ( y|x,θ, µz ) , in which variables z are substituted by their expectations.

heading: 3.3 INFERENCE IN GCRFBCB MODEL
text: Prediction of discrete outputs y for given features x and parameters θ is analytically intractable due to integration of the joint distribution P (y, z|x,θ) with respect to latent variables. However, due to conditional independence between nodes, it is possible to obtain P (yi = 1|x,θ).
P (yi = 1|x,θ) = ∫ z σ(zi)P (z|x,θ)dz (8)
where σ(zi) models P (yi|z). As a result of independence properties of the distribution, it holds P (yi = 1|z) = P (yi = 1|zi), and it is possible to marginalize P (z|x,θ) with respect to latent variables z′ = (z1, . . . , zi−1, zi+1, . . . , zN ):
P (yi = 1|x,θ) = ∫ zi σ(zi) (∫ z′ P (z′, zi|x,θ)dz′ ) dzi (9)
where ∫ z′ P (z′, zi|x,θ)dz′ is normal distribution with mean µ = µi and variance σ2i = Σii. Therefore, it holds:
P (yi = 1|x,θ) = ∫ +∞ −∞ σ(zi)N (zi|µi, σ2i )dzi (10)
The evaluation of P (yi = 0|x,θ) is straightforward: P (yi = 0|x,θ) = 1− P (yi = 1|x,θ). The one-dimensional integral is still analytically intractable, but can be effectively evaluated by onedimensional numerical integration. The proposed inference approach can be effectively used in case of huge number of nodes, due to low computational cost of one-dimensional numerical integration.

heading: 3.4 INFERENCE IN GCRFBCNB MODEL
text: The inference procedure in GCRFBCnb is much simpler, because marginalization with respect to latent variables is not performed. To predict y, it is necessary to evaluate posterior maximum of latent variable zmax = argmax
z P (z|x,θ), which is straightforward due to normal form of GCRF.
Therefore, it holds zmax = µz,i. The conditional distribution P (yi = 1|x,µz,i,θ), where µz,i is expectation of latent variable zi, can be expressed as:
P (yi = 1|x,µz,θ) = σ(µz,i) = 1
1 + exp(−µz,i) (11)

heading: 3.5 LEARNING IN GCRFBCB MODEL
text: In comparison with inference, learning procedure is more complicated. Evaluation of the conditional log likelihood is intractable, since latent variables cannot be analytically marginalized. The conditional log likelihood is expressed as:
L ( Y |X,θ ) = log ∫ Z P (Y,Z|X,θ)dZ = M∑ j=1 log ∫ zj P (yj, zj |xj ,θ)dzj = M∑ j=1 Lj(yj |xj ,θ)
(12) Lj(yj |xj ,θ) = log ∫ zj N∏ i=1 σ(zji) yji(1− σ(zji))1−yji exp(− 12 (zj − µj) TΣ−1j (zj − µj)) (2π)N/2 ∣∣Σj∣∣1/2 dzj
(13) where Y ∈ RM×N is complete dataset of outputs, X ∈ RM×N×A is complete dataset of features, M is the total number of instances and A is the total number of features. Please note that each instance is structured, so while different instances are independent of each other, variables within one instance are dependent.
One way to approximate integral in conditional log likelihood is by local variational approximation. Jaakkola & Jordan (2000) derived lower bound for sigmoid function, which can be expressed as:
σ(x) > σ(ξ) exp{(x− ξ)/2− λ(ξ)(x2 − ξ2)} (14) where λ(ξ) = − 12ξ · [ σ(ξ)− 12 ] and ξ is a variational parameter. The Eq. 14 is called ξ transformation of sigmoid function and it yields maximum value when ξ = x. This approximation can be applied to the model defined by Eq. 13, but the variational approximation has to be further extended because of the product of sigmoid functions, such that:
P (yj , zj |xj ,θ) = P (yj |zj)P (zj |xj ,θ) ≥ P (yj , zj |xj ,θ, ξj) (15)
P (yj , zj |xj ,θ, ξj) = N∏ i=1 σ(ξji) exp ( zjiyji − zji + ξji 2 − λ(ξji)(z2ji − ξ2ji) ) ·
1 (2π)N/2 ∣∣Σj∣∣1/2 exp
( −1
2 (zj − µj)TΣ−1j (zj − µj)
) (16)
The Eq. 16 can be arranged in the form suitable for integration. Detailed derivation of lower bound of conditional log likelihood is presented in Appendix A. The lower bound of conditional log likelihood
L(yj |xj ,θ, ξj) is defined as:
Lj(yj |xj ,θ, ξj) = logP (yj |xj ,θ, ξj) = N∑ i=1 ( log σ(ξji)− ξji 2 + λ(ξji)ξ 2 ji ) −
1 2 µTj Σ −1 j µj + 1 2 mTj S −1 j mj + 1 2 log |Sj |
(17)
where:
S−1j = Σ −1 j + 2Λj mj = Σj ( (yj − 1
2 I) + Σ−1j µj
) (18)
Λj =  λ(ξj1) 0 0 . . . 0 0 λ(ξj2) 0 . . . 0 ... ... ... . . . ...
0 0 0 . . . λ(ξjN )  (19) GCRFBCb uses the derivative of conditional log likelihood in order to find the optimal values for parameters α, β and matrix of variational parameters ξ ∈ RM×N . In order to ensure positive definiteness of normal distribution involved, it is sufficient to constrain parameteres α > 0 and β > 0. The partial derivatives of lower bound of conditional log likelihood are presented in Appendix B. For constrained optimization, the truncated Newton algorithm was used Nocedal & Wright (2006); Facchinei et al. (2002). The target function is not convex, so finding a global optimum cannot be guaranteed.

heading: 3.6 LEARNING IN GCRFBCNB MODEL
text: In GCRFBCnb the mode of posterior distribution of continuous latent variable z is evaluated directly, so there is no need for approximation. The conditional log likelihood can be expressed as: L ( Y |X,θ,µ ) = logP (Y |X,θ,µ) =
M∑ j=1 N∑ i=1 logP (yji|xj ,θ, µji) = M∑ j=1 N∑ i=1 Lji(yji|xj ,θ, µji)
(20) Lji(yji|xj ,θ, µji) = yji log σ(µji) + (1− yji) log ( 1− σ(µji) ) (21)
The partial derivatives of conditional log likelihood are presented in Appendix C.

heading: 4 EXPERIMENTAL EVALUATION
text: Both proposed models were tested and compared on synthetic data and real-world tasks.1 All compared classifiers were compared in terms of the area under ROC curve (AUC) and accuracy 2 (ACC). Moreover, the lower bound (in case of GCRFBCb) of conditional log likelihood L ( Y |X,θ,µ ) and
actual value (in case of GCRFBCnb) of conditional log likelihood L ( Y |X,θ ) of obtained values on synthetic test dataset were also reported.

heading: 4.1 SYNTHETIC DATASET
text: The main goal of experiments on synthetic datasets was to examine models under various controlled conditions, and show advantages and disadvantages of each. In all experiments on synthetic datasets two different graphs were used (hence β ∈ R2) and two unstructured predictors (hence α ∈ R2). The results of experiments on synthetic datasets are presented in Appendix D.
It can be noticed, that in cases where norm of the variances of latent variables is small, both models have equal performance considering AUC and conditional log likelihood L ( Y |X,θ ) . This is the case when values of parameters α used in data generating process are greater or equal to the
1Implementation can be found at https://github.com/andrijaster/GCRFBC B NB 2PyStruct package does not have option of returning SSVM and CRF confidence values for AUC evaluation
values of parameters β. This means that the information provided by unstructured predictors is more important for classifications task than the information provided by output structure. Therefore, conditional distribution P (y, z|x,θ) is concentrated around mean value and MAP estimate is a satisfactory approximation. However, when data is generated from distribution with significantly higher values of β than α, the GCRFBCb performs significantly better than GCRFBCnb. For the larger values of variance norm, this difference is also large. This means that the structure between outputs has significant contribution to solving the classification task. It can be concluded that GCRFBCb has at least equal prediction performance as GCRFBCnb. Also, it can be argued that the models were generally able to utilize most of the information (from both features and the structure between outputs), which can be seen through AUC values. In addition, distribution of local variational parameters were analyzed during learning. It is noticed that in each epoch, the variance of this distribution is small and that the parameters can be clustered and their number significantly reduced. Therefore, it is possible to significantly lower down computational and memory costs of GCRFBCb learning procedure, but that’s out of the scope of this paper.

heading: 4.2 PERFORMANCE ON REAL-WORLD DATASETS

heading: 4.2.1 SKI LIFTS CONGESTION
text: Data used in this research includes information on ski lift gate entrances in Kopaonik ski resorts, for the period March 15 to March 30 for the seasons from 2006 to 2011. The goal is to predict occurrence of crowding on ski lifts for 40 minutes in advance. Total number of instances in dataset was 4,850 for each ski lift, which is 33,950 in total.
Relatively simple method for crowding detection was devised for labelling data. We assume that, if the crowding at some gate occurs, distributions of skiing times from other gates to that gate within some time window get shifted towards larger values. We model probability distribution of skiing time between two gates by the well-known parametric method of kernel density estimation (KDE) (Silverman, 2018). The distribution shift is measured with respect to the mode of the distribution. The dataset is generated by observing shifts in time windows of 5 minutes. When the mode of the distribution of skiing times within that window is greater than the mode for the whole time-span, the instance is labeled by 1 (crowding) and otherwise, it is labeled by 0 (no crowding). In order to obtain more information from the data distribution, additional 18 features were extracted.
Four different unstructured predictors that were trained on each class separately were used: ridge logistic regression, LASSO logistic regression, neural network and random forest, whereas additional two unstructured predictors: decision tree and neural network were trained on all nodes together. Additionally, three structural support vector machine and two CRFs classifiers were used (Müller & Behnke, 2014). Fully connected graph of SSVM and CRF models are defined as SSVM-full and CRF-full, whereas Chow-Liu tree method for specifying edge connections are defined as SSVMtree and CRF-tree, respectively. In the SSVM-independent model the nodes of the graph are not connected.
Six different weighted graphs were used to capture dependence structure between ski lifts (nodes):χ2 statistics on labels of training set, mutual information between labels, correlation matrix between outputs of over-fitted neural networks, norm of difference between vectors of labels and two graphs were defined based on difference of vectors of historical labels and on differences of historical averages of skier times.
The AUC score and ACC of structured and unstructured predictors, along with the total computational time are shown in Table 1. It can be observed that GCRFBCb and GCRBCnb outperformed unstructured and other structured predictors in all cases. Based on evaluated parameters it could be concluded that dependence structure has significant impact on overall prediction performance, even though, due to low values of norm of variance, GCRFBCb and GCRFBCnb have equal AUC scores. It can be summarized that advantages of structured models compared to unstructured are obvious, but in this particular task due to equal prediction performance and its lower computational and memory complexity, GCRFBCnb is the best choice for this specific application.

heading: 4.2.2 MULTI-LABEL CLASSIFICATION OF MUSIC ACCORDING TO EMOTION
text: The dataset used for this work consists of 100 songs from 7 different genres. The collection was created from 233 musical albums choosing three songs from each album. 8 rhythmic and 64 timbre features are extracted. The music is labeled in 6 categories of emotions: amazed-surprised, happypleased, relaxing-calm, quiet-still, sad-lonely and angry-fearful (Trohidis et al., 2008). Total number of instances in dataset was 593. Four different weighted graphs were used: statistics on labels of training set, mutual information between labels, correlation matrix between outputs of over-fitted neural networks and norm of difference between vectors of labels. Same unstructured predictors as in ski lift congestion problem were used, along with three structural support vector machine classifiers.
The performances of models are evaluated by 10 fold cross validation. The AUC score and ACC of structured and unstructured predictors, along with the total computational time are shown in Table 2. It can be seen that GCRFBCb has achieved the best prediction performances. The ACC of GCRFBC models are significantly better than the SSVM performances. The AUC score and ACC of GCRGBCb are higher than the best result (AUC = 0.8237) presented in original paper (Trohidis et al., 2008). As in previous cases, computational time of GCRFBCb is significantly longer compared to GCRFBCnb and SSVM models.

heading: 4.2.3 GENE FUNCTION CLASSIFICATION
text: This dataset is formed by micro-array expression data and phylogenetic profiles with 2417 genes (instances). The number of features is 103, whereas each gene is associated with the set of 14 groups (Elisseeff & Weston, 2002). The same unstructured, structured predictors and weighted graphs, as
in music according to emotion classification, were used. The 10-fold cross validation results of the classification are shown in Table 3.
It can be observed that both GCRFBCb and GCRFBCnb achieved significantly better results in comparison with unstructured predictors. However, neural network trained on all data together achieved the same ACC scores as GCRFBCb. The AUC of GCRFBCb has outperformed Random forest classifier by 19%, whereas SSVM - tree has better ACC compared to GCRFBCnb. It also outperformed GCRFCnb, but as expected, its computation time was longer. In addition, the computation time of CRFs models are longer compared to GCRFBCb

heading: 4.2.4 HIGHWAY CONGESTION
text: The E70-E75 motorway is a major transit motorway in Serbia. With 504 kilometers, it is the one the major transit motorway in Serbia. It crosses the country from north-west to south, starting at Batrovci border crossing with the Republic of Croatia and ending with Preševo border crossing with the Republic of North Macedonia.
One of the biggest problems in E70-E75 motorway is high congestion that frequently occurs. One of the reasons lies in lack of open toll stations. In order to mitigate congestion problem, it is necessary to predict its occurrence and open enough toll stations. Data used in this research includes information of car entrance and exit for the year 2017. Two different sections were analyzed: Belgrade - Adaševci and Niš - Belgrade. The section Belgrade - Adaševci was analyzed for the period of January 2017, whereas section Niš - Belgrade was analyzed for the period of April - July 2017. The congestion was labeled using the similar technique based on KDE as presented in the ski lifts congestion problem. Based on raw datasets for sections Niš - Belgrade and Belgrade - Adaševci with 5,132,918 and 487,767 instances, respectively, a new dataset for section Niš - Belgrade is generated by observing shifts in time windows of 10 minutes due to large number of vehicles, whereas in the case of section Belgrade - Adaševci the shifts are observed in time windows of 20 minutes. Total numbers of instances for sections Belgrade - Adaševci and Niš - Belgrade are 50,964 and 235,872, whereas numbers of highway exits (outputs) are 6 and 18, respectively. The extracted features are similar to the ones presented in ski congestion problem. The χ2 statistics, mutual information, correlation matrix and difference of vectors of historical labels were used to capture dependence structure, whereas the same unstructured predictors as in ski lifts congestion problem were evaluated. The classification results, validated by 10 fold cross validation, are presented in Table 4.
The GCRFBCnb achieved the highest AUC and ACC scores in the section Belgrade - Adaševci, whereas GCRFBCb has better prediction performance in section Niš - Belgrade. Moreover, in case of section Niš - Belgrade, GCRFBCb has worse ACC score than fully connected CRF, whereas CRF-tree outperformed GCRFBCnb in section Belgrade - Adaševci

heading: 5 CONCLUSION
text: In this paper, a new model, called Gaussian Conditional Random Fields for Binary Classification (GCRFBC) is presented. The model is based on latent GCRF structure, which means that intractable structured classification problem can become tractable and efficiently solved. Moreover, the improvements previously applied to regression GCRF can be easily extended to GCRFBC. Two different variants of GCRFBC were derived: GCRFBCb and GCRFBCnb. Empirical Bayes (marginalization of latent variables) by local variational methods is used in optimization procedure of GCFRBCb, whereas MAP estimate of latent variables is applied in GCRFBCnb. Based on presented methodology and obtained experimental results on synthetic and real-world datasets it can be concluded that both GCRFBCb and GCRFBCnb models have better prediction performance compared to the analysed structured unstructured predictors. Additionaly, GCRFBCb has better performance considering AUC score, ACC and lower bound of conditional log likelihood L ( Y |X,θ ) compared to GCRFBCnb, in cases where norm of the variances of latent variables is high. However, in cases where norm of the variances is close to zero, both models have equal prediction performance. Due to high memory and computational complexity of GCRFBCb compared to GCRFBCnb, in cases where norm of the variances is close to zero, it is reasonable to use GCRFBCnb. Additionally, the trade off between complexity and accuracy can be made in situation where norm of the variances is high. Further studies should address extending GCRFBC to structured multi-label classification problems, and lower computational complexity of GCRFBCb by considering efficient approximations.

heading: A DERIVATION OF LOWER BOUND OF CONDITIONAL LIKELIHOOD
text: In this section we derive lower bound of conditional likelihood. In order to obtain suitable form of joint distribution that can be easily integrated, the lower bound for sigmoid function was used (Jaakkola & Jordan, 2000). The lower bound of joint distribution P (yj , zj |xj ,θ) can be expressed as:
P (yj , zj |xj ,θ) = P (yj |zj)P (zj |xj ,θ) ≥ P (yj , zj |xj ,θ, ξj) (22)
P (yj , zj |xj ,θ, ξj) = N∏ i=1 σ(ξji) exp ( zjiyji − zji + ξji 2 − λ(ξji)(z2ji − ξ2ji) ) ·
1 (2π)N/2 ∣∣Σj∣∣1/2 exp
( −1
2 (zj − µj)TΣ−1j (zj − µj) ) (23) The simplified form of Eq. 23 can be represented by rearranging terms in the following form:
P (yj , zj |xj ,θ, ξj) = T (ξj) exp ( zTj (yj − 1
2 I)− λzTj zj −
1 2 zTj Σ −1 j zj + z T j Σ −1 j µ
) (24)
T (ξj) = 1 (2π)N/2 ∣∣Σj∣∣1/2 N∏ i=1 σ(ξji) exp ( −1 2 µTj Σ −1 j µj − ξji 2 + λ(ξji)ξ 2 ji ) (25)
The lower bound of likelihood P (yj |xj ,θ, ξj) can be obtained by marginalization of zj as: P (yj |xj ,θ, ξj) = ∫ P (yj , zj |xj ,θ, ξj)dzj
= T (ξj) ∫ exp ( zTj (yj − 1
2 I)− ΛjzTj zj −
1 2 zTj Σ −1 j zj + z T j Σ −1 j µj
) dzj
= T (ξj) ∫ exp ( −1
2 zTj (Σ −1 j + 2Λj)zj+
zTj (Σ −1 j + 2Λj)(Σ −1 j + 2Λj) −1((yj − 1 2 I) + Σ−1j µj)
) dzj
(26)
The lower bound of likelihood P (yj |xj ,θ, ξj) can be transformed in the following form:
P (yj |xj ,θ, ξj) = T (ξj) ∫ exp ( −1
2 (zj −mj)TS−1j (zj −mj) +
1 2 mTj S −1 j mj
) dzj
= T (ξj) exp ( 1
2 mTj S −1 j mj
)∫ exp ( −1
2 (zj −mj)TS−1j (zj −mj)
) dzj
(27)
where S−1j = Σ −1 j + 2Λj andmj = Σj ( (yj − 12I) + Σ −1 j µj ) .
This integration is easily performed by noting that it is the integral over an unnormalized Gaussian distribution, which yields:
P (yj |xj ,θ, ξj) = (2π)N/2 ∣∣Σj∣∣1/2 T (ξj) exp(1
2 mTj S −1mj
) |Sj |1/2 (28)
The final form of the lower bound of conditional log likelihood Lj(yj |xj ,θ, ξj) is:
Lj(yj |xj ,θ, ξj) = logP (yj |xj ,θ, ξj) = N∑ i=1 ( log σ(ξji)− ξji 2 + λ(ξji)ξ 2 ji ) −
1 2 µTj Σ −1 j µj + 1 2 mTj S −1 j mj + 1 2 log |Sj |
(29)

heading: B PARTIAL DERIVATIVE OF LOWER BOUND OF CONDITIONAL LOG LIKELIHOOD
text: The partial derivative of lower bound of conditional log likelihood (GCRFBCb) ∂Lj(yj |xj ,θ,ξj)
∂αk is
computed as:
∂Lj(yj |xj ,θ, ξj) ∂αk =− 1 2 Tr ( Sj ∂S−1j ∂αk ) + ∂mTj ∂αk S−1j mj + 1 2 mTj ∂S−1j ∂αk mj
− µTj ∂αk Σ−1j µj − 1 2 µTj ∂Σ−1j ∂αk + 1 2 Tr ( Σj ∂Σ−1j ∂αk ) (30) where:
∂S−1j ∂αk = ∂Σ−1j ∂αk = { 2, if i = j 0, if i 6= j (31)
∂mTj ∂αk
= − ( yj − 1
2 I + µTj Σ −1 j ) Sj ∂S−1j ∂αk Sj + ∂µTj ∂αk Σ−1j Sj + µ T j ∂Σ−1j αk Sj (32)
∂µTj ∂αk =
( 2αkRk(x)−
∂Σ−1j ∂αk µj
)T ΣTj (33)
Similarly partial derivatives with respect to β can be defined as:
∂Lj(yj |xj ,θ, ξj) ∂βl =− 1 2 Tr ( Sj ∂S−1j ∂βl ) + ∂mTj ∂βl S−1j mj + 1 2 mTj ∂S−1j ∂βl mj
− µTj ∂βl Σ−1j µj − 1 2 µTj ∂Σ−1j ∂βl + 1 2 Tr ( Σj ∂Σ−1j ∂βl ) (34) where:
∂S−1j ∂βl = ∂Σ−1j ∂βl =
{∑N n=1 e l inS l in(x), if i = j
−elijSlij(x), if i 6= j (35)
∂mTj ∂βl
= − ( yj − 1
2 I + µTj Σ −1 j ) Sj ∂S−1j ∂βl Sj + ∂µTj ∂βl Σ−1j Sj + µ T j ∂Σ−1j βl Sj (36)
∂µTj ∂βl = ( − ∂Σ−1j ∂βl µj )T ΣTj (37)
In the same manner partial derivatives of conditional log likelihood with respect to ξji are:
∂Lj(yj |xj ,θ, ξj) ∂ξji = −1 2 Tr
( 2Sj
∂Λj ∂ξji
) − [ 2 ( yj − 1
2 I ) Sj ∂Λj ∂ξji Sj ] S−1j mj
+mTj ∂Λj ∂ξji mj + N∑ i=1 ( 1 σ(ξji) + 1 2 ξji ) ∂σ(ξji) ∂ξji + 1 2 ( σ(ξji)− 3 4 ) (38)
where:
∂Λj ∂ξji =  0 0 0 . . . 0 ... . . . ... . . . ... 0 0 ∂λ(ξji) ∂ξji . . . 0 ... ... ... . . . ...
0 0 0 . . . 0
 (39)
∂σ(ξji)
∂ξij = σ(ξji)(1− σ(ξji)) (40)
∂λ(ξji)
∂ξji =
1
2ξji
∂σ(ξji) ∂ξji − 1 2
( σ(ξji)− 1
2
) 1
ξ2ji (41)

heading: C PARTIAL DERIVATIVE OF CONDITIONAL LOG LIKELIHOOD
text: The derivatives of the conditional log likelihood (GCRFBCnb) with respect to α and β are defined as, respectively:
∂Lji(yji|xj ,θ, µji) ∂αk
= ( yji − σ(µji) ) ∂µji ∂αk
(42)
∂Lji(yji|xj ,θ, µji) ∂αl
= ( yji − σ(µji) ) ∂µji ∂βl
(43)
where ∂µji∂αk and ∂µji ∂βl are elements of the vectors ∂µj∂αk and ∂µj ∂βl and can be obtained by Eqs. 33 and 37, respectively.

heading: D SYNTHETIC DATASET RESULTS
text: In order to generate and label graph nodes, edge weights S and unstructured predictor valuesR were randomly generated from uniform distribution. Besides, it was necessary to choose values of parameters α and β. Greater values of α indicate that the model is more confident about performance of unstructured predictors, whereas for the larger value of β the model is putting more emphasis on the dependence structure of output variables.
Six different values of parametersα and β were used. In the first groupα and β have similar values, so unstructured predictors and dependence structure between outputs have similar importance. In the second group, α has higher values compared to β, which means that unstructured predictors are more important than the dependence structure. In the third group β has higher values than α, meaning that dependence structure is more important than unstructured predictors.
Along with the AUC and conditional log likelihood, norm of the variances of latent variables (diagonal elements in the covariance matrix) is evaluated and presented in Table 5. In addition, the results of experiments are presented in Fig. 1, where for different values of α and β we show differences between GCRFBCb and GCRFBCnb (a) AUC scores, (b) log likelihoods, and (c) norm of the variances of latent variables.

Review summaries:
The work involves modifiying gaussian conditional random fields to work for classification problems instead of regression problems. The main idea is to apply a bernoulli distribution on top of the regression values to convert them to work with binary classification problems. Two variations are discussed along with the inference and learning methodology. The inference can be done using numerical approximation and learning using variational methods and is still untracktable. Comparisons with other modeling strategies is done using experiments.