WIXLIB

Embedded SystemsAdaptive embedded systemsTwo applications to societyobservationsDevika SubramanianDepartment of Computer ScienceRice //www.cs.rice.edu/ devikaObservation driven, task-specific decision makingMachine LearningEmbedded Adaptive SystemsPrior knowledgePrior knowledgeTraining dataLearningalgorithmPredictive modelobservationsLearningalgorithmSystem fora taskModelactionsEnvironmentEnvironmentCalculate decisions on the basis of learned models of systemsResearch questions in adaptiveembedded system designWhy embed learning? We cannot calculate and implement anaction-choice/decision-makingstrategy for the system at designtime. System dynamics are unknown/partiallyknown.System dynamics change with time.A one-size-fits-all solution is notappropriate – customization is needed. Representation: What aspects of the task,environment and system dynamics do weneed to observe and model for decisionmaking?Learning: How can we build and maintainembedded models in changing environments?Decision making/acting: How can we usethese models effectively to make decisionswith scarce resources in changingenvironments?1

Approach Roadmap of talkDesign and validatealgorithms for large-scalereal world, socially relevantproblems.Publish in the applicationcommunity journals; getcommunity to routinely usethe methods.Abstract task-levelanalysis and presentmethods to the AIcommunity. Two case-studies Unknown system, changing dynamics Submarine School 101The NRL Navigation TaskTracking human learning on a complex visualmotor task.Predicting the evolution of internationalconflict.The NRL Navigation TaskMine configurationchanges with everygame. Pilot a submarine to a goal througha minefield in a limited time period Distance to mines revealed viaseven discrete sonarsGame has a strategicand a visual-motorcomponent! Time remaining, as-the-crow-fliesdistance to goal, and bearing to goalis given Actions communicated via a joystickinterface50% of class weeded out by this game!Task QuestionsLearning curves1009070S360S450S540S130S2 485001Success %80Successfullearnerslook rners areDOA! Is the game hard? What is the source ofcomplexity?Why does human performance plateau out at 80%?Is that a feature of the human learning system orthe game? Can machine learners achieve higherlevels of competence?Can we understand why humans learn/fail to learnthe task? Can we detect inability to learn earlyenough to intervene?How can we actively shape human learning on thistask?Navy takes 5 days to tell if a person succeeds/fails.2

Mathematical characteristicsof the NRL task A partially observable Markov decisionprocess which can be made fully observableby augmentation of state with previousaction.State space of size 1014, at each step achoice of 153 actions (17 turns and 9speeds).Feedback at the end of up to 200 steps.Challenging for both humans and machines.Reinforcement r2, .actionTaskReinforcement Learning, Barto and Sutton, MIT Press, 1998.Reinforcement learning/NRLtask Representational hurdles State and action spaces have to be manageablysmall.Good intermediate feedback in the form of anon-deceptive progress function needed. Appropriate credit assignment policy needed tohandle the two types of failures (timeouts andexplosions are different).Q-learning is too slow to converge (becausethere are up to 200 steps in a single trainingepisode). Algorithmic hurdles State space design 0.75 if s is an all-blocked state and s’ is a not-all-blocked state 0.5 Diff in sum of sonars/1000 if s’ is an all-blocked state 0.5 Diff in range/1000 abs(bearing - 6)/40 otherwisespeed: 0, 20 and 40.turn: -32, -16, -8, 0, 8, 16, 32.Automated discovery of abstract state spaces for reinforcement learning,Griffin and Subramanian, 2001.The dense reward functionr(s,a,s’) 0 if s’ is a state where player hits mine. 1 if s’ is a goal state 0.5 if s’ is a timeout stateBinary distinction on sonar: is it 50?Six equivalence classes on bearing: 12,{1,2}, {3,4}, {5,6,7},{8,9}, {10,11}State space size 27 * 6 768.Discretization of actionsCredit assignment policy Penalize the last action alone in a sequencewhich ends in an explosion.Penalize all actions in sequence which endsin a timeout.3

Simplification of valueestimation Results of learning complete policyEstimate the average local reward for eachaction in each state.r1sr2s’Blue: learn turnsonlyr3Red: learn turnand speedtInstead of learning QHumans makemore effectiveuse of trainingexamples. ButQ-learner gets tonear 100% success.Open question:Q( s, a ) α [ r max Q ( s ' , a ' )] (1 α )Q ( s, a ) When does thisa'We maintain an approximationapprox work?Q ' ( s, a ) (running avg of rewards at s for a ) * pct of wins from sQ(s,a) is the sum of rewards from s to terminal state.Griffin and Subramanian, 2000Full Q learner/1500 episodesFull Q learner/10000 episodesFull Q learner/failure after 10KWhy learning takes so longStateswhere3 or fewerof the 153action choicesare correct!Griffin and Subramanian, 20004

