Self-Adaptive Hierarchical Sentence Model
Han Zhao, Zhengdong Lu and Pascal Poupart

han.zhao@uwaterloo.ca
July 22, 2015

1 / 45

Outline

Background
Machine Learning
Representation Learning

AdaSentMotivation
Architecture
Learning
Experiments

2 / 45

Background
Machine Learning – Definition

Definition
A computer program is said to learn from experience E withrespect to some class of tasks T and performance measure P,
if its performance at tasks in T , as measured by P, improves
with experience E .
— Tom M. Mitchell3 / 45

Background
Machine Learning – Definition

DefinitionA computer program is said to learn from experience E withrespect to some class of tasks T and performance measure P,
if its performance at tasks in T , as measured by P, improves
with experience E .
— Tom M. Mitchell
I E – data

4 / 45

Background
Machine Learning – Definition

Definition
A computer program is said to learn from experience E withrespect to some class of tasks T and performance measure P,
if its performance at tasks in T , as measured by P, improves
with experience E .
— Tom M. Mitchell
I E – data
I T – task of interests

5 / 45Background
Machine Learning – Definition

Definition
A computer program is said to learn from experience E withrespect to some class of tasks T and performance measure P,
if its performance at tasks in T , as measured by P, improves
with experience E .
— Tom M. Mitchell
I E – data
I T – task of interests
I P – objective function

6 / 45

Background
Machine Learning – Application

7 / 45

Background
Machine Learning – Pipeline

Slide courtesy of Kyunghyun Cho
8 / 45

Background
Machine Learning – Components

Machine Learning ≈ Representation + Objective + Optimization9 / 45

Background
Machine Learning – Components

Machine Learning ≈ Representation + Objective + Optimization

10 / 45

Background
Deep Learning

11 / 45

Background
Deep Learning – Application
I Object Recognition (Krizhevsky et al. 2012)
I Speech Recognition (Graves et al. 2013)
I Neural Machine Translation (Sutskever et al. 2014)
I Face Recognition (Schroff et al. 2015)
I Deep Reinforcement Learning (Mnih et al. 2013)
I Image Caption Generation (Vinyals et al. 2014)
I Text Matching (Hu et al. 2014)
I Text Parsing (Chen et al. 2014)

And etc.

Items highlighted in blue happen at Google.
12 / 45

Background
Deep Learning – Representation Learning

Deep Learning: Learning multiple levels of representation directlyfrom massive data

Slide courtesy of Kyunghyun Cho

13 / 45

Background
Deep Learning – Representation Learning

Deep Learning: Learning multiple levels of representation directlyfrom massive data

ail = σ(zil ),zil =X
jwij ajl−1 ,σ(t) =1
1 + exp−t
14 / 45

Background
Deep Learning – Natural Language Processing

15 / 45

Background
Deep Learning – Natural Language Processing

16 / 45

Background
Deep Learning – Word Embedding

Traditional representation of words: One-hot representation.
cat = [0, 0, 0, 0, 0, 1, 0, 0, . . .]dog = [0, 1, 0, 0, 0, 0, 0, 0, . . .]17 / 45

Background
Deep Learning – Word Embedding

Traditional representation of words: One-hot representation.
cat = [0, 0, 0, 0, 0, 1, 0, 0, . . .]dog = [0, 1, 0, 0, 0, 0, 0, 0, . . .]Pros:
I Simple, intuitive
I Basis of bag-of-words model for document representation

Cons:I High-dimensional
I No semantic meaning

18 / 45

Background
Deep Learning – Word Embedding

Word2Vec (Minkolov et al)Distributed word representation: Unsupervised technique to map
each word into a dense and real-valued low dimensional vector.

19 / 45

Background
Deep Learning – Word Embedding

Word2Vec (Minkolov et al)Distributed word representation: Unsupervised technique to map
each word into a dense and real-valued low dimensional vector.

w (China)−w (Beijing) ≈ w (Russia)−w (Moscow) ≈ w (Italy)−w (Rome)
20 / 45

BackgroundDeep Learning – Sentence Modeling

Paragraph Vector (Le et al)Distributed paragraph representation: Unsupervised technique tomap each paragraph into a dense and real-valued low dimensionalvector.

21 / 45

