Teaching Machines To Talk
Link: https://plus.maths.org/content/os/latestnews/may-aug05/adios/index
This article discusses a program called ADIOS – automatic distillation of structure – which uses patterns in graphs of sentence structure to effectively learn how to talk. The program has been shown to be effective in multiple languages, from English to Chinese.
The graph above is used to show how the program works. All the words are nodes, or vertices, and each sentence is a sequence of nodes connected by lines, or edges. A string of words is a path in the graph. The algorithm, uses statistical analysis to learn how speak. By giving it access to a large number of sentences, it then categorizes the nodes and paths by how frequently they occur. The program prioritizes the higher frequencies, called “significant patterns”. The algorithm then replaces each of these patterns by a single vertex to create a broader graph.
The algorithm then looks at which paths in the graph differ by just one vertex. For example, in the graph above, the sentences: “Today it is good” and “Today it is bad” differ by just one vertex. The algorithm then marks which vertices are interchangeable, i.e. where one word in a sentence can statistically be replaced by one of many other words. The algorithm then broadens this to see which paths, are interchangeable. For example: “Today it is not very good” and “Today it is very nice”. The program creates a new graph, like the one below:
This graph shows how Paul can be replaced by the cat and the dog; hungry by thirst, and nice by angry. For example: “Paul is not thirsty” and “The dog is angry”. The program can also go beyond language with its pattern recognition: strings in general, musical notation, and amino acid sequence data.
By using statistical analysis of graphs, the algorithm can effectively talk. This is directed related to the graph theory. Firstly, the algorithm organizes the graph into nodes which together create a path. It then uses statistical analysis to separate the graph into its components, so that is can easily see which words and paths are interchangeable. Basically, the program determines which words are nouns, pronouns, verbs, adjectives, adverbs, etc. and categorizes sentence fragments. It is able to determine where to start and stop sentences because, by using directed graphs, it will also begin with a node that has only outgoing edges and end with a node that has only incoming edges. By using edge degrees, it can tell how often a word is used, and by sorting words and sentence fragments into different giant components, with edges that link to other giant components, it can easily create an infinite number of sentences by simply interchanging words and paths.
While the article does not cover this, it is easily feasible for the program to achieve the following, assuming it does not already. Firstly: cycle detection. The program would have to prevents cycles from being made so a sentence does not run on forever. Furthermore, the program could sort full sentences into giant components based on which sentences have a high percentage of words that are said in a response to a different sentence. For example, the program could put all the responses to “How are you”, such as “I am fine”, “I am okay” etc. into a component, so that it could eventually learn to communicate.
Overall, graph theory has many uses, and teaching a machine a language is just one of them.