Machine Learning I - CNL

Machine Learning IProfessor:Petros KoumoutsakosDozenten:Nicol SchraudolphSibylle MüllerWEB PAGE: www.icos.ethz.ch - Teaching - Machine LearningLECTURES: Thursday, 13:15 - 15:00 Uhr – IFW A36EXERCISES: Monday, 15:15 - 16:00 Uhr – IFW C42Machine Learning Iwww.icos.ethz.ch1What (and where) is HRS?Machine Learning Iwww.icos.ethz.ch21

Machine Learning ITextbooks: Neural Networks for pattern recognition - C. BishopOxford U. Press (used in Machine Learning II) Learning from Data - Cherkassky and MulierJ. Wiley and Sons (expensive)Grades (if needed) : final oral examination (15 mins)if oral exam grade is on the border your homeworkperformance will be taken into accountMachine Learning Iwww.icos.ethz.ch3Homework and Exercises Homework: handed out in classor posted on the web site by Friday noon bring it to the exercise on Monday at least 60% of homework required for the testat content of Monday exercises: review of previous lecture review of homework first month: tutorials on probability theory,differentiation, and linear algebraMachine Learning Iwww.icos.ethz.ch42

ExerciseMon.1LectureContentThu.Content(no exercise)24.10.- organisational matters- Machine Learning:Introduction and History (K,S)Homework: Perceptron learning rule228.10.- homework review- Tutorial (M):probability theory31.10.Bayes Rule (S):- central role in statistics- derivation and formula- use for machine inferenceHomework: ovarian cancer screening ORwhale sound filtering304.11.- homework review- Tutorial (M):differentiationMachine Learning I07.11.Foundations (S):- modeling of data- maximum likelihood (ML)- least-squares (LS) regressionas an ML procedurewww.icos.ethz.ch5Reading: chapters 1-5 ofConjugate Gradient Without the Pain45611.11.Tutorial (M):differentiation,linear algebraOptimisation (S):14.11. - simple gradient descent (GD)- basis functions, generalized LS18.11.Tutorial (M):linear algebraOptimisation (S):- weakness of simple GD21.11.- Newton's method- singular value decompositionlecture reviewRegularisation (M):- overfitting28.11.- cross-validation- penalisation25.11.Machine Learning Iwww.icos.ethz.ch63

78902.12.lecture review09.12.lecture review16.12.review (M):backpropagationMachine Learning I1005.12.Model Selection (M):- Ockham's razor:learning as compression- structural risk minimization- minimum description length12.12.Neural Networks (S):- biological background- trainable basis functions- backpropagation algorithm19.12.Training Methods (S):- learning rate adaptation- quasi-Newton methods- conjugate gradientwww.icos.ethz.ch(no exercise)09.01.7Density Estimation (S):- Parzen window method- Expectation-Maximisationreview (M):11 13.01.expectation-maximisationClassification (K):- Fisher's linear discriminants16.01.- k-nearest neighbor- vector quantisation12 20.01. lecture reviewDimensionality Reduction (K):23.01. - curse of dimensionality- principal components analysis- nonlinear autoencoding13 27.01. lecture review30.01. Self-Organising Maps (K)14 03.02. lecture review06.02. Summary lectureMachine Learning Iwww.icos.ethz.ch84

Machine Learning : A definitionGiven a collection of data originating fromsome functional dependencyinfer this dependencyMachine Learning Iwww.icos.ethz.ch9Machine Learning : A definitionA first cut : Various distribution functions describe wellmany events of reality.Examples : Gauss distribution (e.g. usually grades in anexam ) - Poisson distribution(e.g. distribution of bacteria in water).A second cut : Create descriptions based on anobservational frameworkMachine Learning Iwww.icos.ethz.ch105

How would you describe ?The flight of a paper airplane ?The sound of a violin ?The glow of a campfire ?Surfing a 4m wave ?Highway traffic in rush hour ?The pumping of your heart ?Machine Learning Iwww.icos.ethz.ch11How would you describe :Breaking Glass ?QuickTime and a Compact Video decompressor are needed to see this picture.Machine Learning Iwww.icos.ethz.ch126