Background
Deep Learning – Sentence ModelingPhrase/Sentence/Document Modeling
I Recursive auto-encoder/Matrix-vector recursive neuralnetwork (Socher et al. 2011, 2012)
I Convolutional neural network (Kim 2014)
I Dynamic convolutional neural network (Kalchbrenner et al.

2014)
I Recurrent neural network/Bi-directional recurrent neuralnetwork (Lai et al. 2015)
I Gated recursive convolutional neural network (Cho et al.

2014)

22 / 45

AdaSent
Motivation

AdaSent: Self-Adaptive Hierarchical Sentence Model
I Is vector representation with fixed-length enough to represent

different granularities of phrases/sentences/documents ?

23 / 45

AdaSent
Motivation

AdaSent: Self-Adaptive Hierarchical Sentence Model
I Is vector representation with fixed-length enough to represent

different granularities of phrases/sentences/documents ?
I Can we model the composition behaviour using algebraic

operations with enough flexibility ?

24 / 45

AdaSent
Motivation

AdaSent: Self-Adaptive Hierarchical Sentence Model
I Is vector representation with fixed-length enough to represent

different granularities of phrases/sentences/documents ?
I Can we model the composition behaviour using algebraic

operations with enough flexibility ?
I Can we design a model which can decide the representation ofphrases/sentences on the fly based on the current task athand ?

25 / 45

AdaSent
Architecture

Gating Network

Classifier

x1

x2x3x4x5x6

thecatsaton

thematH

Three components:

26 / 45

AdaSent
Architecture

Gating Network

Classifierx1x2x3x4x5x6

thecatsaton

thematH

Three components:
I Composition hierarchy

27 / 45

AdaSent
Architecture

Gating NetworkClassifierx1x2x3x4x5x6

thecatsat

onthematH

Three components:
I Composition hierarchy
I Gating network

28 / 45

AdaSent
Architecture

Gating Network

Classifierx1x2x3x4x5x6

thecatsaton

thematH

Three components:
I Composition hierarchy
I Gating network
I Classifier

29 / 45

AdaSent
Architecture

Properties of AdaSent
I Maintains a hierarchy of abstractions from the raw input,

rather than a fixed length vector representation
I Implements N-gram model where N ranges from 1 to thelength of the sentence
I Implements and extends the mixture-of-experts idea
I Final decision is based on an ensemble of different level ofabstractions
Gating Network

Classifier

x1x2

x3

x4x5x6

thecatsat

onthematH

30 / 45

AdaSentArchitecture

Composition Pyramid
Directed acyclic graph whose height depends on the length ofinput sentence.
Composition dynamics:(t−1hjt = ωl hjt−1 + ωr hj+1+ ωc h̃jt
t−1h̃jt = f (WL hjt−1 + WR hj+1+ bW )Local combination parametrizations: ωlsoftmax (v)=  t−1
ωr = softmax (GL hjt−1 + GR hj+1+ bG )exp(v1 )

ω
.
cPl 1
 .. 
i=1 exp(vi )
exp(vl )where WL , WR ∈ RD×D and GL , GR ∈ R3×D .
x1

x2x3x4x5x6

thecatsat

onthematH

31 / 45

AdaSent
Architecture

Composition Pyramid
Intuitive interpretation:= (!l2onthematon+ (!r2+thematon

themat+ !r12!l12on

thematonthemat)+ !c11+ !r11!l11on

thematonthemat)+ !c12onthemat!c232 / 45

AdaSent
Architecture

Level Pooling
Global (average/max) pooling applied to each level of the pyramid
to build the abstraction in the hierarchy.
Average pooling:
T1 Xh̄ =htT
t=1

Max pooling:h̄j = max htj ,t∈1:T

x1

x2

x3x4x5x6

thecatsaton

themat∀j ∈ 1 : DH

33 / 45

AdaSent
Architecture

Gating Network and Classifier
Gating network: ω : RD 7→ R+ . Let γt , ω(h̄t ). Constraint:PTDt=1 ω(h̄t ) = 1. Let g : R 7→ ∆+ be the classification function.

Classification consensusp(C = c|x1:T ) =TX

p(c|Hx = t)·p(Hx = t|x) =t=1

TX

gc (h̄t )·ω(h̄t )t=1

Gating Network

Classifier

x1

x2x3x4x5x6

thecatsat

onthematH

34 / 45

AdaSent
Learning

Backpropagation through Structure (BPTS)
Partial derivative of objective function L with respect to model
parameters:
T T −t+1
T TX−t+1ttX∂L∂L ∂hj∂L X X ∂L ∂hj=,=∂WL∂hjt ∂WL ∂WR∂hjt ∂WR
t=1

wheret=1

j=1t+1j=1t+1∂L∂L ∂hj∂L ∂hj−1=+ t+1
ttt+1∂hj∂hj∂hj∂hj−1 ∂hjtt+1
∂hj−1

∂hjt

= ωr I + ωc diag(f 0 )WR ,∂hjt+1∂hjt= ωl I + ωc diag(f 0 )WL35 / 45

AdaSent
Experiments

Data Sets
I MR. Movie reviews data set where each instance is asentence. The objective is to classify each review by its overallsentiment polarity, either positive or negative.
I CR. Annotated customer reviews of 14 products obtained

from Amazon. The task is to classify each customer review
into positive and negative categories.
I SUBJ. Subjectivity data set where the goal is to classify eachinstance (snippet) as being subjective or objective.
I MPQA. Phrase level opinion polarity detection subtask of theMPQA data set.
I TREC. Question data set, in which the goal is to classify aninstance (question) into 6 different types.
36 / 45

AdaSent
Experiments

Data Sets
DataMRCRSUBJMPQATREC

N
10662
3788
10000
10099
5952

dist(+,-)(0.5, 0.5)
(0.64, 0.36)(0.5, 0.5)
(0.31, 0.69)(0.1,0.2,0.2,0.1,0.2,0.2)

K222
2
6|w|
18
17
21
3
10testCVCVCV
CV
500

Table: N counts the number of instances and dist lists the class
distribution in the data set. K represents the number of target classes.
|w| measures the average number of words in each instance. test is thesize of the test set.

37 / 45

AdaSent
Experiments

Classification Accuracy
Model
NB-SVM
MNB
RAE
MV-RecNN
CNN
DCNN
P.V.
cBoW
RNN
BRNN
GrConv
AdaSent

MR
79.4
79.0
77.779.0
81.5
74.8
77.2
77.2
82.3
76.3
83.1

CR
81.8
80.0
85.0
78.1
79.9
82.3
82.6
81.3
86.3

SUBJ
93.2
93.6
93.4
90.5
91.3
93.7
94.2
89.5
95.5

MPQA
86.3
86.3
86.4
89.6
74.2
86.4
90.1
90.3
84.5
93.3

TREC
93.6
93.0
91.8
87.3
90.2
91.0
88.4
92.4
38 / 45

AdaSent
Experiments

Model Variance
Model
P.V.
cBoW
RNN
BRNN
GrConv
AdaSent
Model
P.V.
cBoW
RNN
BRNN
GrConv
AdaSent

MR
71.11 ± 0.80
72.74 ± 1.03
74.39 ± 1.70
75.25 ± 1.33
71.64 ± 2.09
79.84 ± 1.26
MPQA
67.93 ± 0.57
84.04 ± 1.20
84.52 ± 1.17
85.36 ± 1.13
82.00 ± 0.88
90.42 ± 0.71

CR71.22 ± 1.04
71.86 ± 2.00
73.81 ± 3.52
76.72 ± 2.78
71.52 ± 4.18
83.61 ± 1.60
TREC
86.30 ± 1.10
85.16 ± 1.76
84.24 ± 2.61
86.28 ± 0.90
82.04 ± 2.23
91.10 ± 1.04

SUBJ
90.22 ± 0.21
90.58 ± 0.52
89.97 ± 2.88
90.93 ± 1.00
86.53 ± 1.33
92.19 ± 1.19

39 / 45

AdaSent
Experiments

Belief Score Distribution

Figure: Each row corresponds to the belief score of a sentence of length
12 sampled from one of the data sets. From top to bottom, the 10
sentences are sampled from MR, CR, SUBJ, MPQA and TREC
respectively.
40 / 45

AdaSent
Experiments

Concrete Example

Sentence: If the movie were all comedy it might work better but it
has an ambition to say something about its subjects but notwillingness.

41 / 45

AdaSent
Experiments

Representation Learning - SUBJ

Figure: AdaSent

Figure: Original

42 / 45

AdaSent
Experiments

Representation Learning - MPQA

Figure: AdaSent

Figure: Original

43 / 45

AdaSent
Experiments

Representation Learning - TREC

Figure: AdaSent

Figure: Original

44 / 45

Thanks

ThanksQuestion and Answering
Online Version: arXiv:1504.05070
International Joint Conference on Artificial Intelligence 201545 / 45