1The Challenge of Composition inDistributional and Formal Semantics
IJCNLP2017 Tutorial
Ran Tian, Koji Mineshima andPascual Martinez-Gomez

Self-introduction

2ªRan Tian (⽥ 然)– https://tianran.github.io ßFind Tutorial Slides Here!
– Research Assistant Professor at Tohoku University, Japan– I’m interested in natural language understanding, have worked
on recognizing textual entailment, distributional representations,and recently published a theory of additive composition (methodof composing meaning by simply adding word vectors)• Logical Inference on Dependency-based Compositional Semantics; ACL
2014• Learning Semantically and Additively Compositional Distributional
Representations; ACL 2016
• The Mechanism of Additive Composition; Machine Learning Journal 2017

My colleagues

3ª Koji Mineshima (峯島 宏次)– https://abelard.flet.keio.ac.jp/person/minesima/– Project Associate Professor (Ochanomizu University, Tokyo, Japan)– Research Area: formal semantics, semantic parsing, and natural language inference(recognizing textual entailment)ª Pascual Martínez-Gómez– https://researchmap.jp/pascual– Research Scientist at the Artificial Intelligence Research Center, AIST (Tokyo,
Japan)– Current main interests are in Question Answering over large Knowledge Bases,
Semantic Parsing, Natural Language Inferences and multi-modality.

Principle of Compositionality

4

The meaning of a complex expression
is determined by the meanings of its
constituent expressions and the rules
used to combine them. [Frege]
It is the idea that the complicatedmeaning of a whole sentence can bebuilt from simpler, more basic units.

Different Layers of Meaning

5

Is the word “wine” more similar
to “beer” than “house”?
basic,
shallow:

Individual Words
Predicate-argument Structures
Logic

Does sentence A
contradicts sentence B?

Modality, Intention, etc.

…

complicated,deep:

Who did what to whom?

What’s the intention of
the speaker?

Two Approaches to Semantics
Two Approaches

Distributional semantics
represents words as vectors;
so word similarity can becalculated as vector
similarity?
??

Phrases?
Predicate-argument
structures?
How to compose meanings
from word vectors, so thatinference can be conveyed?

6Two Approaches to Semantics
Two Approaches

Formal semantics
represents words as
symbolic predicates

The focus is on rules ofcombining the symbols
into logical formulas
Those logical formulas
can be directly used for
inference and reasoning

7

Composition is the Challenge
Two Approaches

?
??

focus

8

Composition is the Challenge
Two Approaches

?

9

10

In this Tutorial:

We will cover the two approaches, first separately, thenshow some case studies bringing them togetherª Distributional Semantics:ª Formal Semantics:– How to make word embeddings?
(with some detailed studies)– Introduction to the CCG
grammar and semantic
composition– How to combine word vector torepresent phrases and sentences?
(an overview)– Can we just add the vectors? (withrecent theoretical results)– Case studies of combining vectorbased composition and logicalreasoning– Datasets and challenging
composition phenomena– ccg2lambda: a generalframework for formal
semantic composition– Hybrid two approaches forthe task of RTE

RTE: an Ultimate Test

11

Recognizing Textual Entailment (RTE)
T: Smoking in public spaces is prohibited in most cities
in Japan.
H: Some cities in Japan do not allow smoking inrestaurants.

[Does the Text entail the Hypothesis?]

One expects RTE systems to answer many questions at
different levels of meaning:
Is “prohibited” similar to “not allow”?
“X is prohibited” means “does not allow X”?

Are restaurants public spaces?
Does “most” imply “some”?

So one needs to combine two approaches to semantics!

12

Part I: Composition in Distributional
Semantics

1. Word Embeddings(with some detailed studies)

Highlights for detailed studies 13ªDistributional HypothesisªMaking co-occurrence table andapplying a function– What function to apply, and why?

ªDimension reduction– Truncated SVD• How to choose the number of dimensions?

– Noise Contrastive Estimation and word2vec

Distributional Hypothesis

14“You shall know a word by the company it keeps”[Harris 1954; Firth 1957]

Co-occurrence Table

15

Context: words before/after target
TargetWords:

𝑓"# =the frequency of “train”
co-occurring with “drink”

a vector related to themeaning of “beer”

16