Lessons from machine learningTask QuestionsTask level Task is hard because states in which action choice iscritical occur less than 5% of the time.Staged learning makes task significantly easierA locally non-deceptive reward function speeds uplearning. Reinforcement learning Long sequence of moves makes credit assignmenthard; a new cheap approximation to global valuefunction makes learning possible for such problems.Algorithm for automatic discretization of large,irregular state spaces. Is the game hard? Is it hard for machines? Whatis the source of complexity?Why does human performance plateau out at 80%?Is that a feature of the human learning system orthe game? Can machine learners achieve higherlevels of competence?Can we understand why humans learn/fail to learnthe task? Can we detect inability to learn earlyenough to intervene?How can we actively shape human learning on thistask?Griffin and Subramanian, 2000, 2001ChallengesTracking human learningPrior knowledgeLearningalgorithmModelStrategy mappingsensor panelsto joystickaction (sensor panel,joystick action)(time coursedata) High-dimensionality of visual data (11 dimensionsspanning a space of size 1014)Large volumes of dataNoise in dataNon-stationarity: policies change over timeInterventionsto aidlearningExtract strategy and study its evolution over timeEmbedded learner design Representation Use raw visual-motor data stream to inducepolicies/strategies.Learning Direct models: lookup table mapping sensors attime t and action at t-1 to distribution ofactions at time t. (1st order Markov model)Decision-making Compute “derivative” of the policies over time,and use it (1) to classify learner and selectinterventions, (2) to build behaviorallyequivalent models of subjectsStrategy: mapping from sensorsto action distributionswWindow ofw games5

Surely, this can’t work! There are 1014 sensor configurationspossible in the NRL Navigation task.However, there are between 103 to 104 ofthose configurations actually observed byhumans in a training run of 600 episodes.Exploit sparsity in sensor configurationspace to build a direct model of thesubject.How do strategies evolve overtime? Distance function between strategies: KLdivergencewwOverlap sΔ P (Π (i, i w), Π (i w s, i 2 w s )Results: model derivativeBefore shift (episode 300)Siruguri and Subramanian, 2002After shift (episode 320)Model derivative for HeiSiruguri and Subramanian, 20026

How humans learn Behaviorally equivalent modelsSubjects have relatively staticperiods of action policy choicepunctuated by radical shifts.Successful learners have conceptualshifts during the first part oftraining; unsuccessful ones keeptrying till the end of the protocol!Generating behaviorallyequivalent models ModelNRL taskSubject Cea: Day 5: 1To compute action a associated withcurrent sensor configuration s in a givensegment, take 100 neighbors of s in lookup table. perform locally weighted regression(LWR) on these 100 (s,a) pairs.SubjectSubject Cea: Day 5: 2SubjectModelModelSubject Cea: day 5: 3SubjectModel7

Subject Cea: Day 5: 4SubjectModelSubject Cea: Day 5: 6SubjectModelSubject Cea: Day 5: 8SubjectModelSubject Cea: Day 5: 5SubjectModelSubject Cea: Day 5: 7SubjectModelSubject Cea: Day 5: 9SubjectModel8

Comparison with global methodsSummary We can model subjects on the NRL task inreal-time, achieving excellent fits to theirlearning curves, using the available visualmotor data stream.One of the first in cognitive science todirectly use objective visual-motorperformance data to derive evolution ofstrategy on a complex task.Siruguri and Subramanian, 2002LessonsWhere’s the science? Neural correlates Are there neuralcorrelates tostrategy shiftsobserved in thevisual-motor data?Learn simple models from objective, lowlevel data!Non-stationarity is commonplace, need todesign algorithms robust with respect to it.Fast new algorithms for detecting changepoints and building predictive stochasticmodels for massive, noisy, non-stationary,vector time series data.Task Questions Can we adapt training protocols in the NRLtask by identifying whether subjects arestruggling with strategy formulation orvisual-motor control or both?Can we use analysis of EEG data gatheredduring learning as well as visual-motorperformance data to correlate ‘brainevents’ with ‘visual-motor performanceevents’? Can this correlation separatesubjects with different learningdifficulties?9

The (new) NRL Navigation TaskGathering performance data256 channel EEG recordingFusing EEG and visualmotor dataThe coherence function EEGDataArtifactRemovalCoherencecomputation VisualizationMechanismPerformanceDataFrequency bands Coherence map of connections ineach band Δ (0-5 Hz)θ (5-9 Hz)α (9-14 Hz)β (14-30 Hz)γ (40-52 Hz)Coherence provides the means tomeasure synchronous activitybetween two brain areasA function that calculates thenormalized cross-power spectrum, ameasure of similarity of signal in thefrequency domainC xy ( f ) S xy ( f ) 2[ S xx ( f ) S yy ( f )]Topological coherence mapBackFront10

Subject moh progression chartControlControlTargetTargetTarget - controlTarget - controlSubject bil progression chartResults (subject moh)ResultsResults (subject bil)Subject GSubject is a nearexpert performerSubject is inskill refinementphaseBaluch, Zouridakis, Stevenson and Subramanian, 2005, 2006Baluch, Zouridakis, Stevenson and Subramanian, 2005, 200611