Machine Learning

Various projects of mine focussed on machine learning.


  Old - Some content is 10+ years old, not representing my current thoughts  

Index


Machine Learning

Gopher
Image Recognition

Some of my code is available on my GitHub Account


Gopher


I've been fascinated by the ancient board game of Go (Weiqi, Baduk) for a while. It's an incredibly deep game emerging from a simple set of rules. You can read more about it at Sensei's Library. Unlike chess, human players are still stronger than the best computer programs. GOFAI techniques have not been successful at tackling the problem of creating a strong Go AI player. The high branching factor, long game length, lack of a strong evaluation function and global nature of the game make this a very tough problem to solve. Recently, there has been a major breakthrough in AI strength through a new algorithm called Monte Carlo Tree Search (MCTS). Having a Monte Carlo background through my work in computer graphics, this family of techniques seemed immediately appealing. MCTS combines the precision of minmax searching with random simulations (sometimes called playouts, or rollouts) for an evaluation function. Further, UCT (also see Sensei's Library on UCT) adapts the UCB algorithm (Upper Confidence Bounds as applied to the Multi-armed Bandit Problem) to trees. This basically combines stochastic tree search, the exploitation vs exploration balance of a bandit problem and the random-simulations-as-evaluation-function idea into a powerful algorithm that forms the basis for most top Go programs today. See A Survey of Monte Carlo Tree Search Methods for a comprehensive overview. This is a very active area of research, with many publications on improving the general tree search method and incorporating domain specific knowledge into the playouts. The RAVE (Rapid Action Value Estimation) algorithm being an important example of the former, and the addition of 3x3 patterns in the playouts an important example of the later. Research problems include finding automatic ways to acquire domain specific knowledge without relying on external experts (See Computing Elo Ratings of Move Patterns in the Game of Go), parallelization of the MCTS algorithm and fixing weaknesses of current programs (such as dealing with situations where the move order is of great importance). The MCTS algorithm is now being used for applications other than Go such as GGP (General Game Playing) and other planning and decision making problems. My own Go program, Gopher, is a heavy work-in-progress also based on UCT. It features a largely lock-free tree representation and scales nicely on SMP machines. The data structures used during playouts have been optimized for little state to facilitate an eventual GPU port.

Gopher's GUI is based on OpenGL and GLFW. This screenshot shows the board editor, which makes it easy to setup positions and save them for later recall.
Here's Gopher running with 8 threads trying to read a ladder. You can see some statistics about the search status and leaf distribution in the tree. There are also some visualizers for the best play as well as the win rate, visits and UCT value for moves at the root.

Image Recognition


This unfortunately never finished project was an attempt to implement image recognition based on a feed-forward neuronal network with learning through backpropagation. The input for the neuronal network were some features of the images extracted through analysis of the co-occurrence matrix of each color channel.

A Co-Occurence matrix and the features extracted from it. The matrix was computed for every channel and then the extracted features were fed into the network.

 © 2002 - 2024 Tim C. Schröder Disclaimer