Basics of algorithmics, computation models, formal languages

author: Colin de la Higuera, University Jean Monnet, St Etienne

Description

Between the many theoretical computer science issues that one should be aware of when working in Machine learning, we visit, in this series of lectures, two.

The first corresponds to strings, and through the study of strings, the questions about more complex structures like trees and graphs. We describe the main algorithmic and combinatorial questions about substrings and subsequences, and concentrate our attention to the topological questions: ordering strings and computing distances and kernels.

The second is complexity. Not only should we be aware (and have a reasonable control of the techniques involved) of the usual barriers, but we should know something about classes for randomized algorithms. We also show some examples concerning Las Vegas and Monte Carlo techniques.

Categories

Top: Computers: Programming

You might be experiencing some problems with Your Video player.

*Slides*
0:00	TCS for Machine Learning Scientists
0:16	Outline
4:58	Disclaimer
6:31	Alphabet and Strings - 1
7:52	Alphabet and Strings - 2
8:45	Alphabet and Strings - 3
9:11	Alphabet and Strings - 4
10:26	Alphabet and Strings - 5
11:01	Alphabet and Strings - 6
11:52	Basic Combinatorics on Strings
14:25	Algorithmics
16:54	Knuth-Morris-Pratt Algorithm
22:50	KMP (Step 2)
22:56	A Run with Abac in Aaabcacabacac
25:45	Conclusion
26:40	Order! Order!
27:11	Different Orders Can Be Defined Over Σ - 1
28:09	Different Orders Can Be Defined Over Σ - 2
30:06	Example
30:40	Distances
31:14	The Problem - 1
31:47	The Problem - 2
37:03	Summarizing
37:23	Pros and Cons
38:10	Four Types of Distances - 1
39:21	Four Types of Distances - 2
39:59	Method - 1
41:49	Method - 2
42:58	Four Types of Distances - 3
44:06	Four Types of Distances - 4
45:00	The Edit Distance
45:21	Figure
45:28	Basic Operations - 1
46:39	Basic Operations - 2
47:17	Examples - 1
47:24	Examples - 2
47:53	Examples - 3
48:59	A Confusion Matrix
49:55	Another Confusion Matrix
50:00	A Similarity Matrix Using An Evolution Model
51:03	Conditions
51:13	Aligning - 1
52:36	Aligning - 2
52:55	General Algorithm
53:35	The Formula for Dynamic Programming - 1
54:09	The Formula for Dynamic Programming - 2
57:30	The Formula for Dynamic Programming - 3
59:04	The Formula for Dynamic Programming - 4
59:15	Complexity
59:59	Extensions

Lecture rating

People found this lecture:
Worth seeing
because it is:
Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

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.

Watch videos: (click on thumbnail to launch)

Part 1 1:01:07

!NOW PLAYING

Part 2 0:56:35

Part 3 0:24:14

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

1 Colin de la Higuera, July 6, 2007 at 4:39 p.m.:

A comment upon the talk. The idea was to start imagining some elements of TCS revisited for ML students. I suppose there are other possible ways of doing this, and I don't claim this is the most important bits nor that it is essential.
I also wish to say that there are some murky bits, specially about the KMP algorithm. (sorry)

2 Alex Gillis, September 29, 2007 at 2:56 a.m.:

I really enjoyed this lecture. Its the one that has most stayed with me. I knew a little about complexity classes, but you introduced a lot of incredible new stuff, quickly but it a very intuitive way.

3 Abazh, December 22, 2007 at 2:21 p.m.:

I do really enjoyed this lecture. I like the way you deliver explanation, thus make me stayed until the end of the vid lecture. Thanks!

4 quelqu'un, January 16, 2008 at 2:37 p.m.:

la partie 2 s'arrete et ne bouge plus après 18 minutes 52!
(the part 2 stops and do not want to continue when reaching 18 minutes 52!)

Write your own review or comment: