Computer Program Learns Language Rules And Composes Sentences, All Without Outside Help

The development -- which has a patentpending -- has implications for speech recognition and for otherapplications in natural language engineering, as well as for genomicsand proteomics. It also offers new insights into language acquisitionand psycholinguistics.

"The algorithm -- the computational method-- for language learning and processing that we have developed can takea body of text, abstract from it a collection of recurring patterns orrules and then generate new material," explained Shimon Edelman, acomputer scientist who is a professor of psychology at Cornell andco-author of a new paper, "Unsupervised Learning of Natural Languages,"published in the Proceedings of the National Academy of Sciences (PNAS,Vol. 102, No. 33).

"This is the first time an unsupervisedalgorithm is shown capable of learning complex syntax, generatinggrammatical new sentences and proving useful in other fields that callfor structure discovery from raw data, such as bioinformatics," he said.

Unlikeprevious attempts at developing computer algorithms for languagelearning, the new method, called Automatic Distillation of Structure(ADIOS), successfully identifies complex patterns in raw texts. Thealgorithm discovers the patterns by repeatedly aligning sentences andlooking for overlapping parts.

For example, the sentences I wouldlike to book a first-class flight to Chicago, I want to book afirst-class flight to Boston and Book a first-class flight for me,please may give rise to the pattern book a first-class flight -- ifthis candidate pattern passes the novel statistical significance testthat is the core of the algorithm.

If the system also encountersthe sentences I need to book a direct flight from New York to Tel AvivandI would like to book an economy flight , it may infer that thephrases first-class, direct and economy are equivalent in the contextof the new pattern. "Because such equivalence sets can contain otherpatterns -- in turn containing further patterns, and so on -- theresulting body of knowledge grows recursively, as a sort of forest ofbranching trees of possibilities," said Edelman.

He added, "ADIOSrelies on a statistical method for pattern extraction and on structuredgeneralization -- two processes that have been implicated in languageacquisition. Our experiments show that it can acquire intricatestructures from raw data, including transcripts of parents' speechdirected at 2- or 3-year-olds. This may eventually help researchersunderstand how children, who learn language in a similar item-by-itemfashion and with very little supervision, eventually master the fullcomplexities of their native tongue."

In addition tochild-directed language, the algorithm has been tested on the full textof the Bible in several languages, on artificial context-free languageswith thousands of rules and on musical notation. It also has beenapplied to biological data, such as nucleotide base pairs and aminoacid sequences. In analyzing proteins, for example, the algorithm wasable to extract from amino acid sequences patterns that were highlycorrelated with the functional properties of the proteins.

Thenew method was developed jointly with David Horn and Eytan Ruppin,professors of physics and computer science, respectively, at Tel AvivUniversity, and with Zach Solan, a doctoral student there and the leadauthor on the paper. Their collaboration with Edelman was supported inpart by the U.S.-Israel Binational Science Foundation.