NATO Advanced Study Institute on Mining Massive Data Sets for Security

Learning with structured data - structured outputs

author:Patrick Gallinari, Université Pierre et Marie Curie - Paris 6
published: Nov. 26, 2007, recorded: September 2007, views: 154

Turn off the lights

You might be experiencing some problems with Your Video player.

Slides

Slides
0:00	Learning structured outputs
0:00	Example : HTML to XML (Tree annotation)
0:03	Model and training
0:36	Experiments : HTML to XML
1:30	Performance (1)
2:31	Experiments : HTML to XML
2:44	Performance (1)
3:29	Performance (2)
3:31	Summary
5:04	Discriminant models
6:29	Usual hypothesis
8:44	Structured Perceptron (Collins 2002)
9:38	Algorithm (1)
11:20	Algorithm (2)
11:30	Algorithm (1)
11:37	Algorithm (2)
11:54	Extension of large margin methods
13:32	SVM ISO (Tsochantaridis et al. 2004) (1)
16:03	SVM ISO (Tsochantaridis et al. 2004) (2)
16:42	SVM ISO (Tsochantaridis et al. 2004) (3)
17:32	Learning
17:36	SVM ISO (Tsochantaridis et al. 2004) (3)
17:48	Learning
19:06	M3N (Taskar et al. 2003)
20:06	Summary: discriminant approaches
21:46	Incremental learning Learning to search solution spaces
22:55	General ideas
25:13	Incremental parsing (Collins, Roark, 2004) (1)
27:44	Incremental parsing (Collins, Roark, 2004) (2)
28:25	How to build sequences of partial trees : from Y(i) to Y(i+1) (1)
30:38	How to build sequences of partial trees : from Y(i) to Y(i+1) (2)
34:11	SEARN (Daume et al 2006)
35:19	Example : sequence labelling
35:44	Example : expected loss
37:15	Example: state space exploration guided by local costs
37:46	Example : expected loss
37:48	Example: state space exploration guided by local costs
40:19	Inference
40:45	Training (1)
41:54	Training (2)
43:32	Training algorithm (1)
43:33	Training algorithm (2)
44:27	Reinforcement learning search (Maes 2007)
45:36	Reinforcement learning
47:27	Markov Decision Process (1)
48:35	Markov Decision Process (2)
49:41	Markov Decision Process (3)
50:55	Reinforcement learning (1)
51:35	Reinforcement learning (2)
52:41	prototype RL ALGORITHM
53:09	Structured outputs and MDP (1)
53:43	Structured outputs and MDP (2)
54:12	Exemple : sequence labeling (1)
55:44	Exemple : sequence labeling (2)
57:54	Exemple : sequence labeling (1)
58:19	Exemple : sequence labeling (2)
58:22	Dependency parsing (1)
59:57	Dependency parsing (2)
60:38	XML structuration (1)
61:54	XML structuration (2)
62:36	XML structuration (3)
62:43	XML structuration (4)
62:44	XML structuration (5)
63:03	XML structuration (6)
63:05	XML structuration (7)
63:08	XML structuration (8)
63:29	XML structuration (9)
63:31	XML structuration (10)
63:48	XML structuration (11)
63:49	XML structuration (12)
63:59	XML structuration (13)
64:01	XML structuration (14)
64:03	XML structuration (15)
64:17	XML structuration (16)
64:21	Results
66:38	Summary on search method
67:22	Conclusion

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Description

We focus on the prediction of structured outputs. A classical example is sequence labeling with applications in speech, vision, natural language or biology. Beyond sequences, the prediction of structured data, like trees, lattices or graphs also occurs in many domains. Structured prediction is usually considered as an extension of multi-class classification. It is considered as a challenging problem since the size of the output space increases drastically with the number of potential dependencies between output variables. Several methods have been recently proposed in the ML community in order to overcome this complexity and the domain is still largely open. We will provide a review of these methods and discuss there potential and limitations. These different ideas will be illustrated with Natural language processing and text mining applications.