# Video Genre Classification Using Weighted Kernel Logistic Regression

Authors: Ahmed A. M. Hamed; Renfa Li; Zhang Xiaoming; Cheng Xu
Journal: Advances in Multimedia
 (2013)

---

## Abstract

Due to the widening semantic gap of videos, computational tools to classify these videos into different genre are highly needed to narrow it. Classifying videos accurately demands good representation of video data and an efficient and effective model to carry out the classification task. Kernel Logistic Regression (KLR), kernel version of logistic regression (LR), proves its efficiency as a classifier, which can naturally provide probabilities and extend to multiclass classification problems. In this paper, Weighted Kernel Logistic Regression (WKLR) algorithm is implemented for video genre classification to obtain significant accuracy, and it shows accurate and faster good results.


---

## Body

## 1. Introduction

Recently, video usage gains increasing importance, especially with the advance of recent internet technology and digital media; people have access to huge amount of data through internet and television. It is difficult for people to find videos of interest among these tremendous amounts of data and use them when there is a need, and it is not feasible to watch all the videos searching for the one of interest. Exploiting content-based of video footage is continuously needed for many applications, for example, for retrieving video sequence, creating automatic video summarization, or detecting specific action or activities in a video surveillance [1]. Many works are done dealing with video classification problem by categorizing videos in certain categories or genre, bridging the wide semantic gap between computed low-level features and high-level concepts and helping people to find their videos of interest within narrow domain. To get good understanding of video content, many different techniques have been developed and different video features have been identified for better video representation. Many techniques are used for video classification such as Bayesian, Hidden Markov Model (HMM), Gaussian Mixture Model (GMM), Neural-Network (NN), and Support Vector Machine (SVM). SVM is considered a state-of-the-art algorithm for classifying binary data through its implementation of kernels. Oh et al. developed general framework to perform the fundamental tasks for video data mining which are temporal segmentation of video sequences and feature extraction and how to capture the location of motions occurring in a segment, how to cluster those segmented pieces, and how to find whether a segment has normal or abnormal events [2]. Chen et al. proposed a multimedia data mining framework for extraction of soccer goal events in soccer videos, by using combined multimodal analysis and decision tree [3]. Li et al. also proposed a general framework for indexing and summarizing sports broadcast programs, with a high-level model of sports broadcast video using the concept of an event, defined according to domain specific knowledge for different types of sports [4]. Zhong and Chang present a general framework and effective algorithms to detect the syntactic structures that are at a level higher than shots [5]. Fan et al. propose framework to achieve more effective semantic video classification by integrating the unlabeled samples with a limited number of labeled samples [6].Petrushin describes an approach to efficient search for rare and frequent video events and builds a robust GMM classifier to identify real time incoming events for indoor surveillance [7]. Hervieu et al. proposed a trajectory-based HMM framework for video content understanding to solve three tasks: unsupervised clustering of events, recognition of events corresponding to learned classes of dynamic video contents, and detection of unexpected events [1]. Adam et al. present a novel algorithm based on multiple local monitors which collect low-level statistics for detection of certain types of unusual events [8]. Shirahama et al. developed a method for retrieving events of interest in a video archive using “rough set theory” to extract multiple classification rules, each of which correctly identifies a subset of shots of the event [9].Maalouf et al. [10, 11] show that Kernel Logistic Regression (KLR), kernel version of logistic regression (LR), proves its efficiency as a classifier, which can naturally provide probabilities and extend to multiclass classification problems. KLR is used for many reasons; the first is that LR and KLR are well studied, and they do not make assumption about the distribution of the independent variables, and last reason they can be extended to handle the multiclass classification problems. Thus with the right algorithm, the computation time can be reduced less than that for the other methods, such as Support Vector Machine (SVM), which require solving constrained quadratic optimization problem.This paper is going to implement Weighted Kernel Logistic Regression (WKLR) algorithm for video genre classification, because it has direct probabilistic output and it could be extended directly to handle multiclass classification, not like SVM. The rest of the paper is organized as follows: Section2 explains Logistic Regression and Kernel Logistic Regression model, Section 3 describes the Video Feature Extraction, Section 4 presents the proposed method, Section 5 experimental results are depicted, and Section 6 concludes the paper.


## 2. Logistic Regression and Kernel Logistic Regression Model

### 2.1. Logistic Regression

In logistic regression, a single outcome variable,yi(i=1,…,n), is coded 1 with probability pi and 0 with probability 1-pi. Then pi varies as a function of some explanatory variables, such as xi mathematically it is expressed as the following formula Maalouf  et al. and King and Zeng [10, 12]:
(1)E[yi∣xi,β]=pi=exiβ1+exiβ′,
where β is a vector of parameters with the assumption that Xi0=1 so that the intercept β0 is a constant term. So that the assumption that the intercept is included in the vector β will continue from now on.  The logistic (logit) transformation is the logarithm of the odds of the positive response and is defined as
(2)ŋi=ln(pi1-pi)=xiβ.
The logit function can be expressed in matrix form as
(3)ŋ=Xβ.
The regularized log likelihood is defined as
(4)lnL(β)=∑i=1N(yilnpi+(1-yi)ln(1-pi))-λ2∥β∥2,
where the regularization (penalty) term (λ/2)∥β∥2 is added to obtain better generalization.For binary outputs, the loss function or the deviance DEV is the negative log likelihood and, given by the formula(5)DEV(β^)=-2lnL(β).


### 2.2. Kernel Logistic Regression

For Kernel logistic regression and following Maalouf et al., vectorβ can be expressed as a linear combination of the input vectors as the following [10]:
(6)β=XTα=∑i=1NαiXi,
where the vector α is known as the dual variable with dimensions, N×1. Now the logit vector ŋ can be rewritten as
(7)ŋ=XXTα=Kα,
where K=XXT is symmetric positive semidefinite Gram matrix with N×N dimensions.Considering the logit link function again shown previously,(8)ŋi=xiβ=β0+xi1β1,…,xidβd,
where the vector xi is given by xi=[1,xi1,…,xid], with i=1,…,N. this linear function represents the simplest form of an identity mapping polynomial basis function ∅ of the feature space such that
(9)∅(xi)=∅[(xi1,…,xid)]=xi.
So the logit link function can be rewritten as
(10)ŋi=∅(xi)β.
Generally the function ∅(·), maps the data from the lower dimension space to higher dimension space, so that
(11)∅:x∈Rd⟶∅(x)∈F⊆R̂.
The purpose of choosing the mapping ∅ is to convert nonlinear relation between the response variable and the independent variables into linear relation, Maalouf and Trafalis [11].Logit link function in case of KLR then could be expressed as(12)ŋi=∑j=1Nαj〈∅(xi),∅(xj)〉=∑j=1Nαjk(xi,xj)=kiα,
where ki is the ith row in the kernel matrix k(xi,xj)=K. Mercer’s sufficient and necessary conditions must be satisfied in kernel transformation function, which state that the kernel function must be expressed as inner product and must be positive and semidefinite, Maalouf and Trafalis [11]. Now
(13)ŋi=kiα=ln(pi1-pi).
This implies that
(14)pi=eŋi1+eŋi=ekiα1+ekiα=11+e-kiα.
So the regularization likelihood can be rewritten with respect to α as
(15)lnL(α)=∑i=1N(yilnpi+(1-yi)ln(1-pi))-λ2αTKα.
With deviance
(16)DEV(α)=-2lnL(α),
iteratively reweighted least squares (IRLS) method is one of the most popular techniques used to find the MLE of β in LR models, which uses Newton-Raphson algorithm to solve the score equations. KLR models can also be fitted using IRLS. Each iteration finds the weighted least squares (WLS) estimates for a given set of weights, which are used to construct a new set of weights Oh et al. [2]. The gradient and Hessian are obtained by differentiating ln L(α) with respect to α. In matrix form, the gradient is
(17)∇αlnL(α)=KT(y-p)-λKα=0,
where p is the probability vector whose elements are given in (14). And the Hessian with respect to α is
(18)∇α2lnL(α)=-KTVK-λK,
where V is a diagonal matrix with diagonal elements pi(1-pi) for i=1,…,N. The Newton-Raphson update with respect to α on the (c+1)-th iteration is
(19)α^(c+1)=α^(c)+(KTVK+λK)-1KT(y-p)-λKα(c).
Since α^(c)=(KTVK+λK)-1(KTVK+λK)α^(c), then (10) can be rewritten as
(20)α^(c+1)=(KTVK+λK)-1KTVz(c),
where z(c)=Kα^(c)+V-1(y-p) is the adjusted dependent variable or adjusted response.


