During fall 2010 and spring 2011 I’ve been studying Computer Science at the Georgia Institute of Technology, where I took, among the others, an Artificial Intelligence class, held by professor Frank Dellaert. In this page I’m reporting a portfolio of what I’ve learned during the course, how I did and some considerations about the course.
Foundation: Reading and Assignments
In the course, we completed 7 assignments on the foundations of AI, after reading the relevant material in the textbook.
The assignments covered various AI techniques, approaches and applications, organized in five macro-areas as follows:
- Problem Solving
- Search (A*, D*, Stochastic Local Search)
- Constraint Satisfaction Problems (graph coloring, SAT)
- Knowledge, Reasoning and Planning
- Logic (Propositional Logic, knowledge representation, applications on search problems)
- Planning (search, heuristics and logic for planning)
- Uncertain Knowledge and Reasoning
- Bayes Networks (Factor Graphs, elimination)
- Statistical Relational Learning and Markov Logic Networks
- Learning
- Machine Learning with Decision Trees and Support Vector Machines
- Communicating, Perceiving and Acting
- Natural Language Processing with n-grams
The general structure of the course followed a clear schema of presenting a technique, showing pros and cons, and exploring possible improvements; so from search we discussed SLS, from logic to statistics to reach statistical reasoning, until the general, master goals of AI which are fields such as Natural Language Processing, Computer Vision and Robotics, which use all the techniques presented in class and many more. Readings and Assignments has been followed by class discussions about other technologies and approaches, such as First Order Logic, AND-OR trees, RRT/RRT* and Gibbs Sampling, as well as intriguing challenges such as the NetFlix Prize.
In the assignments I did pretty well. On average I have been evaluated 4.85 points out of 5. I did best on CSP and Bayes Networks, probably because they were two very interesting topics and I put more effort on them. The most challenging assignment has been, ironically, the learning assignment (4.5 out of 5,) due to a question that required a statistical knowledge I didn’t have and the book didn’t cover. I am very satisfied of how the assignments affected the course: they have been very useful for better understanding the material covered in class, since, like always, just reading is not enough.
Skills: Mini-projects
There were three mini-projects in which I chose to research a problem that was supposed to be relevant to my your future career. For each of these three projects, I proposed a solution, implemented it, and described it in a mini-conference paper.
Our Mini-projects have been evaluated very well, with an average of 12.6 points out of 13. Apart from the grades, I think we did our best on the third project, which was about forecasting basketball games using bayes networks, because we achieved a very good performance with a very simple approach, which can be easily improved; the most challenging one was the second project, where we tried to use logic to solve puzzles in the form of the zebra puzzle. Unfortunately the approach showed the complexity of the problem, and the limitations of using pure logic on such puzzles.
Project 1: Hierarchical Graphs for GPS Routing Devices
Project 2: Logic for Zebra-Puzzle Style Problems
Project 3: Forecasting Basketball Games Using Bayes Networks
My favorite Project: Forecasting Basketball Games Using Bayes Networks
Forecasting basketball games is still an open topic. While there are good results in forecasting baseball, for example, basketball is still a challenge, since it heavily relies on team statistics and interaction between players. Being able to increase the accuracy of basketball forecasting would not only be a resource for fans, but owners spend millions of dollars on players, and they want to be sure their money is not going to be wasted.
Different approaches have been applied to basketball forecasting: different machine learning techniques [1] achieved an accuracy up to 67%, but where too static and could not take into account single player statistics. Weighted Likelihood [2] performed better on certain tests, but the variability of the results was too high to predict the outcome of a single game. Markov Logic Networks and Bayes Logic [3] performed well, from 64% to 76%, and seems at the moment the best approach to this problem, even if the authors did not take into account many interesting game variables.
[1] The use of data mining for basketball matches outcomes prediction
[2] Forecasting NBA basketball playoff outcomes using the weighted likelihood
[3] First-Order Probabilistic Models for Predicting the Winners of Professional Basketball Games
Our approach consisted in collecting both team and single player statistics from public online resources, and then using them to build two bayes networks, the first using only player statistics and the second adding also team statistics. The resulting networks were very simple, pairing the players of the two teams using their abilities and then using the PER value to get the probability of the home player to win the direct match against his paired opponent. All the probabilities were then joined in the final state, after a smoothing process. The bayes networks have been converted then into a factor graph, and an elimination algorithm gave us the probability of the home team to win the match.
We achieved, with a very simple bayes network and using only two team and player statistics, an accuracy of 64%, the same accuracy obtained by Bayes Logic in [3]. We believe that our simple approach can be easily improved adding more statistics, and taking into account changes in the teams roster.
Integration: Research Proposal
Towards the end of the course I was asked to write a more substantial research proposal that integrates AI into another discipline of my choosing.
My idea was to realize a electronic music stand, eMusicStand, with AI capabilities. Such a device could be used both for training and ensamble performances. Using sound recognition it would be possible to analyze the player and evaluate him/her on some metrics, such as note accuracy, speech recognition would allow to accept vocal commands and music optical recognition would permit to import new music sheets in the device. Other functionalities would be adding notes using touch screen, sharing music sheets using wifi and the possibility to share personal statistics with the director, to give an overview on how the orchestra in playing.
Three main AI techniques are needed. The first, Speech Recognition, is currently implemented using Hidden Markov Models [1], where voice is recorded and features are extracted, each of them representing a particular phoneme (or set of phonemes). This observed phonemes are then used to compute the probability that a particular sequence of phonemes represents a spoken word. The second, Music Recognition [2], implemented using wavelet transform, performs very well on a single tune, but there is currently no research about recognizing music attributes, such as staccato, legato, puntato and so forth. Music Optical Recognition [3] instead boasts many techniques to convert a scanned music sheet in electronic and formal notation, such as staff elimination, vertical/horizontal projection, object classification and so forth, and performs pretty well.
[1] The Application of Hidden Markov Models in Speech Recognition
[2] A Real-time Algorithm for Music Recognition Based on Wavelet Transform
[3] Optical Music Recognition
I proposed to implement each part as follows: the device has to recognize only simple commands, therefore HMM would be a good way to achieve a good speech recognition algorithm, biasing the output using a filtered n-gram in order to limit the sentences to be recognized and increase the overall accuracy. Music recognition instead requires a novel research in order to classify music attributes. My idea is to use analysis in both frequency space and wave form space, using a classification technique such as SVM. OMR will be implemented as at the state of the art, trying to improve the recognition accuracy if needed using computer vision techniques such as object filtering, segmentation and classification.
The evaluation is divided in three phases. In each phase the device will be tested respectively with a soloist, an ensamble of five to eight players, and an orchestra of forty to sixty players. Each AI technique will be tested on accuracy, number of successes over the total attempts, and the algorithms will be tuned to achieve the best performance, still preserving the retrocompatibility.
The development phases will follow a spiral pattern, with implementation and evaluation switching. In this way the system will be evaluated and improved at every step, after an initial implementation. For a project lasting one year, each phase would be as follows:
- Four months: basic implementation of the three AI algorithms and GUI to allow the device to be used;
- Three months: evaluation with soloists and optimization;
- Three months: evaluation with ensamble and optimization, and extension to wifi communication;
- Two months: evaluation with orchestra and final data collection.
Final Comments
This course helped me in my academic career in many ways. I learned how to criticize my work and write a paper with a specific headline in mind, always focusing on what the reader would be interested in. I learned how to effectively present my work in a public presentation, and how to share my ideas with other fellows, and improve my work treasuring their suggestions. The way the course was structured, with assignments about specific fields of interest intervalled by projects presented in a conference fashion, with public presentations and discussions, and with interactive lectures with continuous interaction between all the participants, made this course extremely exciting and effective, with the uncommon ability to be able to fix in our minds pretty hard topics of Artificial Intelligence.