At+t Corp.

Lucent Technologies Inc.

Google Inc.

Inxight Software, Inc.

William W Cohen

Yoram Singer

Dallan W Quass

Andrew K McCallum

Tom M Mitchell

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for determining similarity measures for objects in a dataset that include contextual associations of the objects with contexts. In one aspect, a method includes calculating a similarity measure for any two objects that include a common feature f based, in part, on the likelihood that the two object representations in the dataset that both include f will we associated with distinct contexts, and the likelihood that the two objects in the dataset that both include f will be associated with the same context.

Context-dependent similarity measurements

A method is provided for information extraction and classification which combines aspects of local regularities formulation with global regularities formulation. A candidate subset is identified. Then tentative labels are created so they can be associated with elements in the subset that have the global regularities, and the initial tentative labels are attached onto the identified elements of the candidate subset. The attached tentative labels are employed to formulate or 'learn' initial local regularities. Further tentative labels are created so they can be associated with elements in the subset that have a combination of global and local regularities, and the further tentative labels are attached onto the identified elements of the candidate subset. Each new dataset is processed with reference to an increasingly-refined set of global regularities, and the output data with their associated confidence labels can be readily evaluated as to import and relevance.

Method for learning and combining global and local regularities for information extraction and classification

A method and apparatus is provided for producing a general data extraction procedure capable of extracting data from data sources on a network regardless of data format. The general data extraction procedure is determined from a plurality of pairs of data from the network, each pair including a data source and a program which accurately extracts data from the data source. The pairs of data are processed by a learning system to learn a general program for extracting data from new data sources.

Method and apparatus for extracting data from data sources on a network

An information retrieval system finds information in a Distributed Information System (DIS), e.g. the Internet using query learning and meta search for adding documents to resource directories contained in the DIS. A selection means generates training data characterized as positive and negative examples of a particular class of data residing in the DIS. A learning means generates from the training data at least one query that can be submitted to any one of a plurality of search engines for searching the DIS to find &ldquo;new&rdquo; items of the particular class. An evaluation means determines and verifies that the new item(s) is a new subset of the particular class and adds or updates the particular class in the resource directory.

System and method for finding information in a distributed information system using query learning and meta search

A system and method are provided for answering queries concerning information stored in a set of collections. Each collection includes a structured entity, and each structured entity includes a field. A query is received that specifies a subset of the set of collections and a logical constraint between fields that includes a requirement that a first field match a second field. The probability that the first field matches the second field is determined automatically based upon the contents of the fields. A collection of lists is generated in response to the query, where each list includes members of the subset of collections specified in the query, and where each list has an estimate of the probability that the members of the list satisfies the logical constraint specified in the query.

System and method for accessing heterogeneous databases

Efficient techniques for inducing rules used in classifying data items on a noisy data set. The prior-art IREP technique, which produces a set of classification rules by inducing each rule and then pruning it and continuing thus until a stopping condition is reached, is improved with a new rule-value metric for stopping pruning and with a stopping condition which depends on the description length of the rule set. The rule set which results from the improved IREP technique is then optimized by pruning rules from the set to minimize the description length and further optimized by making a replacement rule and a modified rule for each rule and using the description length to determine whether to use the replacement rule, the modified rule, or the original rule in the rule set. Further improvement is achieved by inducing rules for data items not covered by the original set and then pruning these rules. Still further improvement is gained by repeating the steps of inducing rules for data items not covered, pruning the rules, optimizing the rules, and again pruning for a fixed number of times. The fully-developed technique has the O(nlog.sup.2 n) running time characteristic of IREP, but produces rule sets which do a substantially better job of classification than those produced by IREP.

Rule induction on large noisy data sets

Apparatus and methods which employ a machine learning system to 'learn' the specification for a program from a trace of an execution of the program on a set of test problems. The program is instrumented to produce the trace. Performance is improved by means of a declarative bias which expresses knowledge of the user about the program and constrains the learning system to produce only specifications which are consistent with the declarative bias. The apparatus and methods of the preferred embodiment are employed to learn specifications of views in a data base for a telephone switching system from traces produced by executing the programs which produce the views. Techniques for producing more than one specification and for dealing with views which involve conversions are also disclosed.

Software discovery system

The invention permits various types of background knowledge for a concept learning system to be represented in a single formal structure known as an antecedent description grammar. A user formulates background knowledge for a learning problem into such a grammar, which then becomes an input to a learning system, together with training data representing the concept to be learned. The learning system, constrained by the grammar, then uses the training data to generate a hypothesis for the concept to be learned. Such hypothesis is in the form of a set of logic clauses known as Horn clauses.

Growing community of inventors

Pittsburgh, PA, United States of America

William W Cohen