Additional Stepsª Applying a function to the co-occurrence frequencies(More on this later)ª Dimension reduction (More on this later)ª Cosine similarity

Context
TargetWords:(2.3 1.1 …) apply a function(5.6 1.1 …)
project to lower
dimensions
beer (𝐯% )θwine (𝐯& )cos 𝜃 = 𝐯𝐯, ⋅ 𝐯𝐯.
,

.

17

What Function to Apply?
ªConditional Probability: 𝑝"# =012

5∑2 012ªSquare root [Rohde+’06; Lebret+’14; Stratos+’15]:𝑝"#– so the L2-norm of a vector is always 1ªPoint-wise Mutual Information (PMI) [Church+
1990; Dagan+ 1994; Turney’01]: PMI"# = ln 𝑝"# − ln 𝑝#– Positive PMI = max(PMI, 0) to avoid ln 0 = −∞ [Bullinaria+’07]– ln 𝑝"# + 𝜀 − ln 𝑝# + 𝜀 also works [Tian+’17]– More generally, ln 𝑝"# − 𝑎" − 𝑏# where 𝑎" and 𝑏# are learned fromdata [Pennington+’14]

Rationale

18ªIn practice, square root or PMI performbetter than bare conditional probabilityª[Pennington+’14] attributes the superiority to

a property of the log function:– probability values are naturally multiplied– vectors are naturally added– log is a homomorphism from multiplicative groups toadditive groups, i.e. ln 𝑥𝑦 = ln 𝑥 + ln 𝑦
– but this is not likely the only reason, because squareroot also works

19(Generalized) Zipfʼs LawªAnother explanation [Tian+’17]:– co-occurrence frequencies obey a Zipf-like law:
Context
TargetWords:

1000

count

100
10
1
1

10

100

1000 10000

rank– the expected L2-norm of a vector = the 2nd momentof the Zipf-Law distribution is predictable

20

Therefore...

ªSince a Zipf-Law distribution has heavy tail,the expected L2-norm of a word vector will be∞ unless one applies some function to reducelarge entries
0.4

standard deviationof L2-norms of 0.3
word vectors: 0.2
0.1
0various functions: ln 𝑝 𝑝J.% 𝑝J.&

𝑝 𝑝J.L 𝑝J.M … 𝑝J.N 𝑝…
ªBehavior of word vectors drastically change
when there is/not an expected L2-norm

21

Dimension Reductionª project word vectors to lower dimensionality:dd-dimensional
word embeddings:

projection
matrix A

𝑀 = PMI"#=Xªcan be learned as factorization to approximate
M:
X

𝐴P%

≈𝑀

Truncated SVD

22ªSingular Value Decomposition (SVD) of M:
𝑀 = 𝑈Σ𝑉 V
where 𝑈 and 𝑉 are orthogonal matrices, Σ is diagonalof non-negative entries
ΣW takes the top-𝑑 diagonal entries of Σ𝑈 ΣW

ΣW 𝑉 V ≈ 𝑀 is a factorization approximating 𝑀

𝑈 ΣW only has 𝑑 columns non-zero

Set 𝑋: = 𝑈 ΣW as the 𝑑-dimensional wordembeddings

How many dimensions?

23

diagonal
value of Σ:
usually 250~300

0

100

200

300

400

500

600

dimension 𝑑

700

800

known as the “knee finding” or “elbow finding”
technique in machine learningCalculating Truncated SVD

24ªFast random algorithm for truncated SVD[Halko+’11]:
1. calculate 𝑄 = 𝑀𝐵, where 𝐵 is a random matrix with 2𝑑columns (i.e. randomly project 𝑀 into 2𝑑 dimensions)
2. Gram-Schmidt process making 𝑄 orthogonal
3. calculate SVD for the smaller matrix 𝑄V 𝑀, then recover the 𝑑dimensional truncated SVD for 𝑀ªImplemented in sklearn.decomposition.TruncatedSVDªStep 2,3 almost take no time. Main cost is thematrix multiplication in Step 1, which can be
accelerated by GPU