### 2.3. WKLR Algorithm

Consider(21)(KTVK+λK)α^(c+1)=KTVz(c)
is a system linear equations with kernel matrix K, vector of adjusted responses z, and weighted matrix V, and the weights and response vector both depend on α^(c), which is the current estimate of the parameter vector, so specifying an initial estimate α^(0) for α^ can be solved iteratively, using the Conjugate Gradient (CG) method, which is equivalent to minimizing the quadratic problem
(22)12α^(c+1)(KTVK+λK)α^(c+1)-α^(c+1)(KTVz(c)).
In order to avoid the long computations that the CG may suffer from, a limit can be placed on the number of CG iterations, thus creating an approximate or truncated Newton direction, Maalouf and Trafalis [11].Algorithm1 describes Iterative Weighted Kernel Logistic Regression Maximum Likelihood Estimate (IWKLR MLE) using IRLS.Algorithm 1:
Data:K,y,α^(0)
Result:α^
Begin
C = 0
while|DEV(c)-DEV(c+1)DEV(c+1)|>ε1 and C≤ MAX ILRS Iteration Do
fori←1  to  n  do
p^i=11+e-xiα^;            // compute probabilities
vi=p^i(1-p^i);           // compute werights
zi=Kiα^(c)+(yi-p^i)p^i(1-p^i);        // compute adjusted response
V = diag(v1,…,vN);
(KTVK+λK)α^(c+1)=KTVz(c);      // compute α^
C=C+1
End


## 2.1. Logistic Regression

In logistic regression, a single outcome variable,yi(i=1,…,n), is coded 1 with probability pi and 0 with probability 1-pi. Then pi varies as a function of some explanatory variables, such as xi mathematically it is expressed as the following formula Maalouf  et al. and King and Zeng [10, 12]:
(1)E[yi∣xi,β]=pi=exiβ1+exiβ′,
where β is a vector of parameters with the assumption that Xi0=1 so that the intercept β0 is a constant term. So that the assumption that the intercept is included in the vector β will continue from now on.  The logistic (logit) transformation is the logarithm of the odds of the positive response and is defined as
(2)ŋi=ln(pi1-pi)=xiβ.
The logit function can be expressed in matrix form as
(3)ŋ=Xβ.
The regularized log likelihood is defined as
(4)lnL(β)=∑i=1N(yilnpi+(1-yi)ln(1-pi))-λ2∥β∥2,
where the regularization (penalty) term (λ/2)∥β∥2 is added to obtain better generalization.For binary outputs, the loss function or the deviance DEV is the negative log likelihood and, given by the formula(5)DEV(β^)=-2lnL(β).


## 2.2. Kernel Logistic Regression

