| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Get control of your email attachments. Connect all your Gmail accounts and in less than 2 minutes, Dokkio will automatically organize your file attachments. You can also connect Dokkio to Drive, Dropbox, and Slack. Sign up for free.

View
 

Definitions

Page history last edited by olivier 14 years ago

Definitions

 

ProtocolMain constraint on algorithm design
Success Measuresometimes impossible to practically measure. May serve as a guide for designing algorithms
Type of Analysiswhat we want to prove
Data generation mechanismOnly relevant for the analysis, not for designing an algorithm
Further Restrictive Assumptionsused for designing algorithms or proving restricted results

 

Examples

 

  • Off-line supervised learning: training pairs are given, the goal is to produce a

model that predicts well

  • Semi-supervised: training pairs and unlabeled data are given, the goal

is to produce a model that predicts well

  • Transductive: training pairs and unlabeled data are given, the goal is

to predict well on the unlabeled examples

  • On-line: repeated transductive learning (one new example

at a time, prediction to be performed at each step)

  • Variants of on-line: actions instead of predictions (e.g.

reinforcement learning)

 

General framework

 

Predictor receives x, takes an action y, and gets reward r.

It is possible to combine r with x.

 

A prediction function takes a history of pairs ((x,r), y) and a new x to predict y.

 

 

Classification

 

NameXY
Fixed designfixediid
Random designiidiid
Sequence predictionfixedworst-case
Online learningworst-caseworst-case
Online compressionfixediid

Comments (0)

You don't have permission to comment on this page.