The 5th Advanced NLP Summer Camp

“Grounded Language Learning from Video!
Described with Sentences”!
Haonan Yu and Jeffrey Mark Siskind!
ACL2013
Daichi Mochihashi
daichi@ism.ac.jp
The Institute of Statistical Mathematics
2013-8-31(Sat), Kujukuri-hama, Japan!!

About this paper! ACL 2013 Best Paper Award! http://haonanyu.com/research/acl2013/ provides"

a paper, slides, all codes and data!!

About the author! Jeffrey Siskind: famous for his extraordinary optimized

scheme compiler “Stalin”– https://engineering.purdue.edu/~qobi/software.html! As a researcher, he pursues grounded language

learning from 90s! This paper is an extension to Barbu&Siskind (2012)"
with sentences– Fundamentals: “Recognizing Human Action in Time-"Sequential Images using Hidden Markov Model”,"
Junji Yamato, Jun Otani, Kenichiro Ishii (NTT), CVPR 92"(citation 976!)!!

Objectives of this paper
What Children Learn From

The person picked up the traffic-cone.
The person picked up the traffic-cone to the left of the stool.
The person put down the trash-can quickly.

The person carried the chair.
The person carried the backpack.
The chair approached the backpack.

!!
Yu and Siskind (Purdue)

Grounded Language Learning

Monday 5 August 20133 / 19Objectives of this paper
What Children Learn From

The person picked up the traffic-cone.
The person picked up the traffic-cone to the left of the stool.
The person put down the trash-can quickly.

The person carried the chair.
The person carried the backpack.
The chair approached the backpack.

!!
Yu and Siskind (Purdue)

Grounded Language Learning

Monday 5 August 20133 / 19Objectives of this paper
What Children Learn From

The person picked up the traffic-cone.
The person picked up the traffic-cone to the left of the stool.
The person put down the trash-can quickly.

The person carried the chair.
The person carried the backpack.
The chair approached the backpack.

!!
Yu and Siskind (Purdue)

Grounded Language Learning

Monday 5 August 20133 / 19Objectives of this paper
What Children Learn From

The person picked up the traffic-cone.
The person picked up the traffic-cone to the left of the stool.
The person put down the trash-can quickly.

The person carried the chair.
The person carried the backpack.
The chair approached the backpack.

!!
Yu and Siskind (Purdue)

Grounded Language Learning

Monday 5 August 20133 / 19Objectives of this paper! From the set of {video,sentence} pairs, we will learn– HMM for the “meaning” of each word
! Actual state trajectory! Emission distribution, State transition matrix! .. almost automatically.
! Foundation of this model: "Factorial HMM (Ghahramani and Jordan 1995)!!

Notice! Original paper is very difficult to understand.

– Unintuitive notations– No intuitive figure of the model! See this slides, and draw a picture by yourself!

!!

Meanings as HMM! This paper uses a fixed vocabulary:!

person, backpack, trash-can, chair, traffic-cone, stool! Imagine we already track regions in a video as objects:!"!

Meanings as HMM! Each region has features (=outputs) like– Velocity– Movement direction– Color– X-coordinate, Y-coordinate– Size! Then,!!!

Meanings as HMM! “jump” is a 2-state HMM over velocity-direction! “pick up” is a 2-state HMM over two objects features,"like distance and y-coordinates! “person” is a 1-state HMM emitting image features"(like some specific colors or textures)! “quickly” is a 1-state HMM over the velocity of its
argument!"!

Meanings as HMM“towards”!"!

Meanings as HMM“approached”!"!

The Problem! Image regions are not aligned with words– And we do not know which region to select! However, same words will appear in multiple videos! Similar regions will be aligned to the same word

– Word “dim” will be aligned to dark color region– Word “run” will be aligned to regions with high velocity! How to optimize the correspondences?

!"!

Assumptions! Each sentence caption is generated from a known!

CFG, thus we can parse the sentence! We know the arity of each word (eg. carry( , ))! We can do a shallow “semantic parsing” of a sentence! However, we don’t know what the “object”

corresponds to!
! The number of objects in a video is known !
(4 for the next slide)

!"!

!"!

Assumed Grammar!"!

Region tracking

Detectors yieldcandidate regions!!!!

! Regions evolve like a HMM! Each frame has a “correct” region for object #i!"!

Region tracking+Word HMM!!!!

FeatureEmission!!!!

StateTransition! Joint learning of two HMMs (product of HMMs)!"!

Region tracking+Word HMMs!!!!

“toward”“push”! Joint learning of many HMMs!"!

Region trackings+Word HMMs!!!!

“toward”“push”! Joint learning of many HMMs

“backpack”!!!

Graphical Model as FHMM
!!!!

!!!!

!!!!

CFG!!!!

! Sentence tracker can be described as a!

Factorial HMM (FHMM) (autoregressive FHMM)– CFG partly determines the portion of the output!"!

EM in the Sentence Tracker!"!HMM reestimation formulak"l transition probability of HMM of word v
k"j feature emisson probability of HMM of word v! Each term in the numerator is calculated from a!

standard forward-backward in HMM!
(each HMM in turn)!"!

Experiments!"!

Experimental results! Yielded same!

performance ashand-craftedmodels with!
no supervision! Very similar
model to thehand-crafted
one is obtained!"!

Summary! Modeling “meaning” of a word by a HMM– Representing time series of features associated with"that word– Strong representational power! Dynamic noun (eg. “jump”)! Static verb (eg. “hold”)! Sentence Tracker=Factorial HMM– Choosing appropriate image subregions– Deeply nested EM, forward-backward! Equivalent performance with a hand-crafted model! Very complicated but interesting!
!"!