The quest for intelligent computers

Marcelo Finger’s group at IME-USP is developing algorithms to improve the efficiency of search engines and automatic translators and thereby facilitate disease diagnosis.

By Karina Toledo

Agência FAPESP – Over the past 50 years, the processing and memory capacities of computers have grown exponentially, but machine logic has evolved very little. In 1930, before the first computer had even been built, the class of problems that could be solved by the technology was determined. Later, scientists discovered that there are three types of problems: inherently easy, inherently difficult (the so-called “intractable problems”), and those for which the level of difficulty is unknown.

This is an evaluation of Marcelo Finger, a professor at Universidade de São Paulo’s Mathematics and Statistics Institute (IME-USP), who has coordinated an FAPESP-funded Thematic Project since 2009. The project’s goal is to make computer programs more intelligent. To this end, the team is researching new methodologies to solve problems that are at the intersection of logical and probabilistic reasoning. Practical applications of the method range from the development of more efficient search engines to automatic translators and include software capable of analyzing video-recorded images to detect when something is outside the norm in a given location or situation.

The Thematic Project has resulted in 104 published articles, three post-doctoral degrees, four doctorates, 15 master’s degrees, and six scientific initiatives. In an interview with Agência FAPESP, Finger recalled details about the results obtained thus far.

Agência FAPESP – How can the Thematic Project that you coordinate contribute to make computer programs more intelligent?
Marcelo Finger: There are always solvable and unsolvable problems in computing. Within the solvable category, the majority of problems are considered intractable; that is, the time required for resolution is so long that in practice it is unfeasible. The problems at the intersection of logical and probabilistic reasoning are generally either in the category of the intractable or in a gray zone in which we do not know whether or not they can be solved quickly. One of the Thematic Project’s lines of reasearch is dedicated to developing a means to identify which problems can be solved and  methodologies to solve them quickly.

Agência FAPESP – How is this being done?
Finger – We showed that for some of the intractable problems there is a phenomenon of phase transition. First, there is a large class of easy problems that we know can be solved quickly.. Then there is a class of slightly more difficult problems, for which the answer is always no. In the middle are the really complicated problems, for which we do not know whether a quick solution is possible. On this basis, we developed three algorithms, one better than the other, to quickly solve problems that are in one of the two extreme classes. Previously, we believed that it was impossible to solve a problem that had more than six variables. But with this method, we were able to solve problems with 400 variables in less than a second.

Agência FAPESP – Can you give an example of a practical application of this method?
Finger – We want to apply it to several areas, such as computational linguistics. With the method that we have developed, it will be possible to improve programs that perform syntax analysis. This could be used in automatic translators, for example. We are also trying to improve robotic algorithms to make robots capable of carrying out more complex tasks. There are two additional research lines: one dealing with image analysis, the other with Web semantics.

Agência FAPESP – What is Web semantics?
Finger – It means relating different domains and making them communicate with one another. Today, search engines work through word association. Using web semantics, it is possible to create programs capable of associating concepts, resulting in a more intelligent search. For example, if you are looking for a term, the program is able to provide a valid result that uses  different terminology. In our project, we are working on Web semantics as it applies to the medical area.

Agência FAPESP – What type of application could we see in medicine?
Finger – The idea is to create a tool capable of assisting in medical diagnosis. The program would have the descriptions of symptoms and other information about the disease, based on clinical data that are probabilistic in nature. For example, a fever could be a symptom of a given disease, but not all people with that disease have a fever. These are probabilistic data. This has an immediate practical application. We already have a hospital that is interested.

Agência FAPESP – What is the intention of the Thematic Project’s image analysis line of research?
Finger – Create a program capable of analyzing the scenes recorded by a camera and detecting when something unexpected occurs. For example, airlines could use this to supervise supply procedures or loading and unloading of airplanes.  Armored truck companies could use it in a similar manner. We are working with flight recordings, but thus far we have only received recordings from flights during which no unexpected events occurred, and therefore our data were not adequate for the purpose of training on error probabilities.

Agência FAPESP – What are the Thematic Project’s future plans?
Finger- We intend to extend the project for two more years. We will continue the same lines of research. We will develop better algorithms, seek more rapid solutions, and expand the methodology for other types of related problems. I plan to spend a year at Cornell University in the United States to increase our body of data and foster interactions with researchers there. During my absence, Professor Fabio Gagliardi Cozman of USP’s Polytechnic School will act as the coordinator.