Pedro Sant'Ana

Former intern at Infosimples, studies Computer Engineering at University of São Paulo. Loves music, gaming and programming. Looks forward to further his studies in Artificial Intelligence.

Read all articles published by Pedro Sant'Ana.

Artificial Intelligence for Tic-Tac-Toe
Gravatar published this on

Data Science Programming

The use of reinforcement learning to program the artificial intelligence of games probably has as one of its most impressive achievements the development of a program that could play backgammon at a professional level by Gary Tesauro from IBM during the 90s. The first attempt was to build a model of the many states of the game based on a collection of examples and try to generalize from those using supervised learning. Besides being a tedious job for the researchers to enumerate hundreds of different states, the program was performing poorly.

Using a different approach, this time with reinforcement learning, the developers made two versions of their game play against each other. At the end of each game, the winning one received a positive reward and the losing one a negative. After 200.000 matches, the agent was able to play at the level of some of the best players in the world, without the need of any kind of professional experience or describing the more than 1 trillion possible states of the game.   

In an attempt to recreate the experiment with a simpler game, the idea was to develop an intelligent agent for Tic-Tac-Toe, without the need to write an algorithm with the best strategies or enumerating all the possible states of the game.


String Segmentation using Machine Learning
Gravatar published this on

Data Science Programming

Artificial Intelligence has brought lots of improvements to problems related with language processing, especially in the field of language translation. Other examples include suggestions to correct misspelled words or even speech recognition.

To test a simple algorithm that works with elements of a language, the developed program had the objective of being able to split a string without spaces into the words that compose that string. For instance, receiving the string "thisishowitshouldwork" should result in "this is how it should work".

The problem consists in being able to identify words, since it's impossible to list all the known english words and there is no model that can correctly generalize the structure of every word.

The approach was to use supervised learning and a database of texts as training data so that the agent could start to identify the different words that exist in the english language. By utilizing texts instead of just a list of thousands of different words, it's possible to identify the frequency in which every word tend to appear. Knowing the probability of each word showing up, the agent should be able to calculate the most probable segmentation of every string.

It's viable to say that the probability of a certain segmentation depends on the probabilities of each word obtained by that segmentation. By considering the words that show up before the one we are analysing, the results could be even more accurate but, with the relatively small quantity of training data available, it was only taken in consideration the individual probability of each word.

Another point that has to be taken into consideration is how to deal with words absent from the training data. It's impossible to say that any training database contain every known word, no matter how big it its. This issue was adressed by using Laplacian Smoothing to avoid unknown probabilities to being equal to zero. At last, the calculations should be normalized so it's possible to compare segmentations between a different number of words.

The probability of a single word can be expressed by:

where n is the number of times the word appeared on the training data, T the total of analysed words, k is a constant and V is the estimated total number of words on the english vocabulary. On this problem it was used k = 1 and V = 2,000,000.

The probability of a segmentation can be expressed by: 

where p1, p2, ... pn are the possible words obtained on a segmentation.

Knowing how the calculations should be done, it's necessary to deal with the problem of hardware limitations. A string with n characters has 2n-1 ways of being split, which would result in over one million calculations just to identify the best segmentation of the string "thisishowitshouldwork".

To deal with this problem, it's possible to adjust the algorithm to always split the string in two pieces, f (first part) and r (rest). If the probability of f is X times bigger than r's, the agent has likely found a good segmentation in f, and should try to segment r as well.


Introduction to Machine Learning
Gravatar published this on

Data Science

From may to august 2014, I took an internship at Infosimples and had the opportunity to take the course Intro to Artificial Intelligence taught by professors Sebastian Thrun and Peter Norvig, offered at Udacity. Covering a vast amount of subjects, its machine learning classes are without a doubt the most exciting ones. This article in three parts aims to pass along some of the knowledge acquired and demonstrate a few of the machine learning techniques taught during the course.

Artificial Intelligence and Machine Learning  

Present in many different fields, artificial intelligence programs have been showing surprising results during the last years and are becoming a bigger part of our daily lives. It's possible to spot examples of intelligent programs that help professionals at hospitals, robotic facilities, the internet or even with finances. Besides some of the most known achievements, like the Deep Blue computer from IBM, that in 1997 defeated the chess world champion Garry Kasparov or the recently announced Google's self-driving car, there are thousands of other applications that use artificial intelligence to achieve the required level of performance.

An intelligent agent, as those programs are called, is capable of interacting with the environment and choosing its next action after analysing the received information. Building an efficient artificial intelligence program revolves around finding the best function that maps all the input and output data.

On most cases, the agent works at environments where it is extremely hard or sometimes even impossible to manually program a function that can work around every possible situation. Those difficulties are usually related to the environment being continuous and not discrete, stochastic instead of deterministic and partially observable instead of fully observable.

In situations like these, the use of machine learning in applications stands out with its high efficiency and the ability to cover an enormous amount of states without the need to individually program all of them. These applications require an additional step during development, called training, in which they are presented with the required information to be able to "learn" how to perform in the future.

Machine learning techniques can be split in three categories:

Supervised Learning is used to generalize the behavior of the program from a collection of known cases, so that it can perform correctly in any similar situation. A popular example is the classification of emails as spam: using a database of emails labeled as either being spam or not as reference, the agent should be able to recognize elements that may classify an email as spam. After learning from various examples, the program is capable of doing this classification for future email messages.

In unsupervised learning, there is no proper knowledge on how the data behaves and the used algorithms try to organize that data in patterns so that it is possible to classify them. The agent looks for an approximate way to describe the received information.

And last, there is reinforcement learning, in which there is a feedback about the obtained results, with positive rewards to the correct results and negative to the wrong ones. With this score, the agent can adjust its behavior to work on the desired way.

On the next parts of this article, there are two examples of simple applications using machine learning, one with supervised learning and another one with reinforcement learning.

String Segmentation using Machine Learning

Artificial Intelligence for Tic-Tac-Toe

Read more about: