Here are some of my take-aways from the AAAI-15 artificial intelligence conference this year.

• How Far Has AI Come?  Having come from some involvement in AI back in the 90’s, it is very interesting to note that there is a bit of AI here that looks a whole lot like AI did back then, especially in the domains that involve GOFAI (good old fashioned AI).  Some of the work was probably not even what I would classify as AI, being more like either every day software engineering or incremental advances in optimization of complex problems.  Many solutions still involve highly contrived problem spaces.
• Hinton Says: “GOFAI Yourself, Deep Learning is Here”.  Geoffrey Hinton, who helped give birth to the back-propagation and Boltzmann machine neural networks as well as reinforcement learning, shared very compelling results coming from the connectionist camp and his latest contribution of “deep learning”.  Deep learning is more or less the new buzz term for neural networks.  It almost seemed like he was trying to start a nerd fight, basically proclaiming GOFAI a waste of time, especially with the beatdown it’s been taking from deep learning.
• What if AI Succeeds?  Stuart Russell, author of some comprehensive texts on AI, talked a bit about the implications of AI succeeding, resonating Kurzweil, but suggesting a regulatory body in the government and building ethical intentionality into the functioning of robots.
• Robots is Where it’s Happening.  Honestly, the most interesting work here was in the realm of making robots more intelligent in uncertain environments.
• Things That Might Scare You.   Well, what should not scare people is the idea of a sentient robot army taking over the world, much to the contradiction of some popular press…  today’s AI is no where near nor even remotely resembles human reasoning (obvious to everyone here).  On the other hand, there was one talk that suggested people do prefer robots-as-managers, with the author suggesting the next step would be to figure out how best to have robots manage people (egads).
• Watson is What Watson Does.  IBM explicitly stated that they don’t really understand how Watson (a.k.a. the only non-human millionaire to win Jeopardy) really works.  As in, they have no formal model or theory around it;  they just created this aggregate system that exhibits better behavior than they can explain.  Plea was made to have the academic community help.

My observations from the 4th full day of sessions at the AAAI-15 artificial intelligence conference in Austin, Texas.

von Neumann’s Dream

Talk by Michael Bowling discussing games and applicability to AI, etc.  3 weeks ago Bowling’s team was able to announce that “poker has been solved”.

Stats on game history:  2007 checkers “solved”.   1996 Kasparov loses.  1994 first time any computer beats a chess master.  1948 Turing & 1949 Shannon both wrote chess programs.  1928-1944, theory of games by von Neumann.  1864 Babbage and Lovelace tic-tac-toe, with hints at chess.

Why games?  So many aspects of intelligent thinking are combined in game play; why we use them to help develop our children.  Easy to determine progress.

“Solved” implies guaranteed win.

Many board games are “perfect information” games.  Poker, however, involves things like bluffing and uncertainty.    There’s a part of the decision making space that involves observations, guesses, and missing information.  How do we represent “bluffing”?   Poker has generally been perceived to be a “huge” game that we would never be able to solve.

Looking at Heads-Up Limit Texas Hold’em (HULHE).  3.2 x 10^17 game states (though don’t necessarily know which is which).  3.2 x 10^4 infosets.  1.4 x 10^13 canonical infosets.  Would need 3 petabytes to represent?   Unlike other games that have 3 win states; e.g. {win, lose draw}, poker has more of a continuous range; e.g. [-24,24] big blind (bb).  So solutions end up being approximations.

So instead of getting it perfect, we aim for “essentially solved” (something like 95% confidence), approaching as if training a player over a “lifetime” of poker playing.   Also apply “regret-matching”, in which the AI looks back at the utility of past decisions and replays the ones that seemed to lead to less “regret”.  Over time regret will converge to 0.  Cumulative regret is measured over time, and the most regretful strategies end up getting pruned, which leads to a probability distribution on the no-regret leftovers.  Strategies translate into decision edges in the tree.  Keeping track of all that non-regret may be intractable, so divide and localize many regret algorithms at different points in the tree.  Thus far, these changes between 2003 and 2013 lead to improvements of orders of magnitude.

Some ideas did not work…

Abstraction strategy.  Start with the full game strategy being just too big to solve.  Idea is to abstract the game itself into a form from which a tractable solution can be determined and then translate the strategy back into context.  This actually was successful in that it did beat some top poker players.    From there, we could start measure meaningfully how close we were getting to an optimal solution measuring “exploitability”.   Watching the graph, results were looking very very promising, but misconstrued.

Decomposition strategy.  Very successful in perfect information games.  As name implies, you solve sub-trees independently.  However, in poker, you don’t really have independent sub-trees because of unknown information that crosses potential future solutions (not a perfect information space).  Did have some success with this using sub-trees to work out counterfactuals.  Ends up still being resource intensive.

One did work…

Algorithmic strategy (the one that did work).  Track and use cumulative regret and regret matching.  Bad things in the past get reset, and good things get saved and adjusted.

Look at Rhode Island Hold’em; a smaller game.  Solved in 2005, but takes 2.5 hours to run with that solution.  New solution: 7 minutes.

Additionally strategy includes also dropping data that is “unlikely” to be relevant, reducing the amount of memory needed and the amount of data to process.  When started, the bot plays horribly.  After 4.5 days (many many cpu years).  69 days (900 cpu years) heads us to that “good enough” point where we can claim to have “solved” poker.

Justifying the relevance of this research (beyond being for the fun of it) with an application story…   you are a doctor, and you have to come up with a treatment recommendation for a new patient you don’t know much about, so you start off with some uncertainty.  Could sample something from your sample set of patients.  You can frame it as a game similar to how we represented poker.

“Intent Prediction and Trajectory Forecasting via Predictive Inverse Linear-Quadratic Regulation”

Intent is not just the target trajectory but also the behavior type.  Example of pedestrian movement prediction.   How probable are different behaviors?    Made use of Cornell Activity Dataset (CAD-120), which is a database of videos of various activities, looking to be mostly household.  Dataset includes skeleton movement and object info.  So sample here might be one of cleaning plates, etc off a table.  If recognized in real time, the bot can use predictive information to assist in a non-disruptive way.

Bayesian intention and target prediction.  Approached with Markov decision process, quadratic control for path determination combined with a dynamic based cost function, inverse reinforcement learning.  Have location of objects but not context (plate or microwave platter?).   Have to also consider sub-activity-specific behaviors.  Each gets unique (quadratic) cost functions.

Able to gain a nice set of update rules to allow for fast enough behavior (1000 predictions/sec) for real-time, real-world interventions.  Works best if combined with strong priors.  Future work involves climbing up into higher level activities, actor identification, and actor dependent prediction.

“Model-Based Reinforcement Learning in Continuous Environments Using Real-Time Constrained Optimization”

Quadcopter navigation, 8 dimensional feed.  Should be able to set a higher order objective deployed into foreign environments.   (a little hard to understand speaker)

Use constraints to avoid undesirable states (obstacles, going to fast, incoming ground).  Showed math for in slide given objective, model and constraints.  Use FITC sparse Gaussian processes for learning function.   Use SE ARD kernel for feature selection.  SQP used for NLP, which reduces to a more manageable series of QP problems.  Let first QP converge for locally feasible trajectory, and then “warm-start” QP approximations around the previous trajectory.

Use pole-balancing results for benchmark: good results.  Then test in simulated flight environment.  Applied constraints and dynamic changes in real time: also good results.

“Approximately Optimal Risk-Averse Routing Policies via Adaptive Discretization”

Example of trying to get to the airport on time (relevantly to us conference goers) from the BBQ joint, but you want to maximize your culinary experience time.  Traffic is uncertain.  50% probability of getting there in time at various points in your (common formal) predictive scheme.  Compare fastest expected/shortest path vs best path, etc.   Once you get to another point in time, you can look back at the original prediction and adjust what part of the decision graph you want to go down.  Mostly seems like playing with formal probability so far.  Modeled as a DAG.   Looking at maximum utility to meet end goals.

Approach taken: backwards induction.  For each vertex in reverse topology (from future to present?), calculate best option and expected utility, using Bellman equation to calculate utility.  However, best not to solve the Bellman *exactly* or use time based discretization (might experience gap in utility).  Instead, apply adaptive discretization until the utility gap is less than the delta at any given step.