For Kernel logistic regression and following Maalouf et al., vectorβ can be expressed as a linear combination of the input vectors as the following [10]:
(6)β=XTα=∑i=1NαiXi,
where the vector α is known as the dual variable with dimensions, N×1. Now the logit vector ŋ can be rewritten as
(7)ŋ=XXTα=Kα,
where K=XXT is symmetric positive semidefinite Gram matrix with N×N dimensions.Considering the logit link function again shown previously,(8)ŋi=xiβ=β0+xi1β1,…,xidβd,
where the vector xi is given by xi=[1,xi1,…,xid], with i=1,…,N. this linear function represents the simplest form of an identity mapping polynomial basis function ∅ of the feature space such that
(9)∅(xi)=∅[(xi1,…,xid)]=xi.
So the logit link function can be rewritten as
(10)ŋi=∅(xi)β.
Generally the function ∅(·), maps the data from the lower dimension space to higher dimension space, so that
(11)∅:x∈Rd⟶∅(x)∈F⊆R̂.
The purpose of choosing the mapping ∅ is to convert nonlinear relation between the response variable and the independent variables into linear relation, Maalouf and Trafalis [11].Logit link function in case of KLR then could be expressed as(12)ŋi=∑j=1Nαj〈∅(xi),∅(xj)〉=∑j=1Nαjk(xi,xj)=kiα,
where ki is the ith row in the kernel matrix k(xi,xj)=K. Mercer’s sufficient and necessary conditions must be satisfied in kernel transformation function, which state that the kernel function must be expressed as inner product and must be positive and semidefinite, Maalouf and Trafalis [11]. Now
(13)ŋi=kiα=ln(pi1-pi).
This implies that
(14)pi=eŋi1+eŋi=ekiα1+ekiα=11+e-kiα.
So the regularization likelihood can be rewritten with respect to α as
(15)lnL(α)=∑i=1N(yilnpi+(1-yi)ln(1-pi))-λ2αTKα.
With deviance
(16)DEV(α)=-2lnL(α),
iteratively reweighted least squares (IRLS) method is one of the most popular techniques used to find the MLE of β in LR models, which uses Newton-Raphson algorithm to solve the score equations. KLR models can also be fitted using IRLS. Each iteration finds the weighted least squares (WLS) estimates for a given set of weights, which are used to construct a new set of weights Oh et al. [2]. The gradient and Hessian are obtained by differentiating ln L(α) with respect to α. In matrix form, the gradient is
(17)∇αlnL(α)=KT(y-p)-λKα=0,
where p is the probability vector whose elements are given in (14). And the Hessian with respect to α is
(18)∇α2lnL(α)=-KTVK-λK,
where V is a diagonal matrix with diagonal elements pi(1-pi) for i=1,…,N. The Newton-Raphson update with respect to α on the (c+1)-th iteration is
(19)α^(c+1)=α^(c)+(KTVK+λK)-1KT(y-p)-λKα(c).
Since α^(c)=(KTVK+λK)-1(KTVK+λK)α^(c), then (10) can be rewritten as
(20)α^(c+1)=(KTVK+λK)-1KTVz(c),
where z(c)=Kα^(c)+V-1(y-p) is the adjusted dependent variable or adjusted response.


## 2.3. WKLR Algorithm

Consider(21)(KTVK+λK)α^(c+1)=KTVz(c)
is a system linear equations with kernel matrix K, vector of adjusted responses z, and weighted matrix V, and the weights and response vector both depend on α^(c), which is the current estimate of the parameter vector, so specifying an initial estimate α^(0) for α^ can be solved iteratively, using the Conjugate Gradient (CG) method, which is equivalent to minimizing the quadratic problem
(22)12α^(c+1)(KTVK+λK)α^(c+1)-α^(c+1)(KTVz(c)).
In order to avoid the long computations that the CG may suffer from, a limit can be placed on the number of CG iterations, thus creating an approximate or truncated Newton direction, Maalouf and Trafalis [11].Algorithm1 describes Iterative Weighted Kernel Logistic Regression Maximum Likelihood Estimate (IWKLR MLE) using IRLS.Algorithm 1:
Data:K,y,α^(0)
Result:α^
Begin
C = 0
while|DEV(c)-DEV(c+1)DEV(c+1)|>ε1 and C≤ MAX ILRS Iteration Do
fori←1  to  n  do
p^i=11+e-xiα^;            // compute probabilities
vi=p^i(1-p^i);           // compute werights
zi=Kiα^(c)+(yi-p^i)p^i(1-p^i);        // compute adjusted response
V = diag(v1,…,vN);
(KTVK+λK)α^(c+1)=KTVz(c);      // compute α^
C=C+1
End


## 3. Video Feature Extraction