How would you describe :Raindrops ?QuickTime and a Microsoft Video 1 decompressor are needed to see this picture.Machine Learning Iwww.icos.ethz.ch13How would you describe :how ants find food lishthebypathemittingantswitharecomplexstrongaable pheromonecolony activitiesFirsttheyexploreOther ants use thepheromoneto find the food sourcechemicalthrough:to adaptsubstanceflexibility,by rapidly- arobustnessconcentrationpheromoneadopting secondand- asself-organizationtheybestforagesolutionsfor foodMachine Learning Iwww.icos.ethz.ch147

Pheromone Trail FollowingAnts and termites follow pheromone trailsMachine Learning Iwww.icos.ethz.ch15Asymmetric Bridge ExperimentGoss et al., 1989Machine Learning IDorigo & Bertolissi, 1998www.icos.ethz.ch168

How would you describe :Moving on a Real Bridge ?QuickTime and a Sorenson Video decompressor are needed to see this picture.Machine Learning Iwww.icos.ethz.ch17How would you describe :A Violin and its playing index.htmlMachine Learning Iwww.icos.ethz.ch189

Describing a Violin PlayingThe Observational (MACHINE LEARNING) Way : Determine some correlation between actions and sound that comesfrom the instrument find an effective descriptionThe Numerical Way : Determine the Governing Equations from first principles - (This should be good enough to letyou distinguish between a Stradivarius and a Guarneri ) Determine a method for discretizing them Solve them numerically - (Use large supercomputers (or MATLAB) to get the desiredaccuracy)The Analytical Way (pencil/paper or MAPLE) : make assumptions Simplify the Governing Equations Solve them analytically - (Solution may not sound very good)Machine Learning Iwww.icos.ethz.ch19Levels of Description for a ProblemSpecificGeneralModelFirst iscreteContinuousQualitativeQuantitativeMachine Learning Iwww.icos.ethz.ch2010

The Dream of Intelligent Machines(A Brief History)N. SchraudolphMachine Learning Iwww.icos.ethz.ch21The Big QuestionWhat is life, intelligence, conciousness? Is it caused by divine fire (the Prometheus legend)?It does look like some kind of magic, but:any sufficiently advanced technology is indistinguishablefrom magic (Arthur C. Clarke). So perhaps it is due to some physics we don‘t understand well yet?Machine Learning I electricity? (Mary Shelley‘s Frankenstein, 1817) quantum mechanics? (Penrose, 1989) emergent complexity of adaptive systems?www.icos.ethz.ch2211

A Pragmatic ApproachWe may never know what life/intelligence/consciousness is,but we can try to build machines that look (and act) as ifthey possessed it.If physics is the answer, we may yet become Prometheus,creating real’’ artificial life/intelligence/consciousness.If divine fire is required, we may at least create simulacra thatare good enough’’ for many practical purposes.Through the ages, this program was pursued using the mostadvanced technology of the time. Before the advent ofelectronic computing (and with it, software) that meantbuilding clever hardware: mechanical automata.Machine Learning Iwww.icos.ethz.ch23Early Automata 400 BC Philosopher and mathematician Archytas ofTarentum built a wooden dove that could flap its wingsand fly. Early 16th Century Hans Bullmann creates the firstandroids - simulated people that can play musicalinstruments for the delight of paying customers. 1533 In his laboratory at Nuremburg, scholar JohannMüller, aka Regiomontanus, is reputed to have createdan iron fly and an artificial eagle, both of which couldtake to the air. 1543 In England, John Dee creates a wooden beetlethat can fly for an undergraduate production ofAristophanes' Pax. 1725 At the Heilbrunn chateau in Germany, amechanical theatre is created featuring 119 animatedfigures that perform a play about village life to theaccompaniment of a water-powered organ.Machine Learning Iwww.icos.ethz.ch2412

Jacques de Vaucanson Born 1709 in Grenoble While training as a Jesuit,builds flying angels whichcause him to be thrown outof the order. 1737 Vaucanson creates amechanical flute player thatcan play 11 different tunes.He also creates an automaticduck that can drink, eat,paddle in water, digest andexcrete like a real duck. Eachwing reputedly contains morethan 400 moving parts. ‘‘a rival to Prometheus‘‘ - VoltaireMachine Learning Iwww.icos.ethz.ch25Remains of Vaucanson’s Duckthe program!Machine Learning Iwww.icos.ethz.ch2613