Online Estimation
For training word embeddings, a training
example is a co-occurrence pair 𝑖, 𝑗 .
Instead of counting the frequency 𝑓"# andexplicitly calculating PMI"# = ln 𝑝"# − ln 𝑝# anddoing dimension reduction, one can also train
embeddings in an online fashion, implicitly
optimizing the log-likelihood ln 𝑝"#
This is implemented in the popular toolkit
word2vec [Mikolov+’13], which uses NoiseContrastive Estimation (NCE) [Gutmann+’12]

25

26

NCE
ªProblem setting: a model θ estimates
probability 𝑝` 𝑥 for each data point 𝑥.
How to optimize θ?
– Maximum likelihood: argmax ∑c ln 𝑝` 𝑥`

– but simply optimizing this leads to 𝑝` 𝑥 → ∞– NCE: mix data 𝑥 with noise 𝑦.
Model 𝑝` 𝑥 = Prob 𝑥 is data|𝑥 , maximize thelikelihood of 𝑥 being data and 𝒚 being noise:argmax l ln 𝑝` 𝑥 + l ln 1 − 𝑝` 𝑦`cnNCE and word2vec

27ª In word2vec [Mikolov+’13], real co-occurrence data 𝑖, 𝑗 ismixed with noise 𝑖, 𝑘 , where 𝑘 is randomly generated
from unigram distributionª 𝑑-dimensional vector 𝐯" for target word, 𝐮# for contextª Model the probability of pair 𝑖, 𝑗 being co-occurrence
data as 𝜎 𝐯" ⋅ 𝐮#
– 𝜎 is the sigmoid functionª Objective:
argmax l ln 𝜎 𝐯" ⋅ 𝐮# + l ln 1 − 𝜎 𝐯" ⋅ 𝐮r
`

",#

",r

28

Part I: Composition in Distributional
Semantics

2. Vector-based Composition(an overview)

Composition

29ªWord embeddings can be used to calculatesemantic similarities between words; butwords can compose more complicatedmeanings into phrases and sentences.
good lawyer
Mary loves John.
ªHow would vectors deal with the composition?
ªWe need composition models for word vectors[Mitchell+’10]

30

Evaluation Datasetsª Phrase similarities obtained ª phrase-word synonymy
from crowd-sourcing
compiled from WordNet[Mitchell+’10; Kartsaklis+’14;
Takase+’17][Turney’12]– controlled phrase pairs of thesame combination of POS– WordNet contains multiword expressions– similarity scores by crowdsourcing– some of them synonyms
to single words

phrase1phrase2

win battle fight war
pay price cut cost...

score1 score2 ...

phraseword

52

red salmon
dance hallsockeyeballroom

6 ...
3 ...

...

Composition Models

31ªFour influencing ideas for modelingcomposition:– tree/recursive structure [Socher+’13]– lexicalization [Baroni+’10; Paperno+’14; Bride+’15]– syntactic types corresponding to tensor types[Baroni+’10; Coecke+’10]– training word embeddings and composition
operators jointly [Hashimoto+’14; Pham+’15]

Recursive Composition

32ªNatural language has recursive structure
Dorothy thinks that Toto suspects that Tin Man said that....

ªRecursive Neural Networks [Socher+’13]

Lexicalization

33ªEarly studies explore simple functions ascomposition models, such as addition
and multiplication [Mitchell+’10]ªIntuition of lexicalization: composition
depends on the lexicon being composed[Baroni+’10]– “red car” is a car, “fake car” is not a car– should they be composed by the same function?

Syntactic↔Tensor Types

34ªNouns are vectors, adjectives arematrices [Baroni+’10]:– adjectives are functions from the meaning of a noun
onto the meaning of a modified noun

ªMore generally, every syntactic typecorresponds to a tensor type [Coecke+’10]

Joint Training

35ªUse syntactic structures to jointly learn
both stand-alone word embeddings andtheir compositions [Hashimoto+’14]:– composed vectors can provide additional contexts
for training word embeddings

36Part I: Composition in Distributional
Semantics

3. Theory of Additive Composition(with recent theoretical results)

Additive Composition37ªIn order to represent the meaning of a phrase,
simply take the average of word embeddings– classical and widely used; works well in practice

dance

hall

dance + halldancingbhangradancesbreakdancing
breakdancemusic
stripteasehip-hophi-nrgcha-cha-cha
disco

halls
faneuilfame
auditorium
DDDD-seat
inducteebanquetingxrco
now-demolishedwigmorenatatorium

ballroom
halls
xrco
DDDD-seatrockettes
banquetingbarbershop
burlesquedancing
wigmoreauditorium

38

Theoretical AnalysisªIn order to theoretically analyze a composition
method, investigate two types of vectors:– regard a two-word phrase “s t” as a single target, construct avector of co-occurrence; the natural vector 𝐰 {vw}
– take the average of word vectors 𝐰 v and 𝐰 w ; the composed
vector (𝐰 v +𝐰 w )/2
Target𝐰v𝐰w
𝐰 {vw}

Context

apply a function,e.g. PMI
more on this later glass

53

27

60

43

2

4

34

beer glass

17

9

24

14

0

0

5

ªEstimate distance between the two

Intuition

39ªwhen two words occur next to each other andform a phrase (“beer glass”), they have almost
the same contexts; in contrast, when they
separately appear elsewhere, their contexts
are independent...the strength of modern beer is usually around 4%...
...you can find the perfect beer glass from the new website...
...I wish I can drink a glass of wine in the evening...

ªwhen word vectors are added, independence
cancels out [Tian+’17]

40

FormalizationªIn order to measure how rare two words
occur next to each other:– set 𝜋v ≔ 1 − 𝑓{vw} ⁄𝑓w and 𝜋w ≔ 1 − 𝑓{vw} ⁄𝑓v , where 𝑓v , 𝑓w
and 𝑓{vw} are counts of s, t and “s t” respectivelyªThen, under certain assumptions, one
has [Tian+’17]:
𝐰 {vw} − 𝐰 v + 𝐰 w /2 ≤𝜋v& + 𝜋w& + 𝜋v 𝜋w /2– if s and t frequently occur next to each other, 𝜋v and𝜋w decrease, the bound of distance gets stricter

Verified in Real CorpusªIn the British National Corpus:– take each bigram “s t” occurring more than 200 times– plot 𝐰 {vw} − 𝐰 v + 𝐰 w /2 on y
– plot𝜋v& + 𝜋w& + 𝜋v 𝜋w /2 on x

– theoretically 𝑦 ≤ 𝑥 (under red line)

41And what Function to Apply... 42ªConditional Probability: 𝑝"# =012

5∑2 012ªSquare root [Rohde+’06; Lebret+’14; Stratos+’15]:𝑝"#– so the L2-norm of a vector is always 1ªPoint-wise Mutual Information (PMI) [Church+
1990; Dagan+ 1994; Turney’01]: PMI"# = ln 𝑝"# − ln 𝑝#– Positive PMI = max(PMI, 0) to avoid ln 0 = −∞ [Bullinaria+’07]– ln 𝑝"# + 𝜀 − ln 𝑝# + 𝜀 also works [Tian+’17]– More generally, ln 𝑝"# − 𝑎" − 𝑏# where 𝑎" and 𝑏# are learned fromdata [Pennington+’14]

...for Additive Composition?
ªPMI and 𝑝 work well; bare 𝑝 does not.

ªThe same tendency observed in phrase
similarity tasks [Tian+’17]43Bias and Variance44ª In machine learning, generalization error isdecomposed into bias and varianceª From this point of view, the estimation of a naturalvector has high variance, because phrases are sparseª In contrast, composed vector can be estimated withlower variance because words are abundant; word
vectors are easy to obtainª For additive composition, the result shows that bias isbounded. So, with lower variance and bounded bias,
additive composition is a reasonable method for
estimating phrase vector. [Tian+’17]

45

To conclude:
Additive composition is justifiable by amachine learning theory, as long as
you choose the right function to apply.

Word Order46ªSo far, additive composition is not awareof word order:
beer + glass = glass + beer
John + loves + Mary = Mary + loves + JohnªA proof-of-concept application: improved
additive composition for two-wordphrases, with order awareness [Tian+’17]
beerL + glassR ≠ glassL + beerR

47

Idea
ªtwo sets of word vectors, one for “leftside” and one for “right side”
beerL + glassR for “beer glass”
glassL + beerR for “glass beer”ªHow to make sure that the additive
composition indeed approximates theintended vector?
– addition cancels independent contexts, meanwhile itreinforces those shared by two words occurring next
to each other48

Near-far ContextªPut N-F labels on context words such that:– when sL and tR occur in the order “s t”, they share the samecontext:
a

b

c

d

e

s

t

u

x

y

a

bF cF dN eN sLt

uN vN wF xF

ya

bF cF dN eNtR

uN vN wF xF

y

s

v

w

– when sL and tR occur in the order “t s”, they do not sharecontext because of different N-F labels:
a

b

c

d

t

s

u

v

a

b

cF dF eN tN

sLu

vN wN xF yF

aF bF cN dN

e

e

tR

w

sN uN vF wF

x

x

y

y

Error PlotbeerL + glassR is closer to “beer glass” thanglassL + beerR

49

Demo: most similar word pairs

50

51

To conclude:
With theoretical insights, word order is nolonger an issue for additive composition,
at least for two-word phrases.

Composition and Analogy

52ªComposition is closely related to analogy[Turney’12; Tian+’17; Gittens+’17]:– if one can construct a relation between words bycomposition, one might also reverse the process tosubtract that relation from words– a hypothesized illustration [Tian+’17]:
man ≈ male + humanking ≈ royal + male + humanwoman ≈ female + human
queen ≈ royal + female + humanking – man + woman≈ royal + female + human≈ queenIs it real?

53ªHaving theoretical support is nice.
But to what extent can we count on the
additive composition?
ªadditive composition is...
– far from perfect– no syntax– occasionally inspiring, mostly trivial– but no chaos

54Part I: Composition in Distributional
Semantics

4. Toward Vector-based Reasoning:(Case Studies)Composition and Reasoning55ª Composition is closely related to reasoning:“A and B” implies A“not B” contradicts B“Tad Lincoln’s farther is Abraham Lincoln. Abraham Lincoln was born in Kentucky.”
implies “Birthplace of Tad Lincoln’s farther is Kentucky”.

ª For vector-based composition, reasoning is an ultimate
test of whether composition is properly modeledª We discuss three case studies in which vector
composition is linked to reasoning– Compositional training for knowledge base completion [Guu+’15]– A composition model implementing formal semantics [Tian+’16]– An embedding model for first order logic [Rocktaschel+’15]

56• Compositional training for knowledge
base completion [Guu+’15]

Path Query on Knowledge Graph

57ªKnowledge graph can be used to answer
complicated, compositional questions [Guu+’15]:
Where are Tad Lincoln’s
parents located?

ªModeling path queries in a low-dimensional
vector space forces generalization, and canrecover some missing facts in knowledge baseCompositional Training

58ªTrain on not only single edges in aknowledge graph, but also longer paths[Guu+’15]ªe.g. a bilinear model:– entities are vectors (𝐱 v ), relations are matrices (𝑊• )– query vector: 𝐱 ‚ƒ„_†‡ˆ‰Š‹ˆ 𝑊Œƒ•Žˆ•• 𝑊‹Š‰ƒ•‡Šˆ– answer score:𝐱 ‚ƒ„_†‡ˆ‰Š‹ˆ 𝑊Œƒ•Žˆ•• 𝑊‹Š‰ƒ•‡Šˆ ‘ 𝐱 ’ƒ•“‡ˆ”•Šˆ_•–

59

FindingsªCompositional training reduces cascading
errors and improves path query answeringªCompositional training improves knowledge
base completion as well:– viewed as a “distributional semantics” for database entities,
compositional training provides additional contexts
Mary_Lincoln
parents

Abraham_Lincoln
location

Springfield
Tad_Lincoln

birth_place“context” for Tad_Lincoln
additional context

60• A composition model implementing
formal semantics [Tian+’16]

Formal↔Distributional Semantics
formal semantics

Reasoning
Logic

symbolic formulasymbolic operations
words

?
?

61

distributional semantics

composed vectors
vector composition
word vectorsªA composition model which is [Tian+’16]:– based on the theory of additive composition– modeling semantic roles in a logically consisted fashion

62

The Formal SemanticsªDependency-based Compositional Semantics(DCS) [Liang+’11; Tian+’14]:– content words represent concepts– projection 𝜋 maps concept to denotation (set of things),
according to some semantic role
– compose by set calculation, according to dependency-like trees
drug
DCS Tree:banned drugs

drug
ARG

denotation of“banned things”:

denotation of“banned drugs”:

alcoholAspirin∩ Thalidomide
Thalidomide intersection...
...

Thalidomide
...

ARG

projection map
OBJ

ban

ban

=

πOBJ
πSBJ

denotation of “banning agents”

63

Proposal
Represent set operators as vector calculations[Tian+’16]
𝑋, 𝑌 : denotation∩ : intersection
𝜋 : projection
𝜋 P% : inverse image

corr.

𝜋 𝑋∩𝑌 ⊆π 𝑋 ∩π 𝑌
𝜋 P% 𝑋 ∩ 𝑌 = 𝜋 P% 𝑋 ∩ 𝜋 P% 𝑌
𝑋 ⊆ 𝜋 P% ∘ 𝜋 𝑋
𝑋 = π ∘ 𝜋 P% 𝑋

𝑀 𝐱+𝐲 =𝑀 𝐱 +𝑀 𝐲
𝑀P% 𝐱 + 𝐲 = 𝑀P% 𝐱 + 𝑀P% 𝐲
𝐱 = 𝑀P% ‘ 𝑀 𝐱
𝐱 = 𝑀 ‘ 𝑀P% 𝐱

dot productquery vector:

vdrug + vbanMOBJ
intersection•
answer vectors:

projection

vban

𝐱, 𝐲 : vector
principle of additive+ : addition
composition
𝑀 : matrix
logical consistencyP%
𝑀 : inverse matrix

ufood
uthalidomide…

drug
marijuana
cannabis
trafficking
thalidomide...

coarse-grained listfor “banned drugs”

Training

64ªsample paths from DCS treesªmix real paths with random noise (Noisecontrastive training as in word2vec [Mikolov+’13])ªa path connects two words through several
semantic roles, e.g. John-ARG-SBJ-OBJ-ARG-Maryªprobability of it being real path is modeled as:P%P%𝜎 𝐯•žŸ 𝑀¡¢£ 𝑀¤¥¦
𝑀§¥¦ 𝑀¡¢£‘ 𝐮¨©•nªjoint training as in [Hashimoto+’14], andcompositional training as in [Guu+’15]

Demo: most similar words

65

An example from a recent model showing
additive composition aware of semantic roles:
officer who arrests:

officer who is arrested:varrestMSBJ + vofficer

varrestMOBJ + vofficer

officer + arrested

policegestapoFBI
policemanofficersuspect
policemanprisonerinmateaccomplice

court-martialed
cashieredinspector-generalreservist
paymaster

Implementation: https://github.com/tianran/vecdcs

66• An embedding model for first order logic[Rocktaschel+’15]

Injecting Logic into Factorization

67

Instead of learning embeddings by naïve
matrix factorization, one can make them
conform to logical background knowledge[Rocktaschel+’15]

68

TrainingªMap logical formulas to continuous functions ofembeddings, so that they have gradients andcan be trained by backpropagation– Ground atom:
parent(Tad_Lincoln, Mary_Lincoln)𝜎 𝐱 ‚ƒ„_†‡ˆ‰Š‹ˆ 𝑊Œƒ•Žˆ• ‘ 𝐱 ªƒ•«_†‡ˆ‰Š‹ˆ

– Logical conjunction:
parent(Tad_Lincoln, Mary_Lincoln) ∧ parent(Tad_Lincoln, Abraham_Lincoln)𝜎 𝐱 ‚ƒ„_†‡ˆ‰Š‹ˆ 𝑊Œƒ•Žˆ• ‘ 𝐱 ªƒ•«_†‡ˆ‰Š‹ˆ ‘ 𝜎 𝐱 ‚ƒ„_†‡ˆ‰Š‹ˆ 𝑊Œƒ•Žˆ• ‘ 𝐱 ¡-•ƒ“ƒ®_†‡ˆ‰Š‹ˆ
– Logical negation:¬parent(Tad_Lincoln, Robert_Lincoln)
1 − 𝜎 𝐱 ‚ƒ„_†‡ˆ‰Š‹ˆ 𝑊Œƒ•Žˆ• ‘ 𝐱 ¢Š-Ž••_†‡ˆ‰Š‹ˆ– Other logical operators can be deduced accordingly

69

Thank you!
Questions?