There is a brand new discussion forum associated with this group. Please contribute to the discussion.
The talk is based on this paper (Game Programming Gems 8, 2010).
Background: Sometimes, quantity is quality. Many times a game maker has dreamed of making a virtual world filled with thousands of intelligent agents. If done correctly, these computer-controlled characters act just like people, allowing the player to experience phenomena they could not experience in smaller scale systems. Multi-agent and massively multi-agent systems of behaviorally plausible agents provide more than entertainment, they allow researchers to study phenomena such as influence propagation, tipping points, steering, contextual decision making, group decision making, individual differences, culture, leader theory and much more. Groups such as the University of Pennsylvania, the Army Corps of Engineers and the Navy have used such systems to study the behavior of people fleeing a fire, soccer hooligans, terrorist cells, riots, inner city gangs and the reaction of Afghan villagers to U.S.-led reconstruction activities. Despite the value inherent in massively multi-agent systems, few such systems exist. Those that do typically suffer numerous, significant undesired compromises - agents lack individuality or personality, have limited knowledge, have no persistent memory, are not sufficiently context aware, etc. The reason for this is cost. At Alelo, a company that makes cultural training games using conversational agents, it took two people (a designer and programmer) a combined three weeks to build a single conversational agent. This was only enough time to produce an agent capable of performing a single "conversational task". Populating a town with hundreds of unique, functional characters requires too much time, money and manpower.
This talk is based on the paper "Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation" by Francois Fouss and Jean-Michel Renders. That paper shows that the pseudo-inverse of the Laplacian of an undirected graph (a) gives the expected round-trip commute time between any pair of vertices, (b) matches the effective resistance between two vertices when the network is treated as an electrical network, (c) shows how this commute time is an euclidean metric for a particular embedding of the vertices in Euclidean space. As a result, the paper claims experimentally that this leads to more accurate affinity measures in collaborative filtering. In my talk, I summarize some of the theoretical results and show how some of these may be extended to fully connected directed graphs.
The paper is available at http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4072747&isnumber=4072743
@article{Fouss07,
author = {Francois Fouss and Jean-Michel Renders},
title = {Random-Walk Computation of Similarities between Nodes of a Graph
with Application to Collaborative Recommendation},
journal = {IEEE Trans. on Knowl. and Data Eng.},
volume = {19},
number = {3},
year = {2007},
issn = {1041-4347},
pages = {355--369}
}
While there is no required reading for this week, for those who are interested, the talk covers 4 papers:
Type A Influenza Virus Hemagglutini Protein Analysis with Directed Acyclic Graph
Hemagglutinin (HA) is an antigenic glycoprotein found on the surface of the influenza viruses. The primary goal of this research is to provide insight into the dominant hemagglutinin amino acid sequences. The study of the influenza virus evolution has traditionally relied on phylogenetic techniques, for example, the maximum likelihood approach and traditional parsimony algorithms. We have proposed simply using a pairwise distance function combined with a directed acyclic graph method to study the evolutionary history of the virus.
Related work:
Georgopoulos AP, Kettner RE, Schwartz AB. (1988) Primate motor cortex and
free arm movements to visual targets in three-dimensional space. II.
Coding
of the direction of movement by a neuronal population. J Neurosci. 8:
2928-2937.
Georgopoulos AP, Langheim FJ, Leuthold AC, Merkle AN.
Magnetoencephalographic signals predict movement trajectory in space.
Exp Brain Res. 2005 Nov;167(1):132-5. Epub 2005 Oct 29.
Taylor DM, Helms Tillery SI, and Schwartz AB,
Direct Cortical Control of 3D Neuroprosthetic Devices,
Science 296: 1829-1832 (2002)
We study the algorithms that speed up the training process of support vector machines by using an approximate solution. We focus on algorithms that reduce the size of the optimization problem by extracting from the original training data set a small number of representatives and using these representatives to train an approximate SVM. Using the approach of algorithmic stability, we prove a PAC-style generalization bound for the approximate SVM, which includes as a special case the generalization bound for the exact SVM, which is trained using the original training data set.