Jaquet-Droz Pierre Jaquet-Droz (1721-1790), wasborn in Neuchâtel (Switzerland) andbecame an engineering clockmaker. Hewas interested very early by appliedmechanics. His instruction and hisintelligence allowed him to be one of thelargest mechanists of his time. His son Henri-Louis (1752-1791) becamehis collaborator at a young age andbrought his taste for the arts, music inparticular. Among his apprentices wasJean Frederic Leschot (1746-1824) whowas his right arm. He took over themanagement of the house after thedeath of his two leaders.Machine Learning Iwww.icos.ethz.ch27Jaquet-Droz Automata (1774) 3 famous automata: the writer, themusician, and the draughtsman Presented to Swiss high society, toLouis XV in Paris, in Brussels,London, Russia, Madrid, etc. Now in the Museum of Art andHistory, Neuchatel, Switzerland.sample drawings by the draughtsman:The DraughtsmanMachine Learning Iwww.icos.ethz.ch2814

Baron Wolfgang von Kempelen born 1734 in Bratislava scientist and inventor at the courtof Maria Theresa in Vienna constructed the world’s firstspeech synthesizer (today in theDeutsches Museum, Munich)But infamous for Machine Learning Iwww.icos.ethz.ch29von Kempelen’s Chess Turk (1769)Machine Learning Iwww.icos.ethz.ch3015

The Chess Turk von Kempelen called it “a boldillusion”; it was of course a hoax! nonetheless extremely influentialin establishing the idea ofintelligent machines toured the world for almost 70years; destroyed by fire in 1854Machine Learning Iwww.icos.ethz.ch31Famous Chess Turk Opponents Frederick the Great lost against it, as did Benjamin Franklin Napoleon Bonaparte tried to cheat against it, but lost as well his stepson was so desperate to find out howthe Turk worked, he bought it for 30’000 francs Edgar Allan Poe wrotean investigative essay on it last but not least: CharlesBabbage played against it,then went on to design hisfamous compute enginesMachine Learning Iwww.icos.ethz.ch3216

Charles Babbage (1791 – 1871)the Difference Engine (modern reconstruction)Machine Learning Iwww.icos.ethz.ch33The Advent of ComputingThe advent of electronic computers brough two importantchanges to the quest for machine intelligence: it could be decoupled from special-purpose, limitedperformance, mechanical or electrical hardware it brought a growing realization that our brains are in factcomputing devicesThe focus thus shifted to trying to design intelligent software.The science of cybernetics began to systematically examinetwo-way coupling between an (analog) computer and itsenvironment through adaptive feedback loops.Machine Learning Iwww.icos.ethz.ch3417

The Perceptron 1943: McCulloch & Pittspropose the first computationalabstraction for what biologicalneurons might be doing 1958: Rosenblatt proposes thefirst training procedure for theMcCulloch-Pitts perceptron. 1969: Minsky & Papert show that simple perceptrons canonly learn simple (linearly separable) problems. SymbolicAI wins the battle for funding over machine learning. Rosenblatt, discredited and depressed, dies in a “boating accident”.Machine Learning Iwww.icos.ethz.ch35Neural Networks 1980s: a training procedure for multi-layer perceptrons,that overcome the Minsky/Papert limitation, is found independently by Parker, Widrow, Rumelhart/Hinton/Williams meanwhile, symbolic AI is stagnating. Neural networks,and with them machine learning in general, take over as theleading paradigm for the Promethean quest. today: machine learning is an integral part of computerscience, with applications in many aspects of everyday life. artificial life/intelligence/consciousness, however, remainselusive. Perhaps it’s quantum mechanics after all?Machine Learning Iwww.icos.ethz.ch3618

if oral exam grade is on the border your homework performance will be taken into account Machine Learning I www.icos.ethz.ch 4 Homework and Exercises Homework: handed out in class or posted on the web site by Friday noon bring it to the exercise on Monday at least 60% of homework required for the testat content of Monday exercises: