# A Self-Adaptive Hidden Markov Model for Emotion Classification in Chinese Microblogs

Authors: Li Liu; Dashi Luo; Ming Liu; Jun Zhong; Ye Wei; Letian Sun
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Microblogging is increasingly becoming one of the most popular online social media for people to express ideas and emotions. The amount of socially generated content from this medium is enormous. Text mining techniques have been intensively applied to discover the hidden knowledge and emotions from this huge dataset. In this paper,
we propose a modified version of hidden Markov model (HMM) classifier, called self-adaptive HMM, whose parameters are optimized by Particle Swarm Optimization algorithms. Since manually labeling large-scale dataset is difficult, we also employ the entropy to decide whether a new unlabeled tweet shall be contained in the training dataset after being assigned an emotion using our HMM-based approach. In the experiment, we collected about 200,000 Chinese tweets from Sina Weibo. The results show that theF-score of our approach gets 76% on happiness and fear and 65% on anger, surprise, and sadness. In addition, the self-adaptive HMM classifier outperforms Naive Bayes and Support Vector Machine on recognition of happiness, anger, and sadness.


---

## Body

## 1. Introduction

In the recent years, online social media, such as Microblogging, has generated enormous content on the world wide web. Microblogs are extremely limited in the length of 140 characters. This allows users to easily update a Microblog or receive updates from mobile devices, such as cell phones. Twitter has grown to one of the most popular Microblogging websites and generated hundreds of millions updates per day. Similar to Twitter, Weibo is a Microblogging website in China. In the past few years, it has become an increasingly important source of online social media information with its population of Chinese users growing rapidly to 309 million in 2012 (http://news.xinhuanet.com/english/sci/2013-01/15/c_132104473.htm), as well as with more than 1,000 tweets generated in every second.The emotional states of the users are able to be inferred from these large numbers of short tweets. Emotions in tweets play a significant role in many fields. The stock market and other socioeconomic phenomena could be predicted by using emotion analysis of the Twitter users [1]. Even the gross happiness of a community or a country could be estimated from Twitter [2].Text mining on Chinese tweets is a challenging work. First, word segmentation in Chinese is more difficult than in English since there is no space between Chinese characters and it requires disambiguating segmentation strings. Second, like English Twitter, new words are coming out every day and it is difficult to develop a system to recognize the unknown emotional words. Third, words are ambiguous in various contexts, especially those emotional words. Most of the recent sentiment analysis approaches [3, 4] for Chinese tweets employ emotional word count as main feature and build emotional word dictionary for inference.Considering these issues, we propose a self-adaptive hidden Markov model (HMM) based method to perform the emotion analysis for Chinese tweets. Our method implements a self-adaptive mechanism, which learns the parameters of HMM models and appends new recognized emotional words or sentences into emotional word dictionary, to deal with the issues of the sentiment ambiguities of words and the generation of new words. The main contributions of this paper are shown as follows. (a) More fine grained emotional categories are recognized. We employ the well-known six basic emotional categories defined by Ekman [5]: happiness, sadness, fear, anger, disgust, and surprise, which are more intuitive and useful than traditional sentiment analysis categories: positive, negative, and neutral categories. (b) More useful features, other than word count, are defined. Our method employs the category-based features extracted from the short sentences to train our proposed HMM models. (c) A self-adaptive mechanism is used to test on a real dataset collected from Sina Weibo.The rest of the paper is organized as follows. In Section2, we survey the related works of emotion analysis either in Twitter or in Weibo and provide background on the concepts and methods related to emotion analysis for tweets, especially for Chinese tweets. In Section 3, we describe our proposed self-adaptive HMM-based method. In Section 4, we illustrate the dataset and the experiment setup and present results from our study. We discuss limitations of the method and future work and conclude in Section 5.


## 2. Background

### 2.1. Related Work

Weibo plays a significant role in people’s lives; therefore its opinion mining and emotion analysis become interesting researches. There are a lot of researches on Twitter emotions abroad. Spencer and Uchyigit [6] identified subjective tweets and detected their emotion polarity by using Naive Bayes. In their test using bigrams without part of speech (POS) tags has a high accuracy of 52.31%. In the study carried out by Pak and Paroubek [7], they utilized Naive Bayes to classify tweets into positive, negative, and neutral. It is shown that using the presence of an n-gram as a binary feature yielded the best results. A research [8] has shown that machine learning algorithms (Naive Bayes, Maximum Entropy, and SVM) had high accuracy rate with above 80% when sentiment categories consisted only of positive and negative. In the detection based on Twitter corpus, the authors explored various strategies of selecting features and found that bigram features outperform unigram and POS.However, studies of Chinese Weibo emotions grow just a few years. Zhao et al. [9] used Naive Bayes model to train on emoticon features; they classified Chinese tweets to four categories of emotions (i.e., angry, disgusting, joyful, and sad), with an empirical precision of 64.3%. Yuan and Purver [10] classified Chinese tweets to six emotions which are defined by Ekman as well. In their experiments, character-based features achieved 80% accuracies for “happiness” and “fear” based on the SVM, but there is insufficient analysis to the other four emotions.Our self-adaptive HMM is to recognize more grained emotional categories by category-based features. Besides, the self-adaptive mechanism can continually enhance the recognition accuracy.


### 2.2. Emotion Models

Two models are normally used to represent emotions: the categorical model and dimensional model [11]. The categorical models are based on the assumption that the emotional categories are distinct. Ekman defined six basic emotions: anger, disgust, fear, joy, sadness, and surprise, and found a high agreement of expressions in multiple culture groups in his study. D’Mello et al. [12] proposed five categories (boredom, confusion, delight, flow, and frustration) for describing the affect states in ITS interactions.In the dimensional model, core affects represent emotions in a two- or three-dimensional space. A valence dimension represents positive and negative emotions on different ends of scale. The arousal dimension distinguishes excited states from calm states. Sometimes a third, dominance dimension is used to differentiate if the subject feels in control of the situation or not. For example, Positive Affect and Negative Affect Schedule (PANAS) [13] provides two opposite mood factors (positive and negative) which has been widely used for opinion mining.In this study, the reason we employ Ekman’s emotion model is that the six basic emotions are distinct expressions and contain people daily mood.


### 2.3. Chinese Text Preprocessing

Chinese, a unique language, differing from another language like English, is written without word delimiters. Therefore, its word segmentation is a significant task. Chinese text preprocessing is divided into two steps: word segmentation and stop words removing.To split words, there are some Chinese lexical analysis systems (Institute of Computing Technology, Chinese Lexical Analysis System (ICTCLAS) [14], IKAnalyzer (http://code.google.com/p/ik-analyzer/), HTTPCWS (http://code.google.com/p/httpcws/), Simple Chinese Word Segmentation (SCWS) (http://gc.codehum.com/p/libscws), which are developed to perform word segmentation task). The accuracy rates of those systems are all evaluated above 90 percent.We utilized NLPIR (namely, ICTCLAS 2013) as a word splitter in this study. Its latest lexical database contains new words often appearing in Weibo. It also can recognize bloggers’ nickname. Furthermore, an adaptive word splitter can add new words in its lexical database, which can be applied on our self-adaptive mechanism to update word-emotional vocabulary.For reducing dimension of feature space, the next important step is to remove stop words (quantifier, pronoun, digits, notations, etc., e.g., “hundred,” “we,” “3,” and “*%”). Similarly, Weibo has many unique properties like usernames and usage of links that must be removed.


### 2.4. Features

In the field of document classification, each document is represented as a vector of term. Effective feature extraction is essential to make learning task effective. We adopt four features for our emotion classification model as follows.Mutual Information (MI). MI is a useful information measure, which refers to the correlation between two sets of events. MI reflects the relevance between terms and text categorization on emotions. Two events mutual information of term t and emotion ci is defined as
(1)MIt,ci=log⁡P(t∣ci)P(t).Chi-Square (CHI). CHI is a statistical method to measure the lack of independence between term t and emotion ci. The higher the CHI values, the more dependence between them:
(2)χt,ci=AD-BC2×N(A+B)(C+D)(A+C)(B+D),
where A represents presence of t and membership in ci; B represents presence of t and nonmembership in ci; C represents absence of t and membership in ci; D represents absence of t and nonmembership in ci; N is the total number of tweets.Term Frequency-Inverse Document Frequency (TF-IDF). The main idea of TF-IDF is as follows: if a word or phrase in a tweet appears in a high frequency and rarely appears in other tweets; then it has a good ability to distinguish among emotions:
(3)TF-IDFt,ci=TFi,t×IDFt,
where TFi,t represents the frequency of the term t in the emotion ci; the main idea of IDFt is that if the term t rarely appears in other emotions, IDFt can be an indicator feature for ci. Their definition is
(4)TFi,t=Ni,t∑kNk,t;IDFt=log⁡Nnt+0.01,
where Ni,t means the number of how many times t occurs in emotion ci, N denotes the total number of tweets in the dataset, and nt is the number of tweets where t appears.Expected Cross Entropy (ECE). ECE reflects the probability distribution of the text category on emotions and distances between the probability distribution given term t. Its definition is(5)ECEt,ci=P(ci∣t)log⁡P(ci∣t)Pci,
where P(ci∣t) represents the probability of emotion ci given term t and P(ci) represents the probability of tweets associated with emotion ci.


### 2.5. Classification Methods

Hidden Markov Model (HMM). HMM is used to describe a Markov process with unknown parameters. It is difficult to determine implicit parameters of the process through observable parameters, which are then used to make further analysis.An HMM describes two related discrete-time stochastic processes. The first process pertains to hidden state variables, denoting(S1,S2,…,Su), which emit observed variables with different probabilities, and the second process pertains to observed variables (y1,y2,…,yu).Main parameters of HMM are the transition and emission probabilities [15]:P(Sk=sp∣Sk-1=sq)
(transition probabilities): it means current state is depend on the previous statesq;P(yk∣Sk=sp) (emission probabilities): observation symbol is released by current state sp.In our model, an HMM modelλ(ci) is built for each emotion ci. The features extracted from a tweet T are observed variables, while each hidden state Sk(ci) of λ(ci) is considered as a state associated with the feature yk. If the tweet T gets the highest probability on the model λ(ci), it means that T is associated with emotion ci.


## 2.1. Related Work

Weibo plays a significant role in people’s lives; therefore its opinion mining and emotion analysis become interesting researches. There are a lot of researches on Twitter emotions abroad. Spencer and Uchyigit [6] identified subjective tweets and detected their emotion polarity by using Naive Bayes. In their test using bigrams without part of speech (POS) tags has a high accuracy of 52.31%. In the study carried out by Pak and Paroubek [7], they utilized Naive Bayes to classify tweets into positive, negative, and neutral. It is shown that using the presence of an n-gram as a binary feature yielded the best results. A research [8] has shown that machine learning algorithms (Naive Bayes, Maximum Entropy, and SVM) had high accuracy rate with above 80% when sentiment categories consisted only of positive and negative. In the detection based on Twitter corpus, the authors explored various strategies of selecting features and found that bigram features outperform unigram and POS.However, studies of Chinese Weibo emotions grow just a few years. Zhao et al. [9] used Naive Bayes model to train on emoticon features; they classified Chinese tweets to four categories of emotions (i.e., angry, disgusting, joyful, and sad), with an empirical precision of 64.3%. Yuan and Purver [10] classified Chinese tweets to six emotions which are defined by Ekman as well. In their experiments, character-based features achieved 80% accuracies for “happiness” and “fear” based on the SVM, but there is insufficient analysis to the other four emotions.Our self-adaptive HMM is to recognize more grained emotional categories by category-based features. Besides, the self-adaptive mechanism can continually enhance the recognition accuracy.


## 2.2. Emotion Models

Two models are normally used to represent emotions: the categorical model and dimensional model [11]. The categorical models are based on the assumption that the emotional categories are distinct. Ekman defined six basic emotions: anger, disgust, fear, joy, sadness, and surprise, and found a high agreement of expressions in multiple culture groups in his study. D’Mello et al. [12] proposed five categories (boredom, confusion, delight, flow, and frustration) for describing the affect states in ITS interactions.In the dimensional model, core affects represent emotions in a two- or three-dimensional space. A valence dimension represents positive and negative emotions on different ends of scale. The arousal dimension distinguishes excited states from calm states. Sometimes a third, dominance dimension is used to differentiate if the subject feels in control of the situation or not. For example, Positive Affect and Negative Affect Schedule (PANAS) [13] provides two opposite mood factors (positive and negative) which has been widely used for opinion mining.In this study, the reason we employ Ekman’s emotion model is that the six basic emotions are distinct expressions and contain people daily mood.


## 2.3. Chinese Text Preprocessing

Chinese, a unique language, differing from another language like English, is written without word delimiters. Therefore, its word segmentation is a significant task. Chinese text preprocessing is divided into two steps: word segmentation and stop words removing.To split words, there are some Chinese lexical analysis systems (Institute of Computing Technology, Chinese Lexical Analysis System (ICTCLAS) [14], IKAnalyzer (http://code.google.com/p/ik-analyzer/), HTTPCWS (http://code.google.com/p/httpcws/), Simple Chinese Word Segmentation (SCWS) (http://gc.codehum.com/p/libscws), which are developed to perform word segmentation task). The accuracy rates of those systems are all evaluated above 90 percent.We utilized NLPIR (namely, ICTCLAS 2013) as a word splitter in this study. Its latest lexical database contains new words often appearing in Weibo. It also can recognize bloggers’ nickname. Furthermore, an adaptive word splitter can add new words in its lexical database, which can be applied on our self-adaptive mechanism to update word-emotional vocabulary.For reducing dimension of feature space, the next important step is to remove stop words (quantifier, pronoun, digits, notations, etc., e.g., “hundred,” “we,” “3,” and “*%”). Similarly, Weibo has many unique properties like usernames and usage of links that must be removed.


## 2.4. Features

In the field of document classification, each document is represented as a vector of term. Effective feature extraction is essential to make learning task effective. We adopt four features for our emotion classification model as follows.Mutual Information (MI). MI is a useful information measure, which refers to the correlation between two sets of events. MI reflects the relevance between terms and text categorization on emotions. Two events mutual information of term t and emotion ci is defined as
(1)MIt,ci=log⁡P(t∣ci)P(t).Chi-Square (CHI). CHI is a statistical method to measure the lack of independence between term t and emotion ci. The higher the CHI values, the more dependence between them:
(2)χt,ci=AD-BC2×N(A+B)(C+D)(A+C)(B+D),
where A represents presence of t and membership in ci; B represents presence of t and nonmembership in ci; C represents absence of t and membership in ci; D represents absence of t and nonmembership in ci; N is the total number of tweets.Term Frequency-Inverse Document Frequency (TF-IDF). The main idea of TF-IDF is as follows: if a word or phrase in a tweet appears in a high frequency and rarely appears in other tweets; then it has a good ability to distinguish among emotions:
(3)TF-IDFt,ci=TFi,t×IDFt,
where TFi,t represents the frequency of the term t in the emotion ci; the main idea of IDFt is that if the term t rarely appears in other emotions, IDFt can be an indicator feature for ci. Their definition is
(4)TFi,t=Ni,t∑kNk,t;IDFt=log⁡Nnt+0.01,
where Ni,t means the number of how many times t occurs in emotion ci, N denotes the total number of tweets in the dataset, and nt is the number of tweets where t appears.Expected Cross Entropy (ECE). ECE reflects the probability distribution of the text category on emotions and distances between the probability distribution given term t. Its definition is(5)ECEt,ci=P(ci∣t)log⁡P(ci∣t)Pci,
where P(ci∣t) represents the probability of emotion ci given term t and P(ci) represents the probability of tweets associated with emotion ci.


## 2.5. Classification Methods

Hidden Markov Model (HMM). HMM is used to describe a Markov process with unknown parameters. It is difficult to determine implicit parameters of the process through observable parameters, which are then used to make further analysis.An HMM describes two related discrete-time stochastic processes. The first process pertains to hidden state variables, denoting(S1,S2,…,Su), which emit observed variables with different probabilities, and the second process pertains to observed variables (y1,y2,…,yu).Main parameters of HMM are the transition and emission probabilities [15]:P(Sk=sp∣Sk-1=sq)
(transition probabilities): it means current state is depend on the previous statesq;P(yk∣Sk=sp) (emission probabilities): observation symbol is released by current state sp.In our model, an HMM modelλ(ci) is built for each emotion ci. The features extracted from a tweet T are observed variables, while each hidden state Sk(ci) of λ(ci) is considered as a state associated with the feature yk. If the tweet T gets the highest probability on the model λ(ci), it means that T is associated with emotion ci.


## 3. Method

### 3.1. Features as Observed Variables

Feature extraction methods fall into two main categories: category-based extraction and global-based extraction. The features exacted by the latter methods can reflect the importance of words in global corpus but cannot be used to distinguish the differences between emotions. Therefore, we adopt category-based feature extraction methods in our models. All the selected features we introduced in Section2.4 are category-based extracted features.Suppose a set ofu features extraction methods {F1,F2,…,Fu}. A tweet T is first divided into n terms (w1,w2,…,wn). Let xjk be the kth feature of the word wj extracted by the method Fk. Then, an intermediate n×u matrix of term-level features is obtained for calculating the tweet-level feature vector. For each emotion ci(1≤i≤6), the tweet-level feature vector of the tweet T can be calculated as follows:
(6)w1w2⋮wn⟶x11x12⋯x1ux21x22⋯x2u⋮⋮⋱⋮xn1xn2⋯xnu⟶y1y2⋯yuci,
where yk=∑j=1nxjk/n, (1≤k≤u). Actually, yk is a mean value of kth features over all the words.In our experiment, a tweet is mapped into a four-dimensional vector using the four features: MI, CHI, TF-IDF and ECE. For example, the tweet “How lovely!” is divided into two terms: “how” and “lovely” in Chinese. The features of the terms on happiness and anger are calculated, respectively, as listed in Table1.Table 1
The features of the terms “how” and “lovely” on happiness and anger, respectively.
Term
Emotions
MI
CHI
TF-IDF
ECE
How
Happiness
0.0014
0.0147
0.00088
0.00059
Anger
−0.00056
0.00063
0.00023
−0.000065
Lovely
Happiness
0.0030
0.0067
0.0095
0.0027
Anger
0
0.00014
0
0Therefore, the tweet’s feature vector is[0.0022,0.0107,0.0052,0.0016] in happiness and [-2.8E-4,3.9E-4,1.1E-4,-3.2E-5] in anger.


### 3.2. HMM-Based Emotional Classification Model

In our case each hidden state is supposed to emit a value, and the whole model generates the sequence of values that constitutes the tweet’s feature vector. States are considered to be a set of values that represent the best emotional category. There is a one-to-one mapping between HMM states and tweet features, which requires hidden states transition to be stationary and the states to begin at the first states1. When the classifier works, transition probabilities indicate features of test tweets being drawn closer to the emotion, which is given as follows:
(7)P(Sk=sp∣Sk-1=sq)=1,(p=q+1)0,p≠q+1.
The emission probability P(yk∣Sk) also can be calculated by the known state Sk, feature yk, and training data. Our calculation method is given at the end of this chapter.Algorithm1 depicts the procedure of building an HMM model λ(ci) for emotion ci. The tweet-level feature vector is denoted as y1y2⋯yuci.Algorithm 1:
λ
(
c
i
) model algorithm.
Input: feature vector y1y2…yuci
Output: probability  Py1y2…yuci∣λci
for  k=1  to  u  do
CalculateP(yk∣Sk)ci
end for
CalculatePy1y2…yuci∣λci  using forward algorithm.We construct an HMM model for each of the six emotions. When a new tweet arrives, the probabilities of the tweet are calculated on the six models, respectively. The tweet is labeled with the emotion whose model is associated with the maximum probability.A Strategy of Calculating
P
(
y
k
∣
S
k
)
(
c
i
). To find a way to calculate the P(yk∣Sk) of emotion ci, denoted as P(yk∣Sk)(ci), we attempt to use Jaccard similarity measure [16] to test correlation between value yk and state Sk:
(8)Pyk∣Skci=Jyk∣Skci=M11M11+M10+M01,
where M11 represents the number of tweets, which contains both yk and Sk in ci; M01 represents the number of tweets, which contains only yk in ci; and M10 represents the number of tweets, which contains only Sk in ci. In order to check whether emotion ci associates to observation yk or state Sk, we introduce an associated factor, denoted by δk. Let yk′ be the feature extracted from training data. The following describes the association:
(9)yk′-yk≤δkoryk′-Sk≤δk.
We assume that observation yk or state Sk is associated with ci if the above inequality is met.


### 3.3. Self-Adaptive Mechanism

#### 3.3.1. Parameters Computed by PSO

To build an excellent HMM classifier, an important problem we have to solve is to find optimized sequences of HMM states. There are a variety of strategies we can utilize for optimizing state parameters.Particle Swarm Optimization (PSO) algorithm [17] is a population based stochastic optimization. In our algorithm, each particle represents a candidate solution of an HMM parameter. These particles move around in the search-space. Through particle’s local best known position, it is guided toward the best known positions. Eventually this iterative method can find best parameters. Compared to Genetic Algorithm [18], PSO has simple rules and more powerful ability of global optimization that has been good applications in our study:
av[]=W×v[]+c1×r×(pbest[]-present[])+c2×R×(gbest[]-present[])bpresent[]=present[]+v[],
where [] indicates that its corresponding variable is a vector. The variables r and R are random numbers between [0,1]. pbest[] records the individual extremes and gbest[] records the global extremes. The constant W is the inertia weight, and c1 and c2 present acceleration constants. Moreover, a updates velocities of particles according to previous velocity and the distance to the best particle. The equation b updates the particles’ position present[] according to its previous position and current velocity.PSO Parameter Settings. Different PSO parameters may have a large impact on optimization performance. Following are guidelines to help us select PSO parameters [19, 20].vmax⁡: decide the granularity of searching space. We set it through values of training data.W: keep the particles motion inertia. We set the inertia weight at 0.8.c1, c2: represent accelerated weight of pushing each particle to pbest[] and gbest[]. We set both weights to the value of 2.Fitness Function. We use fitness function to find two kinds of parameters in HMM models, that is, the optimized associated factor δk and the Sk(ci), which is the kth hidden states of the HMM model λ(ci). Accordingly, the fitness function can be defined as follows:
(10)fitnessδk,Skc1,…,Skc6=F1-Measure,(1≤k≤u),
where F1-Measure is the metrics (in Section 4.3) of classifiers’ accuracy. There are a total number of 7×u parameters that need to be searched. Since finding the whole set of parameters is time intensive by PSO, we divide the set of parameters into u independent parts. Seven parameters (δk,Sk(c1),…,Sk(c6)), (1≤k≤u), are learned for each part according to the fitness function.


#### 3.3.2. Feedback

Since it is time-consuming and expensive to manually label all the tweets, we introduce a feedback method that can automatically decide whether an unlabeled tweet shall be chosen and contained in a training data pool after it is assigned with an emotion by our HMM model. Unlike the strategy (Lewis and Catlett [21], Scheffer et al. [22]), which merely concerns the assigned emotions, a suitable strategy is to compute the entropy of a tweet T to identify the discrimination of emotions; that is, an emotion is more discriminating than all other emotions on the tweet T. Entropy is an information-theoretic measure and its formula is given as follows:
(11)ϕT=-∑i‍P(ci∣T)log⁡P(ci∣T),
where P(ci∣T) means the probability of the tweet T recognized as emotion ci. The less the ϕ(T), the more the certainty about the tweet T on the emotion ci. The algorithm of pool-based feedback is shown in Algorithm 2 to decide whether a tweet should be contained in the training dataset.Algorithm 2:Algorithm of pool-based feedback.
Input: training data pool  L, test data pool U, query strategy ϕ(•), query batch size B
repeat
for  i=1  to  |C|  do
Optimizedλ(ci)  by using current  L  and PSO algorithm;
end for
for  b=1  to  B  do
Tb*=arg⁡max⁡T∈Uϕ(T);
MoveTb* from U to L;
end for
until some stopping criterion.


## 3.1. Features as Observed Variables

Feature extraction methods fall into two main categories: category-based extraction and global-based extraction. The features exacted by the latter methods can reflect the importance of words in global corpus but cannot be used to distinguish the differences between emotions. Therefore, we adopt category-based feature extraction methods in our models. All the selected features we introduced in Section2.4 are category-based extracted features.Suppose a set ofu features extraction methods {F1,F2,…,Fu}. A tweet T is first divided into n terms (w1,w2,…,wn). Let xjk be the kth feature of the word wj extracted by the method Fk. Then, an intermediate n×u matrix of term-level features is obtained for calculating the tweet-level feature vector. For each emotion ci(1≤i≤6), the tweet-level feature vector of the tweet T can be calculated as follows:
(6)w1w2⋮wn⟶x11x12⋯x1ux21x22⋯x2u⋮⋮⋱⋮xn1xn2⋯xnu⟶y1y2⋯yuci,
where yk=∑j=1nxjk/n, (1≤k≤u). Actually, yk is a mean value of kth features over all the words.In our experiment, a tweet is mapped into a four-dimensional vector using the four features: MI, CHI, TF-IDF and ECE. For example, the tweet “How lovely!” is divided into two terms: “how” and “lovely” in Chinese. The features of the terms on happiness and anger are calculated, respectively, as listed in Table1.Table 1
The features of the terms “how” and “lovely” on happiness and anger, respectively.
Term
Emotions
MI
CHI
TF-IDF
ECE
How
Happiness
0.0014
0.0147
0.00088
0.00059
Anger
−0.00056
0.00063
0.00023
−0.000065
Lovely
Happiness
0.0030
0.0067
0.0095
0.0027
Anger
0
0.00014
0
0Therefore, the tweet’s feature vector is[0.0022,0.0107,0.0052,0.0016] in happiness and [-2.8E-4,3.9E-4,1.1E-4,-3.2E-5] in anger.


## 3.2. HMM-Based Emotional Classification Model

In our case each hidden state is supposed to emit a value, and the whole model generates the sequence of values that constitutes the tweet’s feature vector. States are considered to be a set of values that represent the best emotional category. There is a one-to-one mapping between HMM states and tweet features, which requires hidden states transition to be stationary and the states to begin at the first states1. When the classifier works, transition probabilities indicate features of test tweets being drawn closer to the emotion, which is given as follows:
(7)P(Sk=sp∣Sk-1=sq)=1,(p=q+1)0,p≠q+1.
The emission probability P(yk∣Sk) also can be calculated by the known state Sk, feature yk, and training data. Our calculation method is given at the end of this chapter.Algorithm1 depicts the procedure of building an HMM model λ(ci) for emotion ci. The tweet-level feature vector is denoted as y1y2⋯yuci.Algorithm 1:
λ
(
c
i
) model algorithm.
Input: feature vector y1y2…yuci
Output: probability  Py1y2…yuci∣λci
for  k=1  to  u  do
CalculateP(yk∣Sk)ci
end for
CalculatePy1y2…yuci∣λci  using forward algorithm.We construct an HMM model for each of the six emotions. When a new tweet arrives, the probabilities of the tweet are calculated on the six models, respectively. The tweet is labeled with the emotion whose model is associated with the maximum probability.A Strategy of Calculating
P
(
y
k
∣
S
k
)
(
c
i
). To find a way to calculate the P(yk∣Sk) of emotion ci, denoted as P(yk∣Sk)(ci), we attempt to use Jaccard similarity measure [16] to test correlation between value yk and state Sk:
(8)Pyk∣Skci=Jyk∣Skci=M11M11+M10+M01,
where M11 represents the number of tweets, which contains both yk and Sk in ci; M01 represents the number of tweets, which contains only yk in ci; and M10 represents the number of tweets, which contains only Sk in ci. In order to check whether emotion ci associates to observation yk or state Sk, we introduce an associated factor, denoted by δk. Let yk′ be the feature extracted from training data. The following describes the association:
(9)yk′-yk≤δkoryk′-Sk≤δk.
We assume that observation yk or state Sk is associated with ci if the above inequality is met.


## 3.3. Self-Adaptive Mechanism

### 3.3.1. Parameters Computed by PSO

To build an excellent HMM classifier, an important problem we have to solve is to find optimized sequences of HMM states. There are a variety of strategies we can utilize for optimizing state parameters.Particle Swarm Optimization (PSO) algorithm [17] is a population based stochastic optimization. In our algorithm, each particle represents a candidate solution of an HMM parameter. These particles move around in the search-space. Through particle’s local best known position, it is guided toward the best known positions. Eventually this iterative method can find best parameters. Compared to Genetic Algorithm [18], PSO has simple rules and more powerful ability of global optimization that has been good applications in our study:
av[]=W×v[]+c1×r×(pbest[]-present[])+c2×R×(gbest[]-present[])bpresent[]=present[]+v[],
where [] indicates that its corresponding variable is a vector. The variables r and R are random numbers between [0,1]. pbest[] records the individual extremes and gbest[] records the global extremes. The constant W is the inertia weight, and c1 and c2 present acceleration constants. Moreover, a updates velocities of particles according to previous velocity and the distance to the best particle. The equation b updates the particles’ position present[] according to its previous position and current velocity.PSO Parameter Settings. Different PSO parameters may have a large impact on optimization performance. Following are guidelines to help us select PSO parameters [19, 20].vmax⁡: decide the granularity of searching space. We set it through values of training data.W: keep the particles motion inertia. We set the inertia weight at 0.8.c1, c2: represent accelerated weight of pushing each particle to pbest[] and gbest[]. We set both weights to the value of 2.Fitness Function. We use fitness function to find two kinds of parameters in HMM models, that is, the optimized associated factor δk and the Sk(ci), which is the kth hidden states of the HMM model λ(ci). Accordingly, the fitness function can be defined as follows:
(10)fitnessδk,Skc1,…,Skc6=F1-Measure,(1≤k≤u),
where F1-Measure is the metrics (in Section 4.3) of classifiers’ accuracy. There are a total number of 7×u parameters that need to be searched. Since finding the whole set of parameters is time intensive by PSO, we divide the set of parameters into u independent parts. Seven parameters (δk,Sk(c1),…,Sk(c6)), (1≤k≤u), are learned for each part according to the fitness function.


### 3.3.2. Feedback

Since it is time-consuming and expensive to manually label all the tweets, we introduce a feedback method that can automatically decide whether an unlabeled tweet shall be chosen and contained in a training data pool after it is assigned with an emotion by our HMM model. Unlike the strategy (Lewis and Catlett [21], Scheffer et al. [22]), which merely concerns the assigned emotions, a suitable strategy is to compute the entropy of a tweet T to identify the discrimination of emotions; that is, an emotion is more discriminating than all other emotions on the tweet T. Entropy is an information-theoretic measure and its formula is given as follows:
(11)ϕT=-∑i‍P(ci∣T)log⁡P(ci∣T),
where P(ci∣T) means the probability of the tweet T recognized as emotion ci. The less the ϕ(T), the more the certainty about the tweet T on the emotion ci. The algorithm of pool-based feedback is shown in Algorithm 2 to decide whether a tweet should be contained in the training dataset.Algorithm 2:Algorithm of pool-based feedback.
Input: training data pool  L, test data pool U, query strategy ϕ(•), query batch size B
repeat
for  i=1  to  |C|  do
Optimizedλ(ci)  by using current  L  and PSO algorithm;
end for
for  b=1  to  B  do
Tb*=arg⁡max⁡T∈Uϕ(T);
MoveTb* from U to L;
end for
until some stopping criterion.


## 3.3.1. Parameters Computed by PSO

To build an excellent HMM classifier, an important problem we have to solve is to find optimized sequences of HMM states. There are a variety of strategies we can utilize for optimizing state parameters.Particle Swarm Optimization (PSO) algorithm [17] is a population based stochastic optimization. In our algorithm, each particle represents a candidate solution of an HMM parameter. These particles move around in the search-space. Through particle’s local best known position, it is guided toward the best known positions. Eventually this iterative method can find best parameters. Compared to Genetic Algorithm [18], PSO has simple rules and more powerful ability of global optimization that has been good applications in our study:
av[]=W×v[]+c1×r×(pbest[]-present[])+c2×R×(gbest[]-present[])bpresent[]=present[]+v[],
where [] indicates that its corresponding variable is a vector. The variables r and R are random numbers between [0,1]. pbest[] records the individual extremes and gbest[] records the global extremes. The constant W is the inertia weight, and c1 and c2 present acceleration constants. Moreover, a updates velocities of particles according to previous velocity and the distance to the best particle. The equation b updates the particles’ position present[] according to its previous position and current velocity.PSO Parameter Settings. Different PSO parameters may have a large impact on optimization performance. Following are guidelines to help us select PSO parameters [19, 20].vmax⁡: decide the granularity of searching space. We set it through values of training data.W: keep the particles motion inertia. We set the inertia weight at 0.8.c1, c2: represent accelerated weight of pushing each particle to pbest[] and gbest[]. We set both weights to the value of 2.Fitness Function. We use fitness function to find two kinds of parameters in HMM models, that is, the optimized associated factor δk and the Sk(ci), which is the kth hidden states of the HMM model λ(ci). Accordingly, the fitness function can be defined as follows:
(10)fitnessδk,Skc1,…,Skc6=F1-Measure,(1≤k≤u),
where F1-Measure is the metrics (in Section 4.3) of classifiers’ accuracy. There are a total number of 7×u parameters that need to be searched. Since finding the whole set of parameters is time intensive by PSO, we divide the set of parameters into u independent parts. Seven parameters (δk,Sk(c1),…,Sk(c6)), (1≤k≤u), are learned for each part according to the fitness function.


## 3.3.2. Feedback

Since it is time-consuming and expensive to manually label all the tweets, we introduce a feedback method that can automatically decide whether an unlabeled tweet shall be chosen and contained in a training data pool after it is assigned with an emotion by our HMM model. Unlike the strategy (Lewis and Catlett [21], Scheffer et al. [22]), which merely concerns the assigned emotions, a suitable strategy is to compute the entropy of a tweet T to identify the discrimination of emotions; that is, an emotion is more discriminating than all other emotions on the tweet T. Entropy is an information-theoretic measure and its formula is given as follows:
(11)ϕT=-∑i‍P(ci∣T)log⁡P(ci∣T),
where P(ci∣T) means the probability of the tweet T recognized as emotion ci. The less the ϕ(T), the more the certainty about the tweet T on the emotion ci. The algorithm of pool-based feedback is shown in Algorithm 2 to decide whether a tweet should be contained in the training dataset.Algorithm 2:Algorithm of pool-based feedback.
Input: training data pool  L, test data pool U, query strategy ϕ(•), query batch size B
repeat
for  i=1  to  |C|  do
Optimizedλ(ci)  by using current  L  and PSO algorithm;
end for
for  b=1  to  B  do
Tb*=arg⁡max⁡T∈Uϕ(T);
MoveTb* from U to L;
end for
until some stopping criterion.


## 4. Experiments

### 4.1. Dataset

Since there are no public datasets of Chinese tweets associated with emotions, many studies employ emoticons to label tweets [7, 8, 10]. However, only a small percentage of Chinese users post tweets with emoticons. Besides, several emoticons cannot find their corresponding emotions. Hence, we build our own dataset as follows.(i)
About 200,000 tweets were collected through Sina API.(ii)
For each emotion, more than twelve seed terms were chosen for term-level feature extraction. We refer interested readers to Aman’s annotation scheme [23] for seed term selection. For instance, a set of seed terms on happiness may contain “enjoy” and “pleased.”(iii)
Manually screening. Not all tweets are associated with a corresponding emotion. We asked ten students in computer science to choose good indicator tweet for the six emotions.Notice that duplicate tweets are removed. Eventually, we selected 271, 159, 251, 229, 118, and 194 tweets on happiness, anger, surprise, fear, sadness, and disgust, respectively.


### 4.2. Setup

The procedure of emotion recognition for a tweet is shown as follows:(a)
preprocess dataset;(b)
build emotion lexicons; each lexicon contains a feature vector of terms extracted by feature extraction methods;(c)
calculate feature vectors of the whole dataset;(d)
optimize hidden states of eachλ(ci) by PSO;(e)
for eachλci(ci∈C), calculate feature vector y1y2⋯yuci of T in emotion ci and obtain the output value P(y1y2⋯yuci∣λ(ci)) through model λ(ci);(f)
returnc*=argmaxci∈|C|{P(y1y2⋯yu∣λ(ci))}.To evaluate the performance of each of the HMM models, we randomly select several hand-annotated tweets. The test dataset contains 30 tweets for each emotion. Each test run is executed five times. We use the average results for our evaluation.


### 4.3. Evaluation Metrics

Precision, recall, andF-measure are the most commonly used evaluation methods for text classification tasks [7]. We employ the three metrics in our experiment. For each emotion ci, precision and recall are defined as
(12)Precison=aa+c;Recall=aa+b,
where a represents the number of tweets that are correctly recognized; b represents the number of tweets that are falsely recognized as ci; c represents the number of tweets that are actually associated with ci, but are recognized as another emotion.To balance precision and recall rates,F1 is defined as
(13)F1=2×Precision×RecallPrecision+Recall.


### 4.4. Evaluation

#### 4.4.1. Compare with Another Classifier

We compared our approach with two well-known classifiers, that is, Naive Bayes and Support Vector Machine (SVM) [24]. They are often used for sentiment classification in literatures because of their easiness of implementation.As shown in Figure1, our HMM-based approach outperforms Naive Bayes and SVM on happiness, anger, and sadness. The performances produced by all these classifiers have less difference on the other three emotions.Figure 1
Performance comparison of three approaches on the six emotions, respectively. Thex-axis means the number of test runs.The results also show that, for the emotions of happiness, surprise, and fear, all the three classifiers get good performance. TheF-measure is greater than 65%. Furthermore, the F-measure exceeds 78% on fear. None of the three classifiers recognize disgust accurately.


#### 4.4.2. The Comparison of Six Emotions

Figure2 shows the classification results of the six emotions using our HMM-based approach. We find that our approach gets the best accuracy over 76% on happiness and fear. It also gets a good performance on anger, surprise, and sadness with an average accuracy of 65%.Figure 2
The accuracy of our HMM-based approach on the six emotions. Thex-axis means the number of test runs.


#### 4.4.3. Analysis of HMM Results

We also attempt to analyze the reasons for false recognition on emotions. Twitters with specific characteristics may lead to false recognition using our HMM-base approach.(i)
Some twitters may contain multiple emotions. For example, “Wow, I’m so smart!” (original sentence is in Chinese) contains both happiness and surprise. Multiple emotional tweets may cause false recognition. It also explains why our approach gets lowF-score on disgust, which is often falsely recognized as anger.(ii)
A number of tweets contain new words that can not be recognized.In addition, puns and polysemous words are significant factors but rather difficult to be recognized. According to these reasons, our HMM-based approach can be improved concerning the above characteristics in our future experiments.


## 4.1. Dataset

Since there are no public datasets of Chinese tweets associated with emotions, many studies employ emoticons to label tweets [7, 8, 10]. However, only a small percentage of Chinese users post tweets with emoticons. Besides, several emoticons cannot find their corresponding emotions. Hence, we build our own dataset as follows.(i)
About 200,000 tweets were collected through Sina API.(ii)
For each emotion, more than twelve seed terms were chosen for term-level feature extraction. We refer interested readers to Aman’s annotation scheme [23] for seed term selection. For instance, a set of seed terms on happiness may contain “enjoy” and “pleased.”(iii)
Manually screening. Not all tweets are associated with a corresponding emotion. We asked ten students in computer science to choose good indicator tweet for the six emotions.Notice that duplicate tweets are removed. Eventually, we selected 271, 159, 251, 229, 118, and 194 tweets on happiness, anger, surprise, fear, sadness, and disgust, respectively.


## 4.2. Setup

The procedure of emotion recognition for a tweet is shown as follows:(a)
preprocess dataset;(b)
build emotion lexicons; each lexicon contains a feature vector of terms extracted by feature extraction methods;(c)
calculate feature vectors of the whole dataset;(d)
optimize hidden states of eachλ(ci) by PSO;(e)
for eachλci(ci∈C), calculate feature vector y1y2⋯yuci of T in emotion ci and obtain the output value P(y1y2⋯yuci∣λ(ci)) through model λ(ci);(f)
returnc*=argmaxci∈|C|{P(y1y2⋯yu∣λ(ci))}.To evaluate the performance of each of the HMM models, we randomly select several hand-annotated tweets. The test dataset contains 30 tweets for each emotion. Each test run is executed five times. We use the average results for our evaluation.


## 4.3. Evaluation Metrics

Precision, recall, andF-measure are the most commonly used evaluation methods for text classification tasks [7]. We employ the three metrics in our experiment. For each emotion ci, precision and recall are defined as
(12)Precison=aa+c;Recall=aa+b,
where a represents the number of tweets that are correctly recognized; b represents the number of tweets that are falsely recognized as ci; c represents the number of tweets that are actually associated with ci, but are recognized as another emotion.To balance precision and recall rates,F1 is defined as
(13)F1=2×Precision×RecallPrecision+Recall.


## 4.4. Evaluation

### 4.4.1. Compare with Another Classifier

We compared our approach with two well-known classifiers, that is, Naive Bayes and Support Vector Machine (SVM) [24]. They are often used for sentiment classification in literatures because of their easiness of implementation.As shown in Figure1, our HMM-based approach outperforms Naive Bayes and SVM on happiness, anger, and sadness. The performances produced by all these classifiers have less difference on the other three emotions.Figure 1
Performance comparison of three approaches on the six emotions, respectively. Thex-axis means the number of test runs.The results also show that, for the emotions of happiness, surprise, and fear, all the three classifiers get good performance. TheF-measure is greater than 65%. Furthermore, the F-measure exceeds 78% on fear. None of the three classifiers recognize disgust accurately.


### 4.4.2. The Comparison of Six Emotions

Figure2 shows the classification results of the six emotions using our HMM-based approach. We find that our approach gets the best accuracy over 76% on happiness and fear. It also gets a good performance on anger, surprise, and sadness with an average accuracy of 65%.Figure 2
The accuracy of our HMM-based approach on the six emotions. Thex-axis means the number of test runs.


### 4.4.3. Analysis of HMM Results

We also attempt to analyze the reasons for false recognition on emotions. Twitters with specific characteristics may lead to false recognition using our HMM-base approach.(i)
Some twitters may contain multiple emotions. For example, “Wow, I’m so smart!” (original sentence is in Chinese) contains both happiness and surprise. Multiple emotional tweets may cause false recognition. It also explains why our approach gets lowF-score on disgust, which is often falsely recognized as anger.(ii)
A number of tweets contain new words that can not be recognized.In addition, puns and polysemous words are significant factors but rather difficult to be recognized. According to these reasons, our HMM-based approach can be improved concerning the above characteristics in our future experiments.


## 4.4.1. Compare with Another Classifier

We compared our approach with two well-known classifiers, that is, Naive Bayes and Support Vector Machine (SVM) [24]. They are often used for sentiment classification in literatures because of their easiness of implementation.As shown in Figure1, our HMM-based approach outperforms Naive Bayes and SVM on happiness, anger, and sadness. The performances produced by all these classifiers have less difference on the other three emotions.Figure 1
Performance comparison of three approaches on the six emotions, respectively. Thex-axis means the number of test runs.The results also show that, for the emotions of happiness, surprise, and fear, all the three classifiers get good performance. TheF-measure is greater than 65%. Furthermore, the F-measure exceeds 78% on fear. None of the three classifiers recognize disgust accurately.


## 4.4.2. The Comparison of Six Emotions

Figure2 shows the classification results of the six emotions using our HMM-based approach. We find that our approach gets the best accuracy over 76% on happiness and fear. It also gets a good performance on anger, surprise, and sadness with an average accuracy of 65%.Figure 2
The accuracy of our HMM-based approach on the six emotions. Thex-axis means the number of test runs.


## 4.4.3. Analysis of HMM Results

We also attempt to analyze the reasons for false recognition on emotions. Twitters with specific characteristics may lead to false recognition using our HMM-base approach.(i)
Some twitters may contain multiple emotions. For example, “Wow, I’m so smart!” (original sentence is in Chinese) contains both happiness and surprise. Multiple emotional tweets may cause false recognition. It also explains why our approach gets lowF-score on disgust, which is often falsely recognized as anger.(ii)
A number of tweets contain new words that can not be recognized.In addition, puns and polysemous words are significant factors but rather difficult to be recognized. According to these reasons, our HMM-based approach can be improved concerning the above characteristics in our future experiments.


## 5. Conclusion

In this paper, we present an approach to extract features using the four methods, that is, MI, TF-IDF, CHI, and ECE. Our classifier is based on HMM, in which hidden states are found by PSO algorithm. Since manually labeling large-scale dataset is difficult, we employ the entropy to decide whether a new unlabeled tweet shall be contained in the training dataset after being assigned an emotion using our HMM-based approach. The experimental results show that HMM outperforms SVM and NB, especially on happiness, anger, and sadness. In terms of the recognition precisions on the six emotions, HMM gets better performance on happiness and fear than on anger, surprise, and sadness.In the future, we will optimize HMM to accurately recognize twitters associated with other emotions and automatically add new words for emotional seed terms selection. Moreover, self-adaptive mechanism will be implemented in our HMM model.



---

*Source: 987189-2015-10-04.xml*