TODO

- mege in notes from CS182, 6.867

- generalized/weighted least squares -> local linear regression with kernels -> density estimation

- Why do kernel smoothers divide the norm by λ before applying the weight fn? Isn't it dealt with in the summation in the estimator fn?

- kalman filters, smoothing

- <http://measuringmeasures.com/blog/2010/3/12/learning-about-machine-learning-2nd-ed.html>

- separating hyperplane

- sigmoid kernel function

- k-means++

- <http://hunch.net/?p=224>

- <http://googleresearch.blogspot.com/2010/04/lessons-learned-developing-practical.html>

- top 10: <http://gettinggeneticsdone.blogspot.com/2010/04/top-10-algorithms-in-data-mining.html>

supervised learning

- old statistically inspired linear methods

- artificial neural networks

- decision trees

- support vector machines

- Gaussian processes

- case-based reasoning

- knowledge-based ai

- statistical ml

- anytime learning: online continuous learning

graph searching

- BFS, DFS, IDFS

- best-first search

- beam search

- A* serach

- dijkstra

constraint satisfaction

- unification

- backtracking

optimization algo families

- minimax

- hill climbing

- simulated annealing

- nearest neighbors

- knn

- cuckoo hashing

- genetic algos

clustering

- difference from partitioning: clustering is on points that have coordinates

or distances, rather than shapeless graphs

- hierarchical

- agglomerative: bottom-up merging

- divisive: top-down splitting

- partitional: determine all clusters at once; can be used in divisive

- $k$-means: assign each point to cluster with closest centroid; initialize with random centroids

- locality sensitive hashing (LSH): TODO

- also used in nearest neighbor search

- feature space vectors are sets

- jaccard distance

- min-hash

- density-based: discover arbitrary shapes

- 2-way-/co-/bi-clustering: objects are clustered but also their features; if

data in matrix, then rows and columns clustered simultaneously

- distance measures: euclidian/2-norm, manhattan/1-norm, maximum norm aka

infinity norm, hamming, inner product/cosine similarity

- many clustering algos require number of clusters as input;

machine learning

- linear classif, perceptron, SVM

- non-linear classif, kernels

- n-way classif, rating, ranking

- anomaly detection

- (logistic) regression

- collab filt

- feat sel

- ensembles, boosting

- active learning

- model sel, complexity

- VC-dim, generalization guarantees

- mixture models, EM

- topic models, markov models, HMMs

- bayesian nets (and learning them)

- markov random fields, factor graphs, inference

- inference, belief propagation

- inference, junction trees

- conditional models, structured prediction

- learning conditional models

- current topics

Developing a self-driving car for the 2007 DARPA Urban Challenge (Seth Teller's

Angstrom talk, 5/1/08)

- 40 compute cores

- many other teams performed human-assisted map annotation

- Seth's team focused on going almost entirely from sensing

- many other teams used much fewer cores

- uses of sensing

- using vision for finding paint

- using active sensing for depth

- stereo algos: reconstruct 3D from cameras

- recent stereo algos have a global component that is harder to parallelize

- optical flow: estimating motion across time

- groups

- planning & control: how to stay on the white dotted lines; one technical

focus

- perception: another technical focus

- working on the car

- software infrastructure: codebase, OS, etc.

- power-bound

- also CPU-bound in the sense that they could process rawer images, at higher

rates, etc.

- also IO-bound; had 2 GigE and a CAN, all mostly utilized

- Anant: near future will yield cameras that have encoders

- Seth: these are not as useful for vision research

- algos need to know gradients, for instance; what does MPEG do to gradients?

- looked at GPUs

- programming models still painful

- form factor limits (1U blades)

- didn't want DSPs either because they didn't know what algos they ultimately

wanted; everything was exploratory

- Anant: suggest fifth team, on computation resources

MACHINE LEARNING

- variables

- visibility

- _hidden variables_, _latent variables_, _model parameters_, _hypothetical variables_

- _observable variables_, _manifest variables_

- causality

- _independent variable_, _predictor variable_, _regressor_, _controlled variable_, _manipulated variable_, _explanatory variable_

- _dependent variable_, _response variable_, _regressand_, _measured variable_, _responding variable_, _explained variable_, _outcome variable_

- TODO any diff btwn visibility/causality?

- bayes vs frequentist

- TODO diff btwn | and ;?

- models

- data mining

- collaborative filtering

- analyses

- mathematical

- real analysis

- complex analysis

- statistical

- analysis of variance (ANOVA)

- time-series analysis

- latent variable model

- factor analysis

- latent trait analysis

- latent profile analysis

- latent class analysis

- PCA

- exploratory data analysis

- resources

- http://videolectures.net/icmi05_bengio_tsmla/

- google video: machine learning

trending algorithms

- simple baseline trend algorithm: daily trend = most recent day's change *

log(monthly total)

- <http://stackoverflow.com/questions/1635703/understanding-algorithms-for-measuring-trends>

decision tree learning algorithms TODO

- NP complete

generalization error

- cross validation, bootstrapping: methods to estimate generalization error;

based on "resampling"

- often used to choose among different models; e.g. different neural network

architectures; choose one with lowest gen error

- cross validation

- $k$-fold cross validation: divide data into $k$ subsets of roughly same

size (folds)

- train $k$ times, each time leaving out one of the subsets, then testing on

one subset

- LOOCV: when $k$ is the sample size ($k=n$ where $n$ is data size)

- leave v out cross validation: more elaborate and expensive that leaves out

all possible subsets

- diff from "split-sample"/"hold-out" method commonly used for early stopping

in neural networks

- only 1 fixed subset (the validation set) used to estimate generalization

error, not $k$ subsets; no "crossing"

- cross-validation to split-sample is superior for small datasets

- LOOCV good for continuous error functions/model-selection methods, bad for

discontinuous ones

- jackknifing: LOOCV but for estimating bias not gen error

- compute some statistic of interest in each subset

- compare avg of these to avg of entire sample to estimate the latter's bias

- bootstrapping: seems to work better than CV in many cases

- repeatedly analyze subsamples of the data rather than subsets

- ea subsample is a random sample with replacement from full sample

- TODO

- ref: <http://www.faqs.org/faqs/ai-faq/neural-nets/part3/section-12.html>

nlp

===

- segmentation: figuring out word boundaries

- simplest: over all possible segmentations, return seg w max prod over all

words of P(word)