Extracting appropriate features is vital for acceptable design of any pattern classifier. In video classification studies, the features used can be categorized as one of three which are text features, audio features, and visual features; some studies divide the features into two main categories: text features and nontext features, and the latter is divided into low-level and semantic video features. Text features contain text extracted from video and user-generated text feature. Nontext features are features extracted from images, audio, and motion; such features could be referred to as low-level features which could be defined as features extracted from video clips and audio track without reference to any external knowledge [13, 14]. Some of researches use features that correspond to cinematic principle for visual features which are composed of color, motion and average shot length. One difficulty in using low-level feature especially visual features is the huge amount of data, and the most used solution for this is using a key frame to represent the shot or by using dimensionality reduction techniques such as Principal Component Analysis (PCA) and wavelet transforms application [13, 15, 16]. Discrete transform is widely used for feature extraction and data redundancy reduction. Proportional advantages of deterministic transforms make them an interesting type of feature extraction approaches. One of the important discrete transform, is Discrete Cosine Transform (DCT), and special properties of the DCT make it a powerful transform in video processing applications [17–20]. DCT has ability for data decorrelation. There are fast algorithms for DCT realization. When applying DCT to video, some coefficients are selected and others discarded for dimension reduction of data. DCT coefficient selection is an important part of feature extraction process. DCT feature extraction is composed of two steps: the first one DCT is applied to the entire key frame to obtain the DCT coefficients, then in the second step some of coefficients are selected to construct feature vectors. The size of the DCT coefficient matrix is the same as the input frame. DCT by itself does not decrease data dimension, so it compresses most signal information in small percent of coefficients. DCT coefficients for M×N frame are calculated as follows [18]:
(23)f(u,v)=1MN∝(u)∝(v)×∑x=0M-1∑y=0N-1f(x,y)×cos((2x+1)uπ2M)×cos((2y+1)vπ2N),u=0,1,…M,v=0,1,…N,
where ∝(ω) is defined by
(24)∝(ω)={12ω=0.f(x,y) is the frame intensity function, and F(u,v) is 2D matrix of DCT coefficients. As mentioned that DCT coefficient matrix is the same as the frame size and to obtain feasible and compact low-dimensional representation of the features, PCA could be used [21]. Given N d-dimensional feature vectors [22,…,N], the mean vector calculated as
(25)τ=1N∑i=1Nxi.
And covariance matrix is calculated as
(26)c=1N∑i=1N(xi-τ)(xi-τ)T;
then the Principal Component assumes the first P significant eigenvectors of c, that is, {vi,i=1,2,…,P}. By constructing the eigenmatrix U=[v1,v2,…,vP] of dXP dimension, an arbitrary d-dimensional original feature vector x can be represented as a new low P-dimensional vector y=UT(x-τ), and P≪N, and P≪d [21]. In our proposed method we deal with shot or scene concept and take a key frame to represent the whole shot or scene. There are different algorithms implemented for extracting key frame; most of these algorithms depend on the motion part to extract the key frames. After extracting the key frames, we used DCT to obtain the DCT coefficients. PCA is applied on the DCT coefficients to select the most significant DCT coefficients.


## 4. Proposed Method

In this paper, first shot detection is used to extract the key frames from the input videos; shot detection is used because it is more sophisticated method for video summary [19, 22]. Secondly we construct X and Y variables; variable represents the features of video shot represented by the DCT_PCA data, and Y variable determines that video shot is set manually. Then feature should be scaled to values between 0 and 1 using the following equation:
(27)f(x)=11+e-x.
The advantage of this scaling is to avoid features in greater numeric range dominating those in smaller numeric range. Another advantage is to avoid numerical difficulties during the calculation when large feature value might cause numerical problem. Finally WKLR is implemented on the prepared data for classification aiming to achieve significant accuracy and making WKLR to be an effective method for video classification.


### 4.1. Performance Measures

The predictions quality evaluated using five measures: Matthews correlation coefficient (MCC),Qtotal, Predicted Positive Value (PPV), sensitivity, and specificity. FP: false positive, FN: false negative, TP: true positive, and TN: true negative. Matthews correlation coefficient can be in the range of −1 to 1, where 1 is a perfect correlation and −1 is the perfect anticorrelation. A value of 0 indicates no correlation. Its value can be calculated as follows:
(28)MCC=(TP*TN-FP*FN)(TP+FN)*(TN+FP)*(TP+FP)*(TN+FN).Q
total is the percentage of correctly classified residues, also called the prediction accuracy. It is given as follows:
(29)Qtotal=(TP+TN)TP+TN+FN+FP.PPV is the predicted positive value, also called the precision orQpred. It is given as follows:
(30)Qpred=TPTP+FP×100.Sensitivity is also called recall orQobs and is the fraction of the total positive examples that are correctly predicted, and it is calculated as follows:
(31)Qobs=TPTP+FN×100.Specificity is the fraction of total negative examples that are correctly predicted; its value can be calculated as follows:(32)Specificity=TNTN+FP×100.


## 4.1. Performance Measures

The predictions quality evaluated using five measures: Matthews correlation coefficient (MCC),Qtotal, Predicted Positive Value (PPV), sensitivity, and specificity. FP: false positive, FN: false negative, TP: true positive, and TN: true negative. Matthews correlation coefficient can be in the range of −1 to 1, where 1 is a perfect correlation and −1 is the perfect anticorrelation. A value of 0 indicates no correlation. Its value can be calculated as follows:
(28)MCC=(TP*TN-FP*FN)(TP+FN)*(TN+FP)*(TP+FP)*(TN+FN).Q
total is the percentage of correctly classified residues, also called the prediction accuracy. It is given as follows:
(29)Qtotal=(TP+TN)TP+TN+FN+FP.PPV is the predicted positive value, also called the precision orQpred. It is given as follows:
(30)Qpred=TPTP+FP×100.Sensitivity is also called recall orQobs and is the fraction of the total positive examples that are correctly predicted, and it is calculated as follows:
(31)Qobs=TPTP+FN×100.Specificity is the fraction of total negative examples that are correctly predicted; its value can be calculated as follows:(32)Specificity=TNTN+FP×100.


## 5. Experimental Results

The steps mentioned previously are tested on group of videos downloaded from youTube and Youku websites, containing the three categories, News, Sport, and Movies, and the selected frames of all those videos are almost about 10000 frames to test the accuracy of the proposed method. In the training phase, the data distributed randomly, the algorithm of WKLR MLE was implemented with 10-fold cross-validation, and max number of iterations is set to 30 for truncated Newton method.Figure1, Tables 1 and 2 show the accuracy and classification performance of each category against the other two categoriesTable 1
Number of positive and negative occurrences for each genre.
TP
TN
FP
FN
News
829
1322
119
109
Sport
664
1402
129
179
Movies
449
1621
134
169Table 2
The accuracy and MCC for each genre.
Accuracy
MCC
Qpred
Qobs
Specificity
News
90%
80%
88%
88%
92%
Sport
87%
71%
84%
79%
92%
Movies
87%
66%
77%
72%
93%ROC curve for news, sport, and movie, respectively.
(a)
News ROC curve
(b)
Sport ROC curve
(c)
Movie ROC curveAs shown in Table2, using KLR with same Gaussian kernel shows that the proposed approach could achieve considerable improvement in performance on small to medium size data sets; the average accuracy of our proposed method is 88%, compared to 86% accuracy of the work done in [23] in which the last paper proposed a new technique for improving unconstrained face recognition based on leveraging weakly labeled web videos. KLR has also advantages including that KLR has direct extension to multiclass classification and it can yield probabilistic output without intervention.


## 6. Conclusion

This paper proposed Weighted Kernel Logistic Regression (WKLR) in order to enhance the accuracy and processing time of video classification, which shows easy to implement and good acceptable results regarding to performance. One of the benefits of using WKLR is that it uses algorithms which are less complex for unconstrained optimization methods compared to algorithms used for constrained optimization methods such as SVM. An other benefit is that WKLR takes the advantage of speed of the IRLS and the power of the kernel methods. Future studies may compare this method using different kernels and test the algorithm on more datasets. They may also try to improve the speed of the algorithm. Methods such as the trust region Newton might also be utilized because of their stability and rigorous mathematical derivation.



---

*Source: 653687-2013-10-09.xml*