Experimental results…  done on fairly uniform graphs that *might* represent traversing Manhattan to get to the airport.  So tests kinda limited, but planning to apply to more complex scenarios.

“Easily Accessible Paper: Reusing Previously Found A* Paths for Fast Goal-Directed Navigation in Dynamic Terrain”

Note that this is one of the “accessible” papers in the conference.

Problem: pathfinding in general graphs applied to a dynamic terrain; costs increase and decrease; e.g. mars rovers.  The paper describing A* bot information is relatively unreadable, so trying to make more accessible here.

Generic solution: search and store result in a path.  follow the path to the goal, execute a solution, if the arc cost changes, update the search graph.

Repeated forward A*: shown briefly…

D* Lite:  do an optimized dynamic backward A* and store result in path.  move through path and adjust for unknown object.   Generalized Adaptive A* (GAA*): do A* followed by heuristic update and store in path, follow path, adjusting for arc cost changes.

Showed 2d picture of agent, target and obstacles.  Backward strategy requires knowing the location of the target and where all the obstacles are (it looks like).   Pic of D* strategy space looked like a blob, and the A* looked fairly directed.  However, D* is more efficient because A* has to be repeated many more times.

AA* will improve upon A* by re-using previous search information.   Pseudo code displayed, but font kinda small for my friggin eyes… alas.

Regardless…  experimental evaluation in random maps (random, room, and warcraft maps).  MPGAA* performs faster than the other x* solutions in the random and indoor settings.  Not much improvement over D* Lite in outdoor settings.  MPGAA* in any case is much easier to implement.

“SCRAM: Scalable Collision-Avoiding Role Assignment with Minimal-Makespan for Formational Positioning”

UT LARG dudes.

Role assignment problem.  Assign N robots to M targets into 1-1 mapping so that collisions are avoided while minimizing the makespan.    Can represent as bipartite graph.  Applicable to scenario where using robots to procure items in a warehouse, or robots on an assembly line. Also applied to RoboCup domain.

Minimum Maximal Distance Recursive (MMDR) Role Assignment…  mapping costs calculated, then apply hungarian algorithm.  Translate MMDR into the assignment problem.

Minimum maximal distance + minimum sum distance…

Algorithm is a little dense, and presenter zoomed through it a little quickly, but did indicate that the solution is speedy and scales well.  Showed some results assigning 10 robots in a 100×100 grid, which indicate improvements over typical solutions (greedy, MSD, MSD^2, etc).  Showed animations of paths taken, illustrating significant performance difference.

RoboCup simulation shown as well.  Formations seemed to make sense relative to ball position.  Also showed pre-defined formation movement which included effects of battery drain because of additional work needed to form under other circumstances.

May try to apply to more complex scenarios with obstacles and such, and may also trying applying auction algorithms to the solution.

“Learning to Mediate Perceptual Differences in Situated Human-Robot Dialogue”

Situated referential grounding.  To bot: “get me the black panda on the floor there”.  Bot sees a floor space with all sorts of objects, including a stuffed black panda.  However, there are mismatched perceptions about that space between the human and the bot.  Related work spans from the 70’s.

Focused here on grounding procedure and “word grounding models”.  Reliability of word grounding models can be affected by situational factors.  Propose a weight-learning approach. Can make use of peripheral verbal cues from human (e.g. if two objects look similar, and the human adds “the one in the back”, then probability can be applied to resolve ambiguity), and then use that info to help reinforce general recognition of the type of object.  Make use of graph matching between known and experienced (and maybe predicted?), and adjust weights at the attribute and word levels.  Can frame as a linear programming problem.  Pull this into online learning with human feedback.

“Spatio-Spectral Exploration Combining In Situ and Remote Measurements”

Rover (as in Mars/space Rover) navigation.  Currently terrain priors are pretty low-resolution.  Would like to figure out a sensible way to collect spectra to more accurately reconstruct from imagery and improve adaptive path planning.

Concept of endmembers, similar to PCA, that ideally correspond to geologic materials; hard to determine from orbital pixels.  Determining where would be good to collect a sample to help inform the images is part of the goal.  Rover-based endmembers…   As in, we don’t necessarily know what different colors in the spectral analysis mean.  Collecting samples helps to dispel mystery.

Tested on data from Cuprite, Nevada (has a number of visually distinct spectral classes).  Paths chosen at random, with samples in a uniform grid.  AVIRIS: camera used for capturing high res spectral resolution (2m/pixel); spatial resolution meh.  ASTER: low res orbital spectra (15-30m/pixel) — used to help inform sampling done with AVIRIS.  Tried various planning options (random path, direct path, etc).  MESMA and NNLS performed the best.  Field tests coming in the near future in Atacama Desert, Chile.

“An Entorhinal-Hippocampal Model for Simultaneous Cognitive Map Building”

Brain-inspired navigation.  Study how mammal perform spatial cognition.  Reference to neuroscience work done on the “Brain’s Inner GPS”.   Function of “place cells” in the hippocampus and “Grid cells” in the entorhinal cortex used as inspiration for the development of a model.

Visual => place cells (to cognitive map) => set of grid cells (path integration)…  (accellerated through the slides at this point.  as the material became more dense, of course).

Tested on Pioneer bot with arm.   Live test: build cognitive maps of two indoor environments.  Result images showed neural map responses to different locations in office environment.  Cool video showed neural spikes along with video of bot moving through its environment.

My observations from the 3rd full day of sessions at the AAAI-15 artificial intelligence conference in Austin, Texas.

Intelligent Decisions

I missed most of this particular talk, so a bit of this is second-hand.  Here’s what I’ve been able to gather from it.

Talk is mostly about what has been happening with IBM research, most of which seems to be going down the track of aggregating algorithmic solutions; a sort of overloaded shotgun approach.

Have developed a synapse chip that presents a significant performance improvement that can possibly be applied to neural simulation.

Cognitive systems development.  In practical terms, the design support system is made for working in partnership.  Part of goal is to be able to effectively answer questions that weren’t programmed into the system.  General strategy is to train multiple classification algorithms at once, favor the one with the best upper bound, and have humans interpret the result for feedback.  Cycle of processing: search => read => find => record => aggregate.  User will not provide all of the data, but may relate how to extract more, which can lead to better interactive modeling.

Solution to another problem involved painting a scenario wherein you allow the system to “max out” a budget in order to find a solution to a problem.

Meta-learning:  multiple learners together give you better results.  They, in effect, learn with algorithm works the best for a given input, without interpolation.  Select winner by clustering, etc.  More or less the Watson way, and the Watson Development Platform is available for use.

meinoff@us.ibm.com

“Deployed: Robust System for Identifying Procurement Fraud”

Fraud risk in enterprises.  $3.5 trillion in losses.  18 months to capture fraud on average by way of auditing, which captures only a small percentage.  Average loss of $1 million in 20% of the cases. Clear that opportunities exist to improve.

Taxonomy of fraud events (created by IBM).  Fraud by vendors vs fraud by employees, both often involving collusion; e.g. artificially inflating prices, bribes, lower quality product or service, falsifying performance, fake vendors, fictitious orders, etc etc.  Example of lady in india ordering usb sticks, but would end up getting for free, had access to and would delete relevant boss’s email.  Ended up ordering thousands of usb’s for free and selling.  So WIDE range of cases that need detection.

Example of conjoining events & observations which alone may not indicate anything; e.g. hear fight between husband and wife (happens all the time and not necessarily alert on its own), hear loud noise at night (ditto), see husband carrying bag out in the morning (ditto).  Combined, however, is pretty suspicious.

Here, multiple analytics techniques applied for a procurement fraud analytics tool:

data capture/prep => text analytics => anomalous event detection => social network analysis = importance weighting => unsupervised learning => investigation & alert triggers (scores and confidence levels) => supervised learning

Risk event groups:  profile risk (problems with vendor profile that indicate closer look needed), perception risk (problems with perception of vendor), transactional risk (issues with transaction patterns and history), and collusion risk (problems with relationships between associated parties.

Vendor scoring includes things like registration with Dunn, roundness of dollar invoice, perception index, how well P.O.’s line up with invoices, etc.

Uses sequential probabilistic learning, an “online” learning algorithm, for evaluating collusion.  Input weights and confidences => determine edge probabilities => assign edge weights => infer probability of collusion => output collusion confidence.

Showed to be better than leading competition in solving more types of fraud problems.  Seamlessly combines various models to effectively analyze procurement risks.  Actively, since last year, monitors daily about $45 billion, 65k vendors across the world.  Still a work in progress, but currently is quite useful and accomplishing things that haven’t been done for 15 years.

Then showed demo on real data.  Landing web page is a sort of dashboard of statistics.  Risk analysis report shows word clouds for countries and types of issues, with various filter and NLP options, summary charts, score distribution, country to country risk assessment, etc.

“Emerging: Design and Experiment of a Collaborative Planning Service for NetCentric International Brigade Command”

German, French and US army.   Cooperative planning.  Optimization of collaborative operations.  Information flows very fast at tactical levels.  Using constrained optimization techniques, conducted experiments 2008-2012.

Joint planning today is at the division level and is very slow.  Division decision level 6-8 hours down to platoon or squad which needs decisions like NOW.   Situations involves enemy and friendly forces, of course.  Execution involves phasing and coordination; who’s doing what at what time.  Highly asynchronous and time sensitive.  All sorts of variable aspects; mobility, size, firepower, effectiveness of troops, etc.  Example of embassy taken by terrorists.  Contingencies can cause unintended cross fire between friendly forces.

Created a planning service “ORTAC” that can be accessed by US/FR/GE command and control.  CLP(FD) in SICStus Prolog; involves constraint graph, branch and bound algorithm, predicates and constrained predicates, etc.  Navigation constraint model uses to calculated costs (on timing, security capacity, etc) for paths; more or less a routing optimization problem.  Introduce a deconfliction model to minimize conflicts in the graph overall.  Then apply (global) search algorithm with “probes”: metric computation => relaxed problem solving => variable ordering => branch and bound…  Then tune the algorithm to consider temporal  and spatial deconfliction.

Many participants in the experiment, government and corporate; conflict and threat warning, plan computation and time/space deconfliction/repair.  Can propose alternative “better” plans.   Robots and humans alike considered in deployment analysis.  The paper includes a lot of military acronyms; author says you can contact him if you have any questions.  The experiment  was successful enough to prove feasibility of a system like this, so research and development is continuing.

Questions raised about effectiveness with broken communications on the field…   There’s a political barrier that complicates it; each country wants to control its own resources, etc.  It is something that would involves cooperation at other levels than just the tech.

“Deployed: Activity Planning for a Lunar Orbital Mission” 

NASA Ames research.  Problems/contributions:  LADEE activity scheduling system (LASS) for activity planning to meet deadlines, using AI  to help formulate activity planning modeling and processing to manage orbit; does involve issuing various live commands to equipment on the spacecraft, and can be applied to “snap-to-orbit”.

Mission objectives: examine lunar atmosphere, sample dust.  “Sunrise Terminator” is a position important for collecting data, among other positions with equally interesting names.  Predictions of crossing times important and affect overall planning of spacecraft trajectory.  Variable aspects that had to be taken into consideration in live planning and update to planning included things like purpose of observation, when science activities could or could not occur, multiple concurrent plans that need to be coordinated, etc.  Instrument activity plans have to be coordinated with strategic, tactical, etc activity plans.

Numerous fairly involved, detailed slides of the flow and other aspects shown; will have to reference the paper/presentation.

Showed a number of JPL space projects this has be successfully used in.  Dynamic Europa: automated constraint reasoning system. SPIFe: client interface.  Activity Dictionary: encoded activities. Template Library: partial pre-defined plans.

Didn’t really go much into the actual algorithms or what was novel in terms of AI.  It kinda came across as fairly routine software engineering, and a little bit of a stretch calling it AI.

“Asking for Help Using Inverse Semantics”

IkeaBot (yes, for building Ikea furniture 😉 )

Noticed while testing, noticed bot was flailing.  Solution was to shove it twice.  Not really good solution.  So…  made them think about how to get the robot to ask for help when it needs it.   How does the robot determine what it wants the person to do?  And how does it know how to communicate it?

Looking at prior NLP work…   tried to find crossover solution for two main types of solutions.

Strips style symbolic planner for assembling furniture, includes pre and post conditions.   Can hardcode mappings from failures to intervention methods, but that’s a fragile solution.

Introduce inverse semantics…  involving forward semantics on “groundings”, probabilistic determination of the surrounding objects.  Generation of semantics starting with looking at a context free grammar to describe the language used to talk about the groundings/objects.  E.g. “hand me the (most likely the) white leg (that I need)”.  Suggests that the formula presented (a product over a sum*product) for inverse language understanding *is* language understanding (seems a little stretchy).

Tested, of course, by introducing complications for the IkeaBot.  Initial success rate was relatively low (20%-50%).   Human written got high rate (as a control?).  Inverse semantics approach reached about 64%.

Collaborative planner infers human actions needed to help robot, and generates natural language, and mathematical framework unifies  language understanding and generation.

“Learning Articulated Motions from Visual Demonstration”

Motivation: want robot to understand the underlying kinematics of objects in a household environment.  Doors, cabinets, trash cans, faucets, knobs, etc.  How does the bot learn these things?  An option is to mark objects in the environment, but this obviously doesn’t generalize beyond specialized environments.  Would rather them learn in an unstructured environment with humans roaming about.

RGB-D as input only.  Trajectory construction: extract features and motion over time.  Trajectory clustering:  collect into object parts .  Pose estimation: can be noisy, but observe and predict possibly movement for the parts.  Articulation learning:  learns movement.  Object model persistence: remember what has been learned in a way that can be used in other environments.  Predicting object motion.

Qualitative results:  train in one room with a set of objects.  Then take into another environment with similar objects.  Compared to state-of-the-art, this solution provides more robustness, better fidelity and accuracy of motion, show that over 43 different test environments, successful over 2/3 of the time.

Recent work:  learning done with a human co-operator, which seems to be pretty effective in increasing smoothness and accuracy by way of observation of aided movement.

“Tell Me Dave: Context-Sensitive Grounding of Natural Language to Manipulation Instructions”

Common scenario is to give a grounding command to a robot, and it has to interpret it correctly and do something intelligent.  Problem with grounding is converting a command into an action plan/sequence of actions.

Example.  Making sweet tea => “Heat up a cup of water, add tea bag.  Mix well.”.  So in the environment there’s a table, a cup, a microwave oven, a stove, a sink, etc.  Many instructions presumed and missing from the action description.  Command also may not be in sync with the environment (might not be a cup, but *might* be a glass or something “close enough”).  May be a multitude of ways to perform the task (e.g. multiple vessels, a microwave or a stove?).  So the grounding is subject to all of these circumstances.

Common approach is to define action templates.  However, fragile and typically doesn’t handle ambiguity or many to many situations well.  E.g. “heat cup of water” vs “heat cup of milk”.

Another approach is to create a search path (a graph/tree).  However, search space can become exponential.

Proposed here is a learning model (CRT with latent nodes).  Clauses.  E.g. “get me a cup” can be scoped in the tree with feedback about what’s available in the environment.  Model solved using VEIL-template, which appears to be a function of the clause + environment  + instruction sequence template + original object mapping.

Created an online gaming environment (crowdsourced testing).  Able to collect 500 real templates by recording movements made by online users (I think).   Those templates went into training the bot.  Results show that robot is able to “fill in the gaps”, and shows 3x improvement over other solutions.  Video showed a bot cooking and serving a meal, which was kinda cool.

“Learning to Locate from Demonstrated Searches”

Elderly care scenario.  Want robot to find grandma’s glasses.  Want this to happen for any grandma.

To make this work, would like this to be applicable in an optimal way in a novel environment.  Introduce notion of “priors”, which are, e.g., beliefs about the likelihood of an object being in a particular place.

Given a location, then target probability distribution, then figure out an optimal search plan.  For each location we have some features and determine a log probability.  All we get to observe are “pasts” prior to our current situation.  Scores end up being time-optimal search stories.  Learning algorithm is iterative, starting with some weights.  Make adjustments with feedback.  Expected time to locate the object is part of what’s fed into the inference engine.  “bag of words” technique used to capture/represent features.

Naive approach equations shows in contrast to better approach that involved “transposing sums”.  As well…  “admissible” heuristics are derived from “relaxations”.  Introducing these sorts of heuristics shows good results as the complexity of the scenario scales up, by a factor of 10.   Basically these changes shifts the search path to try the “most probable” locations first.  While not purely optimal, results showed what a human would perceive to be near optimal (and I guess not totally dumb; e.g. robot: “glasses?  I’ll check the fridge!”).

“Fully Decentralized Task Swaps with Optimized Local Searching”

Multi-robot task allocation.  Which bot should do which task?  Applicable to many scenarios; e.g. warehousing, robocup soccer, etc.  Generate a task cost matrix.  Translate into assignment matrix.

Background for task swapping…   minimize total travel distance.  Start with initial assignment.  Update by swapping if not optimal.  Use duality to optimize the solution.   Use only local and single-hop communication (instead of global).  Idea is to decompose the global solution into localized bits.

“Toward Mobile Robots Reasoning Like Humans”

Robot teammates with humans.  Semantic navigation, search, observe, manipulate with autonomy, natural communication and explanations of “why”.  A bit of related work cited that applies to just about everything described later.  Work is centered around perception.   Example: “stay to the left of the building and navigate to a barrel behind the building”.  As humans, we can immediately upon seeing the building imagine a barrel behind it.

This approach mimics that behavior.  Semantic classifiers applied to 2D visual image, then use that to generate 3D label points, given the resulting “plane cloud”, we predict a “building”.  Based on the predicted building, the bot “hypothesizes” a barrel behind it.  Robot can then generate path with pref to left side of building, per the command.  Adjusts and corrects prediction as it moves.    Introduced architecture (lot on the slide), includes world modeling, navigation, path planning, search actions, NLP, etc.

Semantic classification tries to label regions with a pre-defined set of labels.  From there, cluster 3D objects, applying labels tempered by bayesian probabilities and field of vision limitations.

Imitation learning is used to teach spatial relationships and models of environment.  Show the robot what it means to navigate in different environments.  Robot extrapolates and weighs features for future use in live environment.   Hypothesizing the unseen environment involves summations; equations shown, along with live environment examples, along with a crapload of small font sample commands, etc.  During tests…  35 of 46 tests were successful.  Some tests with bad commands excluded.  Videos shown of real robot and interpretation of what the bot sees… going around the building, ignoring a fire hydrant, ignoring a barrel that’s not behind the building, and navigating to the barrel behind the building.  All from a real robot over gravel and bumpy terrain.

“Learning to Manipulate Unknown Objects in Clutter by Reinforcement”

Autonomous robot for rubble removal.  Major challenge for search and rescue.  Previous work achieved 94% success on regular objects, 74% with irregular objects.   Added strategy of pushing objects.  Wanted to be able to get the robot to learn without any human intervention.  Involves a lot of random interactions; a lot of trial an error.  All by trying and observing success.  Video shown of it in action, touch, touch, move box, move cylinder, push cylinder, pick and move box, pick up and move cylinder.

Unreadable slide of overview of the integrated system (thin, small yellow font on blue rectangles), and MC Botman in the house overloading the microphone…  will have to see the paper.  Something about clustering and segmentation of surfaces into objects, then breakdown into “facets”.  Looks like this led to the bot translating visual image into conceptual mapping of disparate non-uniform objects.  Touch and push appears to play into extracting features of the object, though it doesn’t look like tactile sensor based; rather success or failure of grasping.  Functions shown for action evaluation, and yes it does appear to be a matter of iterations evaluating push-grasp feedback.  Bandwidth selection equation shown that makes use of a “Bellman error” to adjust predicted.  Plus makes use of reinforcement learning.

“Learning and Grounding Haptic Affordances Using Demonstration and Human-Guided Exploration”

Humanoid bot, Curi.  Learning from demonstration.  Human guided exploration.  Involves: action demo => human guided exploration => affordance model.

Video shown.  First assist Curi by physically hand-holding the action.  Then bot tried on own a few times, but with a little bit of corrective assistance.  Then create affordance model; 2 markov models…  successful trajectories vs failures.

10 successful, 10 failed cases.  Feed into offline classification.  Precision is generally higher than recall.  Skill with best performance have distinct and continuous haptic signals.  Online testing involved variations, and successful 6 out of 7 times.  Curi detects shake top affordance, pour top affordance…

Note that no visual information is actually recorded, just trajectory information…  (hrm…)

(note to self: Curi’s approaching the uncanny valley (observation from video).  And ignoring visual info (going blind basically) seems pretty limiting and difficult to generalize from).

“Apprenticeship Scheduling for HumanRobot Teams in Manufacturing”

On verge of a revolution in manufacturing in that we will see more robots and people working together.  Early or lateness, broken parts or tools introduce complications.  How do we do this efficiently?  How do we allocate authority over workflow?   How do we handle implications of adoption?

Task allocation, ordering of tasks, timing of tasks (duration), balance, deadlines, agent capabilities, etc etc…   Tercio introduced.  Uses heuristic techniques among other.

Looking at human acceptance of this, tested on two humans, two robots.  Fetching tasks.  Assembly tasks.   Only the humans can build (legos).   Team efficiency was better if the bot had more control over the flow.  Plus the humans liked handing over some of that control to the bots.  Further examination of that shows that people preferred robots over human control.  So further questions include how to have robots coordinate teamwork.  Regardless, figuring out the psychology of this is something worth more study.

(Note to self: implications of where this heads is scary and seems wrong.  Egads.  Regardless, figuring out the psychology of this is something worth more study.)

“Following a Target Whose Behavior Is Predictable”

What makes a good robot videographer?  E.g. motorcycle jump video, sports, political events, etc.  Line of sight, viewpoint.  Good camera settings and beauty too, but focus on the former.

Video shown of underwater bot following a yellow target.

Robot needs to retain a belief about target, anticipate actions, search for target, consider dynamics of environment.  Range from fully cooperative to fully adversarial targets.

Modeling the target…   compute cost to go, giving pref to single path.  Incorporate speed of convergence to the goal, somewhat relative on the rational behavior of the target, and include perceived rationality of the target into the equation.  Particle filter applied.  Cast as a finite-horizon POMDP problem.  Robot has limited time to compute, so use monte carlo tree search.  Each node maintains times visited and expected reward.

Animation shown of agent pursuing target in a maze.  Seems to still be able to follow even when the target is out of the line of sight / field of vision.    Still work to be done, because apparently there are some performance issues, etc.  Not really scalable.

“Multi-Agent Rendezvous”

E.g. automated taxis meeting to load balance passengers, or an underwater vehicle near a surface vehicle.  What’s the best strategy for solving the task?   Goal: minimize time and resources for rendezvous.  How much prior knowledge and communication is there?  What if it’s an unknown environment?   Compare to how humans do it.

Bots discover their environment as they go, eventually encounter each other.  No prior knowledge or communication.  Introduce cost-reward model and “distinctiveness”, which represents expensive choices.

My observations from the 2nd full day of sessions at the AAAI-15 artificial intelligence conference in Austin, Texas.

“Statistical Parsing with a Context-Free Grammar and Word Statistics”

(no show)

“Task-Oriented Planning for Manipulating Articulated Mechanisms Under Model Uncertainty”

Task of cooking involves many subtasks.  Many household objects have mechanical constraints: “articulated”.  Here we’re looking at learning the kinematic structure of an objects.  Use task-drive to help motivate and guide the learning.  Graph representation, vertexes and edges representing joints, shape, etc, as generalized kinematic graph.  Given some number of candidate models, find minimal cost to achieve the goal, involving user-defined cost.

Belief MDP…   Assuming we can assume no noise in observation, and perfect motions, we can construct a sound logical space.  Observes environment, generates plan.  Learning is supervised in that the robot will know about and have prototypical concepts for drawers and doors.

Experiments conducted in office and kitchen spaces.  Videos showed success finding and opening various cabinets and doors.

“Learning the State of the World: Object-based State Estimation for Mobile-Manipulation Robots”

Creating semantic world models.  How should a robot represent its spatial environment?  Object-based spatial representation using attributes… what and where?

Say a robot captures image of objects on a table.  Apply object recognition processor…  identify box, etc.  However, object detection is noisy, misinterpreted, occluded, etc.  Then can possibly combine partial views to form hypotheses about what’s on the table.  Becomes a data association problem.  Can use crossover clustering to help association accuracy.

What representation should be used?  Object as atom?  Occupancy grids?  Why not use both?  Fuse together on demand as needed.

Example shown of a toy train behind a board.  Robot arm can sweep behind the board (?)

Scaling this up has issues, of course, but much of it is irrelevant (what you can’t see) and doesn’t matter.  Instead, the estimator should be tied to the task, but flexible enough to be tasked on the fly.  As in, the bot would generate an estimator for a task.

“Time-Optimal Learning, Exploration and Control for Mobile Robots in (Partially) Known Environments”

Robot knows there are objects in a space, but must find them.  Circular sight range.  Assume that bots pick up objects automatically, and that detection is instantaneous (to simplify computations), and uniform distribution over the space.  (Egads, highly constrained to help the study)

Two approaches tried.  One heuristic worst case and heuristic probabilistic optimization, using decision trees, and exploration to action cycle.  Given all the constraints, able to create a sound logical model (note to self: isn’t this part of the general problem in AI that we try to fit problems into sound logical models?)  Showed various paths taken in either case, and that the probabilistic version performed a little better (moving in a spiral).   Can solve an approximate version of the OCP problem (non-convex).

“Plan Execution Monitoring through Detection of Unmet Expectations about Action Outcomes”

Intelligent behavior via accurate model.  Case in point with RoboCup robots.  Many models used:  optimal attack location, opponent marking, ball and robot motion.  Works well if we have accurate models to work with.  However, cannot always fully explore domain before deployment.  Especially in adversarial or human environments and domains.  In some cases too dangerous to deploy and test.  So how to go about it?

Can possibly create “generally accurate” models with anomalous subspaces.  Still applicable to RoboCup, in which case it depends on the opponents and how they play.  What do you do if there’s a subspace wherein the bot is totally inaccurate?

Introduce into the sense-plan-act loop: the planner will also generate some expectations and monitor/correct based on observations/feedback.  Optimization applied to identify and correct anomalous subspace regions.  Using elliptical parametric subspaces, nonlinear optimizations, and a cost function (likelihood of anomaly over probability of anomaly).

Focusing on anomalous subspaces acts as negative feedback for learning.  Showed various animations of their own bots learning off each other.

“Representation Learning for Robotics”

Can call it “feature learning” or “learning to see”.  Showed animation of blurry visual feedback that came from a bot with 4 cameras trying to navigate in a box with different colored walls.  The blurry image showed how vague the visual field is when interpreted by the bot.

Idea is to take this blurry observation and map it to a state.  There’s a learning objective applied, with punishment and rewards applied (reward being a corner).  Still supervised, but does convert raw visual imagery into an internal map of the walled box space.

Added “distractors”, a.k.a. obstacles.  Relying on observations solely, not great.  This new method performs as well as introducing “cheat” information about the environment.

“A Divide and Conquer Approach to Control Complex Continuous State Dynamic Systems using Hierarchical Reinforcement Learning”

Imagine Mario trying to drive around a track.  Continuous space, x, y, direction, velocity.  Typical reinforcement learning leads to consistent mistakes.  If you discretize/decompose the track, with assumed hierarchy.  Completion function is used to re-asses what’s left after a subtask is completed.  As well, divide the regions of the termination step, with multiple policies for each region.  So then it becomes a matter of picking a particular exit region to aim toward.  Reduces the solution space, so easier to solve.  Reasonably successful, but still not optimal, and errors introduced in a non-simulation, continuous environment.  Plan to extend this research to pole balancing and real bots.  Currently using a road bot in a track.

“Towards a Programmer’s Apprentice (again)”

Revisiting the original paper of same title from 1974.  Motivation is to give aid to programmers; e.g. go back to old code or get code piled on to you, and think…  Why that way?  does it work?  etc.  Speaker formerly with Symbolics, etc.

Example: the mailer bug.  Mail would just stayed queued for no apparent reason. Had lunch with original author, who remembered the bug.  As in “oh yeah, I remember that”.

Problem:  software systems last forever, continually evolving, break, design rationale lost…  so could a computer help?  Concept of an apprentice working with the programmer, but in such a way as to capture the rationale; e.g. asks about the stuff that’s not routine.  Programmer, draws, points, codes, talks, etc.  Project to solve this problem started in 1974…  Developed plan calculus, temporal abstraction, cliche recognition, etc.  In emacs!!!

Why revisit now?  Computers are better now, various technologies have improved, and massive open source libraries to reuse.

Prototype now uses Siri and Start natural language system to gather input.  Involves cliches, taxonomy, viewpoints of the data, code generation and refinement.  Runtime is a temporal sequence state machine of sorts.  Examples…    encounters code that intends to represent pixels as bytes, refines and generates code that works.

Video demo demonstrates emacs talking to the programmer, asking questions.  User says “add a disk drive”, and then corrects the user by saying that the data types in his design are not matching up.  In another case, user asks to generate pixels for some data, and the bot asks how user wants to do it, asking why once the user has made a choice.  Kinda cool.   Synthesized code is in lisp.

“Conducting Neuroscience to Guide the Development of AI”

Many people pursue AI as way to understand how the brain works.  Rather, here suggesting that we use tools and research of neuroscience to make more intelligent systems or dispel any illusions about AI models being accurate.  So, along those lines, what we usually do is feed input to computer, get output, then feed input to person, get output.  But we can’t answer the question about whether what the bot did == what the human did.  Still no idea what was going on in the human brain.

Interface between language and vision as a focus here.  Action recognition and video captioning.

Action recognition: Take video data and map to fixed set of concepts; e.g. a video of a kiss ==> “kiss”.  Typical way…  extract space time features, classify with SVM, etc.  Questions…  how does this compare with the human brain?  Well… MRI scan the brain with the same input, and compare.  And of course, they compare poorly.  Explore more…  does the brain pool features?   MRI scans once per two second time resolution, which is slow, but can improve to 300ms, which improves possible results because of the importance of hitting the critical identifying moments.

Video captioning:  Video clip input ==> speech text output.  Solutions use priors from web scale natural language corpora to determine likelihood.  However, is this what the brain does?  Probably not.  Accurate?  Only if your video clip happens to hit the right probability.   Again did MRI scans to find active regions and crossover between.  And compared.  Not really similar.

“Mechanism Learning with Mechanism Induced Data”

Mechanism design in internet applications with multiple agents with independent intentions and self-interest.   Context of crowd-sourcing, search ads, and app stores.  Users <==> Platform <==> Agents.  Agents may be pretty irrational, but some consistency in behavior.  Note that this is from Microsoft Research.

Game theory assumes rational behavior. Machine learning has unknown, but fixed distribution.  So…  quandary is in dealing with a combination of bounded rational and mechanism dependent behaviors.

Introduce MLMID as a hybrid between game theory and machine learning.  Even with irrational behavior, there will still be patterns, plus changes in behavior depending on circumstances that can be recorded and used in a probabilistic model.  Take into consideration evolution of user behavior as well.  Strict use of previous history may not be effective.   Make use of “regret” and “equilibrium” analysis.   All very complicated, however, and really there are just a lot of open questions.

“Challenges in Resource and Cost Allocation”

Food banks in Australia and worldwide.  Using technology to do good in the world.  In this case, creating an app to help people both donate and receive food.  Technology-wise, this becomes a resource allocation problem (similar to vehicle routing problem, which is more or less a variation on the np-complete traveling salesman problem, etc).  Great bit of complexity added with a number of constraints and granularity of items that can be distributed, money available, etc etc etc.   20k customers, 600 vehicles, $100’s million+, etc.

Challenges:  development of complex models and mechanism for fair division, mixed fair divisibility, optimization, and behavior awareness (not everyone behaves fairly or rationally), cost allocation mechanisms, etc.   And the whole domain of the environment is constantly changing. (note to self: seemed to miss reacting to delays and other extenuating circumstances)

Benefit to food providers is that costs can be cut in half if done right.

“Explaining Watson: Polymath Style”

Why does Watson work well?  Not standard NL research.   Despite it’s success, we still don’t know why it works.  Figuring it out can be an open collaborative effort (“polymath style”).

Why do we care?  Seems to be a mismatch between our theory of meaning vs what we’re experiencing with Watson.  In the Jeopardy Challenge, there are 5 key dimensions…  broad open domain, complex language, high precision, accurate confidence, high speed.  Some questions are not encyclopedic that can just be looked up.  Regardless, can sort of be considered solved as of 2010.  Watson became the first non-human millionaire by winning Jeopardy.

Four years later, and Watson’s accuracy no replicated yet (something like 75%), even on factoid questions.  Unlike Deep Blue, after which progress in chess playing increased.

Watson has two search engines.  Analyses question ==> decomposes query ==> –2x split here– hypothesis generation (primary search with candidate answer) ==> soft filtering ==> hypothesis and evidence scoring (supporting evidence lookup and scoring) ==> –join split here– synthesis ==> merge and rank hundreds of scored items (logistic regression applied) ==> answer and confidence.   Dozens of NLP models used in the process.

So… where’s the meaning in all of that?  We get the impression that the meaning is understood somewhere in there (the ghost in the machine).  No formal model or theory.  IBM has published it in the IBM research journal, so how Watson works is open to play with.  Offered some possibly research paths that could be taken.  Can contact them if interested in doing related research.  Opened up to public because they are not seeing any replication of this sort of tech in the academic community.

Deep Learning 

Presented by Geoffrey Hinton, of original backprop and boltzmann machine fame.

What is deep learning good for?  Distinguish structure from noise.  Example problem: pixels to words.

Backpropagation had a bit of promise, but didn’t make good use of hidden layers.  Couldn’t get it to work effectively for recurrent neural networks.  RNN’s held hopes of being able to combine in mass to help solve problems.  Regardless..  what’s wrong with BPNN?  Required labelled training data.  Very slow to run.  Only found local optima.  Often good, but otherwise really inaccurate.

Attempt to overcome by using unsupervised learning.  Make use of stochastic binary units  Then hook it together to form restricted Boltzmann machines.  With one hidden layer, the chances of one feature detecting unit can be independent of other units.  Hopfield energy function applied to determine weight of a joint configuration, and the derivatives are useful for defining probabilities.  Go back and forth training vectors until activity stabilizes.  Applied to learning to model images from video data.  Problem, however, is that it’s horribly slow.

However, the RBM can be improved.  Corrupt the data with encoded “beliefs”, then reconstruct, then take the difference and learn from that.

Training a deep network:  Based on this RBM, more or less.  First train layer base directly on the pixels.  Then treat the activations as if they were pixels to learn features of features, creating a multi-layer generative model.  Apparently it’s provable that each layer added leads to a better variational lower bound variability.

Then… fine tune for discrimination…  and use BPNN to pre-process data (I think).

Example application to acoustic modeling using a DNN pretrained as a deep belief network.  Last year all good speech recognition apps were using this.

How many layers?  How big?  Backprop works better with greedy pre-training, and for scenarios with limited label information.

stuff ==> image ==> label.  This is typical, and is what commonly leads us to focus on the gap between image and label.  However, seems sensible enough to go from stuff ==> label directly.  Unsupervised pre-training not necessary for optimization, but helpful for generalization.

Success achieved with ILSVRC-2012 competition on ImageNet.  1.2 million images, 1000 classes of objects.   Goal: get correct class in your top 5 bets.  Other groups looking at 25%-30% error.  This solution is hitting 8% error.  Architecture used:  7 hidden layers (most recently using 20), early layers convolutional, last two layers globally connected, activation function is rectified linear units, global layers had most parameters utilizing “dropout”.  Example images shown, with confidence list.  Dropout involves randomly omitting units, which helps to retain some of the information already learned.

Again…  what’s wrong with backprop?  Misconstrued before.  In retrospect:  too few labels, too slow computers, stupid method for initializing weights, used wrong type of non-linearity.

Back to RNNs. Hidden layers feed into themselves, can take input or output at any time slice, etc. Powerful because they combine distributed hidden states that allow them to store info about the past efficiently and non-linear dynamics that allow them to update…  AND if they’re deep, then they work better.  Applied to doing machine language translation, using hidden state to represent the thought that the sentence expresses.  Take that “thought” state vector and feed it into the “french” translation RNN.   This solution beats state of the art now.  Goal is to create a real babelfish on a chip that goes in your ear.

Then…  combine vision with language.  Train the RNN with vision percepts.  Tested on a database from Microsoft of 200k images with captions.  Successfully trained on this data, was good at generating sentences for images.   All done without symbols, etc.  Suggested that this is really bad news for GOFAI.   Connectionist vs Symbolist — FIGHT!  Hinton’s being pretty forward about denouncing people who keep using symbols in knowledge representation; that symbols are only input and output.

Audience…
– Rebuttal from GOFAI:  defending ability of humans to use formal logic even if it’s not part of the basic way we work.
– Can get NN to learn mathematics and perhaps interpret code.
– Smolensky brought up as someone who worked on Boltzmann machines, but has been pursuing more symbolic solutions
– Thought experiment: black box that sorts numbers.  Whether or not there is a NN on the inside does not matter.  Arguing that we cannot conclude that there are not algorithms in the brain

Hinton was more or less saying that most people here are probably wasting their time if they’re still dabbling in GOFAI.  What he says about symbolic knowledge rep with classical logic reasoning frameworks is pretty obviously correct: it’s not how our brains work.

“Spontaneous Retrieval from Long-Term Memory for a Cognitive Architecture”

Knowledge search heuristics…  e.g. “find an item that has a solid line and ends in a square”.  What if the agent doesn’t have any of the basic knowledge in the first place.  Doesn’t know cue, cue relationship, when to search, etc.

Applied to missing link domain, remote associates test.   Agent gets some words as a clue, then has to look up associative words.  Assuming imperfect associative information, with no pre-established relationships, introduce “spontaneous” retrieval.  Results show that this solution helps in some cases, but does not do any worse than typical solutions in other cases; so it only improves.  For cases in which puzzles are not solvable or there’s no good solution, the spontaneous solution performs faster and does just as well.

“Automatic Ellipsis Resolution: Recovering Covert Information from Text”

Ellipsis, in the sense of …

or [e] or “what we didn’t do”

Confounders…  a lot of syntactic and other world make many assumptions about the correctness and completeness in the environment.  This group intends to handle actual natural language.  Question to investigate here is to see to what extent we and explore situations with incomplete, dirty data baby.  With focus on resolving syntactically incomplete sentences (with ellipses).

Processing cycle:  (showed slide for 1 second, alas)…  used standard input processing, then applied removal of false positives, ordered matches with level of confidence (using phrasals, parallel configurations, non-parallel matching modalities, etc).  Some challenges experienced after detecting antecedent clauses.

Unclear what the results were or indicated, but expressed that it would hopefully help inform agent decision making.

“Automated Construction of Visual-Linguistic Knowledge via Concept Learning from Cartoon Video”

KidsVideo project.  Representing and learning concepts from kid videos.  Many aspects to consider.  Multimodal, vision, language, story lines, grammar, etc.  Previous approaches include semantic networks, etc.

Solution involves image pre-processing, multiple abstraction layers, sparse population code (hierarchy free brain inspired representations), deep concept hierarchy of cartoon videos using SPC models, empirical distribution of a scene utterance pair, graph monte-carlo (stochastic, with numerous sub graph methods-UGMC, PRGMC, FGMC), etc.  Generates a multimodal concept map, which includes formation of character property classification and recognition.

Results seems to include success in scene to subtitle determination, generation of images associated with given sentences.

Note: very dense material for the short amount of time to present, so it went by a little fast.

“Ontology-Based Information Extraction with a Cognitive Agent”

Problem is looking at text from family/genealogy history books, taking it and populating an ontological model to gather meaning and establish meaningful relationships.  How can we determine who’s who even within the same family article?  Probabilistic models applied to determine likelihood that two symbols may represent the same referent.

Introduce “Ontosoar” architecture, which is a combination of off-the-shelf and some new home grown components, including a semantic analyzer.  OntoES used to help tie things together.

Notion of construction grammar.  Form patterns are constructed and matched against inputs to determine meaning.   Translated into a knowledge structure, with deduced relational links.

Tested against real genealogy sources, got mostly good, but some mixed results; accuracy checked against human interpretation of the sources.

“Extending Analogical Generalization with Near-Misses”

Learning from structured examples.  Extend analogical generalization with “near-misses”.   Introduce “ALIGN”: analogical learning by integrating generalization and near-misses.  Involves generating hypotheses and refining or filtering.

Applied to recognizing structures (relatively geometric).  Assume some generalized contexts; e.g. for “arch” concept, etc.  Case libraries exist for each case (?).  Pseudo probabilistic methods used to extract hypotheses based on analogy.   Relatively good success rate.

“Learning Plausible Inferences from Semantic Web Knowledge by Combining Analogical Generalization with Structured Logistic Regression”

Problem:  learn to do inference on structures, with all the issues people run into using traditional methods that assume no noise or a sound, complete system of some sort.  Trying to overcome issues with incomplete, noisy data.   Solution tries to combine structural alignment with statistical learning.  SLogAn: structure logistic regression with analogical generalization.

Test example…   use semantic web to gather information to infer information about family relationship.  Preprocess structure, then apply analogical generalization, then make weight adjustments with structured logic regression…   can then do a structure mapping between input and a template.

Compared to state of the art classification models.  Better results that even some NN solutions.

My observations from the 1st full day of sessions at the AAAI-15 artificial intelligence conference in Austin, Texas.

Hot Talk: General Game Playing

This talk involved taking a look at the utility of using game playing as an outlet for proving out AI.  Gave contrast between typical approaches that presume too much, but more realistically have to consider things like incomplete game trees, lack of prior knowledge of problem space, etc.  2007 brought us the effective Monte Carlo search.  Various ways cited to pre-process info, different types of games, segregating concerns, etc.

Hot Talk: Robocup @ Home

This was an overview of research that is being done testing robots in real human environments; e.g. coffee shops and malls… getting a beer, carrying a tray, by request, etc.   Emphasis on working out the kinks with human robot interaction, maybe dispelling some of the fear.  Involves combining of many many aspects of AI; semantic 3D mapping, etc.

“This Time the Robot Settles for a Cost”

This paper on temporal logic planning involves simulating janitorial robot in an office, with a list of tasks to accomplish.  This solution tries to bridge the gap between the ai and robotics approaches.

Approach in robotics:

• continuous motion planning
• LTL is defacto language

Approach in AI:

• discrete planning
• pddf is defacto language

Solutions tried involved translating “co-safe LTL” into DFA.  Information flows as: high level planner -> synergistic planner -> low level planner.  Problems come into play in the form of closed doors (closed connections/edges)

Example: to bot: “don’t step on carpet with dirty feet (until you have slippers on)”.  however, carpets are between bot and slippers…   leads bot to ask user question.  user in this case replies by assigning a “cost” to stepping on the carpet.  becomes a shortest path problem with cost applied to paths, as a matter of ‘least cost of violation”.

Animation of the path taken by the bot seem decent.  Can see that the bot handles exceptions; e.g. closed doors, etc, on the fly.

(note to self:  can almost see value, implied in the government funding meeting, in refreshing knowledge with new generations by allowing them to run through experiments that use the same techniques as 20 years ago.)

“Strong Temporal Planning with Uncontrollable Durations”

How to deal with temporal planning that is subject to tasks that may or may not take a certain amount of time…

• actions have durations
• conditions can be non-instantaneous
• effects at-start and at-end

PDDL used as language for.

Solutions tried are extensions of “forward state-space temporal planning”.  When introducing uncertainty of task duration into a plan using standard FSSTP, trying to get the system to re-order constraints doesn’t work.  You get an incomplete solution, even when the algorithm tries to re-order tasks to suit the overall goals.

Tried a variety of ordering techniques to use within the main technique…  landed on disjunctive ordering, but ended up being really slow.

Note:  Dude kept throwing around acronyms.  Colin, SMT, DR, TO, LAD, etc, and was not particularly good at explaining the research

“Robustness in Probabilistic Temporal Planning”

This research involved multi agent scheduling. How do you tell how good a given schedule is?  Solution uses robot create platform and probabilistic reasoning techniques.

iRobot example video shown, avoiding collision with each other, with some level of communication between.

Given a simple temporal network (nodes = events, edges = diff between events), there’s a challenge in responding to new constraints in real time.  Introduce “flexibility”, where naive flexibility is when you sum up all possible events.  Problem with naive flexibility is that it double counts events, so devised a way to minimize duplicates.

Questions arose:  How do we define what’s “good enough”?  When is flexibility more relevant?  What are the critical moments?  This led to a solution that involved moving integrals, but that ended up being to complex.

So… introduced “sampling approximation” and “representative approximation” as ways to add robustness to adaptive approximation of next move.  In the case of sampling approximation…  as it comes to the first edge, it takes a sample, which propagates changes to constraints.  Success or failure (as in, whether or not there was a collision or either failed to reach their destination) is used to train for the next time around.

Brief Planning Oriented Poster Previews:

NEXT:

Resolving Over-Constrained Probabilistic Temporal Problems through Chance Constraint Relaxation.  Involves a bus schedule problem, wherein, for example, I am leaving office for home at 6pm.  Complications in planning involve determining probability of a bus arriving on time, etc.  Found that by relaxing some constraints got better solutions.

NEXT:

“tBurton”: A Divide and Conquer Temporal Planner.  Involves factoring the planning problem into bits, planning using heuristic forward search, merging child plans by de-conflicting sub-goals, etc.  Ends up performing better than state of the art heuristic planners.

NEXT:

Take a general maze plan.  Drop an agent with a camera and non-precise actuators into the maze.  Goal is to send a policy into the agent to reach probability of 1 that the bot will get out of the maze.  Results showed that  positive, negative and approximated costs all play into good results.

NEXT:

SMT based nonlinear pddl + planning.  Couldn’t tell what they accomplished other than munging translation between knowns methods.

NEXT:

Crowdsourcing action model for planning (no-show)

NEXT:

This paper involved dealing with large number of sensor resources and how to allocate them; e.g. sensor systems like multi camera systems.  Becomes untenable, but introduced a “greedy” bpvi as a way to solve this.

NEXT:

Transition constraints for parallel planning.  Investigated various different models.  Created new encoding that encoded constraints better and made use of Minion to come up with better plans using the new constraints

NEXT:

This involved planning with multiple objectives; specifically semi-autonomous driving.  Initially you sequentially order objectives, then introduce “slack” deviation from optimal.  References change as driver slips from “attentive” to “tired”.  Data used from open street map.

NEXT:

Discretization of temporal planning.  Involved developing conditions for breaking timeline into discrete segments to improve scalability of planning.

NEXT:

Chance constrained scheduling.  Used new technique to assess temporal risk of a plan based on conflicts that arise.  Circular ordering of processing: temporal plan – > allocate risk -> conflict -> check controllability -> check policy -> extract conflict -> (back to start).

NEXT:

Hybrid models from guarded transitions.  JMLS insufficient. PHA better, but doesn’t learn as well.  Uses classifiers from machine learning to help train.  Tested on target tracking.  Showed significant improvements over existing systems.  Applicable to activity recognition (on going research).

NEXT:

Multi agent epistemic planning as classical planning.  Reasoning about the states of other agents from perspective of a single agent, uses modal logic axioms, states in classical method, etc.  Addresses plan synthesis based on perception of state of other agents, and employs conditional mutual awareness.  Applied to a classical gossip problem.  Focuses on belief instead of knowledge.

“Probabilistic Attributed Hashing”

Applied to binary similarity; e.g. representations of images, music genres, paper authors, etc.  Involves large scale approximate nearest neighbor search.  Preserves similarity using Hamming distance.

Purports, by way of attributes and content features, to capture human cognition more accurately.  Introduced generative model to deal with scalability problem.

To capture heterogeneity of attributes and content features, applied hashing with separation and gaussian distribution.  Algorithm shown, but would have to look at in more detail.  Kinda zoomed through it.

Tested against DBLP authors database and NUS-WIDE images with tags from Flickr.  Showed 10% performance improvement with this research, goal being to build a better hash function, it seems.

“The Boundary Forest Algorithm for Online Supervised and Unsupervised Learning”

Problem is to approximate complicated functions.  Applicable to many complicated functions, including robotic control, vision, etc etc.

Online algorithm performs effectively and efficiently.  Uses boundary trees (as applied to condensed nearest neighbor problem), and incrementally builds a graphical structure.  Sort of monte carlo style, samples points and classifies incrementally as new points are added.  Animation of the process shows the algorithm eventually (after 10k sample points) capturing the pattern in an original image.  Better performance came by forming a “forest” of these boundary trees.  Faster and more accurate.

“Lazier Than Lazy Greedy”

Big data searching.  Goal is to select a small representative subset out of a large data set.  Typical solutions are subject to diminishing returns.

Greedy algorithm tags elements as it passes through the dataset, picks the one with the best score and adds to the solution set.  Then repeats runs through.  However…  the greedy algorithm can be untenable, performance-wise.

Lazy greedy algorithm is an alternative.  Does a first pass, then sorts according to last scores, forming a high-score subset.  On subsequent passes don’t go through the whole set.

Stochastic-greedy algorithm only scans a random subset on each round.  Can reduce to O(n log 1/e) vs the O(n * k) of the original greedy algorithm.

Experimented and compared to a variety of algorithms, including random selection.  Applied to non-parametric learning in massive data sets.  Stochastic-greedy had the best utility (accuracy) to cost factor.  Tested successfully on set of 10,000 images with 3072 attributes, and “Battle of Water Sensor Networks” challenge.

“Transfer Feature Representation via Multiple Kernel Learning”

Cross domain feature learning…  This was relatively gibberish-filled.  The presenter zoomed very quickly through many pages of notation and equations without showing much relatable context, accompanied by highly-accented, terse chatter.  Kinda picked up on some distance and cost functions, but geez.  Sorry, this one will probably require just looking at the paper.

Tested out on face data sets (slide shown for like 1 second) to classify faces, as far as I can tell.  Egads.  Indecipherable. 

Presenter suggested at the end to just contact the main researcher for any questions.

Brief Machine Learning Oriented Poster Previews:

NEXT:

Stacked denoising auto-encoding.  Involves creating a relational probabilistic graph model.  Applied to tagging movies and predicting award winners.

NEXT:

Sample targeted clinical trial adaptation.  Applied to determining people best to select for a clinical trial.  Uses auxiliary data to stratify the candidates and remove least likely ones.

NEXT:

Matrix completion for multi label image classification.  Involves applying a “low-rank” classification method in contrast to classical multi-view subspace methods that are not suitable for multi-label classification.

NEXT:

Multi objective reinforcement learning.  Involves learning a continuous approximation of a Pareto frontier of an underlying markov process.  Also involves building a parameterized manifold in the policy space that maps the frontier, and then minimizing loss from the real Pareto frontier.

NEXT:

Learning half spaces using query synthesis.  Assume a deterministic noise-free half-space.  You can only conduct membership queries, but that’s expensive and would like to be able to estimate the half space efficiently.  Solution involves creating an elliptical generation process that ends up being polynomial (vs exponential).

NEXT:

Reinforcement learning via demonstrations and relaxed reward demands.  Involves a learning cycle:  request -> policy -> teacher -> action -> world -> observations -> state -> learning -> model -> planning -> back to policy.

NEXT:

Probabilistic tensor decomposition, leveraging features and networks.  Involves probabilistic methods and side-information to inform the tensors.

My observations from the AAAI-15 Open House, 1/26/2015 in Austin, Texas.

“Leveraging Multi-modalities for Egocentric Activity Recognition”

Using Google glass and similar tech, combined various techniques to improve accuracy of activity recognition; e.g. whether you are brushing your teeth or doing laundry.

“Cogsketch: Sketch Understanding for Cognitive Science and Education”

This was a pretty interesting poster demonstrating software that can classify objects in a hand-drawn sketch and then use that information for various interactive contexts; e.g. educational programs for kids where they draw answers to questions.  Will eventually go open source, but can download code now.

“2012 BotPrize Champion: Human-like Bot for Unreal Tournament”

The idea here is that you play Unreal for a while and then identify which other player is the bot; sort of a non-verbal Turing Test.  I sat down and played and died a lot and could not really determine who was or wasn’t a bot.  I kinda think this is a bit jinky in that: you’re really distracted by the game, there’s limited interaction (shoot shoot bang bang), and real life players vary greatly.

“Going Beyond Literal Command-Based Instructions: Extending Robotic Natural Language Interaction Capabilities”

This poster was interesting in that it was focused on human-robot interaction and designing the bot to ask questions to inform about the intention of the human asking it to perform a task, especially if the question can be interpreted  differently depending on tone of voice, etc.  Some compelling results, but still very stochastic in methodology.

“An Agent-Based Model of the Emergence and Transmission of a Language System for the Expression of Logical Combinations”

This poster was pretty interesting in that the research created a virtual environment for independent agents who, with separate overlapping concept sets, would be set in scenarios with each other where they would generate utterances to represent concepts an the back and forth interplay would result in a generated, agreed upon language to describe the objects in the environment.  However, relied a lot on the contrivances of the environment, and is modelled mostly on propositional logic (all coded in Prolog).

The Future of (Artificial) Intelligence (talk by Stuart Russell)

Gave quick overview of recent advancements in AI.  Deep Learning, poker “solved”, etc.  Implying that we’ve been maximizing expected utility.   Deep Mind can learn to play Space Invaders from scratch simply from watching pixels on a screen.  Deep Mind can learn to drive in a similar way.   Watson winning Jeopardy (funny slide with one of the contestants having written with his answer that he bows to “our future computer overlords”).   A Google cat bot prototype can traverse on ice, and regain its balance if pushed.  Bots can do your laundry.

However, there are misconceptions in the media.  There’s an odd quote (should look up) from the Harvard Business Review predicting that AI will soon have IQ’s greater than 90% of the workforce (which is ridiculous).  As we know in the AI community, this is so far from reality.  We have made progress along narrow corridors of the science, but really no breakthroughs that would constitute an sentient IQ.   Also a misconception that progress in AI follows Moore’s law.  Also pretty false.  (note to self: Minsky recently made a statement about how there hasn’t really been any progress in AI for 20+ years).

Injected note about work he has been doing to help detect nuclear explosions around the globe; heavily suggesting the use of AI tech to help and improve the world.  Apparently there have been 2k+ nuclear detonations since 1945, and now there are detection sites all over the world listening for vibrations in the earth.  Distinguishing between a nuclear detonation and other types of disturbances is a challenge that his AI is helping to solve (and has significantly improved the accuracy of).

What about the impact and realization of fears if AI succeeds?  Is a human with a voice (think Hitler) more powerful than a robot army?  How likely is a robot to exhibit spontaneous malevolence vs competent decision making?  References to “Superintelligence” (note to self: planning to read).  Some movement in the direction of establishing counter-AI regulation and security, to limit the impact of AI on humans.

Russell’s proposal:  create provably beneficial AI.  Set limitations, verifiers, etc.   Cooperative value alignment, which means that the robot has the human’s interests in mind, not its own, and wants to make the human “happy”.   There are obviously problems to be addressed.  How do we verify behavior?  The bot may be programmed to have the human interest in mind, but humans are fallible, fickle, inconsistent and weak-willed.  Even if the bot asks questions, how will it know what’s right?  Objective functions have largely been presumed, but really they need to be learned/generated (so the race to solve this is on!)

Injected other things we should maybe be concerned about outside of AI; e.g. the ability to literally type the structure of a genome and generate the organic equivalent, which can potentially be used to modify the genomic structure of babies in the womb.

Brought up the idea of forming a robotics commission in the government, mostly for the need to have more understanding about robotics in the government.  There are some laws that need to be changed; e.g. current law allows an ISP to more or less own bot AI that you put through their service.  But really, we mostly need common sense containment in the same way that we do with nuclear energy / bombs; i.e. you can use that knowledge to create h-bombs or generate energy efficiently in a fission reactor.