Systems and methods for automatic creation of agent-based systems

An agent-based system may be automatically generated from a specification provided by a user or third-party process. An agent generator may map the specification to a canonical model identifying one or more tasks to be performed by the agent-based system as ontological concepts. The agent generator may generate one or more candidate agents using the canonical model. The candidate agents may comprise one or more interconnected data transforms, which may comprise data access transforms, preprocessing transforms, machine learning transforms, and/or structural transforms. The agent generator iteratively modifies the agent-based system until a termination criteria is satisfied. The termination criteria may provide a selection mechanism whereby a performance of the plurality of candidate agents may be evaluated. An optimal agent may be selected using, inter alia, the performance of the agent-based system.

TECHNICAL FIELD

This disclosure relates to systems and methods for automatically generating an agent-based system configured to perform a particular task.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

An agent or agent-based system may be used to perform a task for a user, such as data processing, data mining, or the like. As used herein, an “agent” or an “agent-based” system may refer to software and/or hardware components configured to perform a data processing task. As such, an agent may include, but is not limited to: an expert system, a semantic intelligence system, a machine learning system, a data mining system, a predictive analytic system, or the like.

An agent may be comprised on one or more transforms. As used herein, a transform may refer to any task related to data gathering, data processing, data flow (e.g., data flow between transforms), data analysis, or the like. A transform, therefore, may include, but is not limited to: data acquisition, data harvesting, data aggregation, data cleansing, data formatting, data mining, machine leaning, pattern matching, results formatting, and the like.

The process of developing an agent-based system may include selecting, configuring, and/or combining various transforms into one or more agents adapted to perform a particular task. Once an agent-based system has been created (e.g., transforms selected, configured, and/or combined), the system may be tested and/or refined. The testing may include providing the agent-based system with one or more datasets, evaluating results produced by the system responsive to the datasets, and modifying the system accordingly. The datasets may include test datasets for which a known “answer” or desired result exists. Alternatively, or in addition, the datasets may include “real-world” data. In some embodiments, the testing may be iterative; after each iteration, the results produced by different variations of the agent-based system may be compared to identify an “optimally performing” version of the system.

As illustrated above, the development of an agent-based system may be tedious and time consuming, and may require skills that are beyond those of typical users. In fact, in many situations, the development of an agent-based system may require the services of one or more “domain exerts” (persons who have the expertise required to select, combine, configure, and/or refine the transforms comprising the agent-based system).

The systems and methods disclosed herein may be used by typical users (e.g., non-expert users) to automatically generate an agent-based system. In one embodiment, an agent generator (e.g., a “meta-agent”) may be provided, which may be capable of autonomously generating an agent-based system. The agent generator may be configured to receive an “agent specification” from a user, which may define the problem and/or data sources to be addressed by the system. A canonical model of the specification may be determined by mapping tasks defined in the specification to concepts within an ontology. The canonical model may also include a mapping between the data sources identified in the specification and the ontology.

Responsive to deriving the canonical model of the specification, the agent generator may be configured to select one or more transforms from a transform ensemble to form an agent-based system. The transforms comprising the agent-based system may be iteratively evaluated and modified until an “optimal” system is determined.

FIG. 1Ais a block diagram of one embodiment of a system100for automatically generating an agent-based system. In some embodiments, one or more components of the system100(e.g., the meta-agent110, the agent generator130, the modules120,122, and/or124) may be implemented on and/or in conjunction with one or more computing devices, such as the computing device101depicted inFIG. 1B. As shown inFIG. 1B, a computing device101may include one or more processors150, memory modules152, computer-readable storage media154, a human-machine interface156, a communications interface158, and the like. The processors150may include one or more general purpose processors and/or one or more special purpose processors (e.g., one or more Application Specific Integrated Circuit (ASIC) processors). The memory modules152may include volatile and/or non-volatile memory storage resources. The computer-readable storage media154may include one or more discs, optical storage, Flash memory modules, or the like. The human-machine interface (HMI)156may allow a user104to interact with the computing device101, and may comprise a display, input/output devices (e.g., mouse, keyboard, etc.), and the like. The communications interface158may include one or more adapters configured to communicatively couple the computing device101to one or more networks102. The communications interface158may include, but is not limited to: a wired network interface (e.g., Ethernet), an optical network interface (e.g., fiber optic interface), a wireless network interface, a public switched telephone network (PSTN) interface (e.g., a modem), a cellular network interface (e.g., a 3G network interface), or the like.

Referring back toFIG. 1A, the system100comprises a meta-agent110, which may be communicatively coupled to one or more external data sources160and/or a user104by a network102. The network102may comprise any communications network known in the art including, but not limited to: an Internet protocol (IP) network (e.g., a Transmission Control Protocol IP network (TCP/IP) or the like), a local area network (LAN), a wide area network (WAN), a virtual private network (VPN), a wireless network (e.g., IEEE 802.11a-n, Bluetooth®, EDGE, G3, or the like), a public switched telephone network (PSTN), a cellular telephone network, or the like.

The user104may be communicatively coupled to the meta-agent module110via a respective computing device (not shown), which may comprise any computing device known in the art including, but not limited to: a personal computing device (e.g., a personal computer (PC) or the like), a mobile computing device (e.g., a laptop computer, an ultra portable computer, or the like), a smart phone, a personal digital assistant, or the like. The user104may interact with the meta-agent module110via a general purpose application (not shown) running on the user computing device, such as web browser software, a Telnet portal, or the like. Alternatively, or in addition, the user104may interact with the meta-agent module110via a special purpose application112provided by the meta-agent module110.

As will be discussed in additional detail below, a user104may submit an agent specification105to the meta-agent module110, which may indicate what type of agent-based system the user104requires: define the problem to be solved by the system (e.g., define the task to be performed by the system), identify the data sources required to perform the task, and/or specify how various outputs are to be formatted. For example, the specification105may indicate that the user is interested in identifying stocks traded on the New York Stock Exchange (NYSE) that exhibit a particular trend, such as an “Inverted Hammer” pattern, “Inverted Cup” pattern, or the like. The specification105may further indicate that the user104wants to limit the search to stocks within a particular industry, to stocks having a particular price-to-earnings (PE) ratio, having a particular market capitalization, or the like. In another example, the specification105may indicate the user104wishes to find content relating to a particular topic, such as a medical condition. The specification105may restrict the search space to content that has been peer reviewed, was authored by researchers having a particular set of credentials (e.g., degree from a particular set of schools, published in a particular set of journals, etc.), having a particular type of experience, and so on.

Although two non-limiting examples of a specification105are provided herein, one skilled in the art would recognize that the specification105could relate to any topic or area of interest known in the art, and could be adapted to include any qualifiers and/or parameters related to the particular topic and/or area of interest known in the art.

The meta-agent module110may construct an agent-based system in accordance with the specification105. Upon receiving a specification105from a user104, the meta-agent module110may route the specification105to the agent generator module130, which may be configured to derive a canonical model from the specification105. As will be discussed below, the canonical model may comprise an ontological mapping between the specification105and the ontology134(discussed below). Using the canonical model, the agent generator130may select a set of transforms from a transform ensemble, from which an agent-based system may be generated. In some embodiments, the transforms comprising the agent-based system may be iteratively modified until an optimal agent-based system is identified.

The meta-agent110may include an ontology134, which may be used to develop a canonical model of the specification105, identify concepts associated with data161accessed from various data source(s)160, select transforms for inclusion in an agent-based system, and the like. As used herein, an ontology, such as the ontology134, may refer to an organized collection of knowledge referring to both the meaning of natural language terms (e.g., concepts) and relationships between concepts. In some embodiments, an ontology may be implemented as a graph data structure having a plurality of vertices (e.g., nodes) interconnected by one or more edges. The vertices may refer to concepts within the ontology, and the edges interconnecting the vertices may represent relationships between related concepts within the ontology. The ontology134may be implemented in conjunction with a computing device, such as the computing device101ofFIG. 1B, which may be configured to make ontological information available to other modules and/or devices (e.g., over the network102). The ontology134may comprise computer-readable storage media on which the ontology data structure is embodied including, but not limited to: a dedicated ontology store (e.g., Allegro® or the like); a database (e.g., a Structured Query Language (SQL) database, eXtensible Markup Language (XML) database, or the like); a directory (e.g., an X.509 directory, Lightweight Directory Access Protocol (LDAP) directory, or the like); a file system; a memory; a memory-mapped file; or the like.

In some embodiments, the ontology134may comprise a data access layer (not shown), such as an application-programming interface (API), a remote access protocol (e.g., SOAP, RMI, etc.), or the like. The data access layer may provide for programmatic access to and/or modification of the ontology134(e.g., using a language, such as Semantic Application Design Language (SADL), or the like).

The ontology134may comprise precompiled knowledge in a format suitable for automated processing by the agent generator130. For example, the ontology134may be formatted in Web Ontology Language (OWL or OWL2), Resource Description Format (RDF), Resource Description Format Schema (RDFS), or the like.

The ontology134may be compiled from one or more knowledge sources comprising concepts and relationships between concepts. Such knowledge sources may include, but are not limited to encyclopedias, dictionaries, and the like. In some embodiments, the ontology134may comprise information obtained from an online encyclopedia, such as Wikipedia® (registered trademark of Wikimedia Corp. of San Francisco, Calif.), Encarta® (registered trademark of Microsoft Corp. of Redmond, Wash.), or the like.

In some embodiments, the ontology134may be generated by crawling through the topics of a knowledge source using a web-based crawler, script, or the like. Each resource (e.g., webpage) in the knowledge source may be represented within the ontology134as a concept. Edges (e.g., relationships between concepts) may be extracted by categorization information in the knowledge source, such as links. For example, a knowledge source may comprise links to related material; edges may be created for each link within a particular concept (e.g., concept webpage).

In some embodiments, the ontology134may comprise information from a plurality of different knowledge sources. The ontology134may be adaptive, such that the concepts and/or relationships between concepts may be modified (e.g., strengthened, weakened, created, and/or removed) responsive to machine learning techniques, user feedback, changes to the underlying knowledge sources, or the like.

In some embodiments, the ontology134may change over time responsive to knowledge input into the ontology134and/or feedback received from users (e.g., the agent generator module130, users104, or the like). In addition, the ontology134may be modified responsive to updates to the one or more knowledge sources used to generate the ontology134. As such, the ontology134may comprise an updating mechanism (e.g., crawlers, scripts, or the like) to monitor the one or more knowledge sources underlying the ontology134, and to update the ontology134responsive to changes detected in the respective knowledge sources.

An ontological mapping module136may be configured to associate data (e.g., natural language text, numerical data, or the like) with a corresponding ontological concept. Accordingly, the mapping module136may be configured to map the data161and/or the portions of the agent specification105to one or more concepts within the ontology134. For instance, data161relating to a stock quote may be mapped to a “stock quote” concept within the ontology134. Examples of systems and methods for concept mapping are provided in co-pending U.S. patent application Ser. No. 12/534,676 filed Aug. 3, 2009, and entitled, “Systems and Methods for Concept Mapping,” which is hereby incorporated by reference in its entirety.

As discussed above, the meta-agent module110may receive a specification105directing the meta-agent module110to generate an agent-based system configured to achieve a particular task using a particular set of data. The specification105may be routed to the agent generator module130, which may autonomously or quasi-autonomously generate an agent-based system capable of implementing the specification105.

The agent generator130may be configured to derive a canonical model from the specification105. As discussed above, a canonical model may refer to an ontological mapping between the specification105and the ontology134. Accordingly, the canonical model may identify concepts associated with the tasks defined in the specification105. For instance, if the specification105included a directive to “identify biotechnology company stocks exhibiting an ‘Inverted Cup” pattern in the last 6 months,” the canonical model may include a corresponding directive expressed as logical combination of concepts within the ontology134(e.g., in Common Algebraic Specification Language format, in Common Logic Format (CLF), in Rule Interchange Format (RIF), in OWL, or the like). The canonical model may also include conceptual mappings between data sources identified within the specification105and concepts within the ontology134. For instance, the canonical model derived from a specification105identifying stock ticker data may include a corresponding “stock ticker” concept mapping. The development of a canonical model from the specification105may be performed by the concept mapping module136, which may leverage the concept mapping techniques described above.

Using the canonical model, the agent generator130may programmatically determine the nature of the agent-based system required by the specification105. For example, the agent generator130may include a priori knowledge indicating which machine learning transforms are effective at performing particular ontological tasks (e.g., pattern matching, etc.). Similarly, the agent generator130may know which transforms are effective at preprocessing certain types of data. In addition, the canonical model may allow the agent generator130to identify and/or generate one or more performance metrics whereby sets of candidate transforms may be evaluated and/or compared to one another (e.g., to select an “optimal” set of transforms for inclusion in the agent-based system).

The agent generator130may construct the candidate agent-based systems using transform components available in the meta-agent module110including, but not limited to: a harvester module120, an integration module122, a machine learning module124, the ontology134, and/or the ontology mapping module136. In some embodiments, the agent generator130may be configured to generate a plurality of candidate agent-based systems (each comprising a set of candidate transforms) and to select an “optimal” agent-based system therefrom. The selection may be based upon the performance of the candidate transforms in a testing and/or real-world environment.

The harvester module120may be configured to communicate with one or more external data sources160over the network102to obtain data161therefrom. The external data sources160may comprise any data source known in the art including, but not limited to: databases, such as Structured Query Language (SQL) databases, eXtensible Markup Language (XML) databases, or the like; directory systems, such as an X.509 directory, a Lightweight Directory Access Protocol (LDAP) directory, or the like, a hierarchical and/or flat file system, a sequence of space-delimited values (SDV), natural language content (e.g., text content), web content (e.g., content formatted as Hyper Text Markup Language (HTML) data); delimiter-separated values; formatted data (e.g., data in Portable Document Format (PDF), as a Microsoft® Word Document, etc.); or the like.

The agent generator130may configure the harvester120to access data required by the agent-based system construed thereby (e.g., as defined in the specification105). The harvester120may be configured to access data from particular locations (e.g., from particular data sources160), to access data in particular format, to access data meeting a particular set of qualifications (e.g., produced by researchers having a particular set of qualifications), and so on. For example, if the specification105calls for processing a particular type of data (e.g., financial data, such as stock quotes, earnings information, or the like), the agent generator130may configure the harvester module120to access data161of a particular type and/or from an appropriate data store (e.g., access financial data from an SEC database, stock quote provider, and so on).

The harvester module120may be capable of interacting with different types of external data sources(s)160. For example, if the specification105calls for data accessible via the Internet (e.g., via the network102), the harvester module120may provide a web crawler to crawl one or more web-accessible storage locations (e.g., websites) provided by the data source(s)160. The web crawlers may be configured to interact with the external data source(s)160via Hyper Text Transfer Protocol (HTTP), Secure HTTP (HTTPS), File Transfer Protocol (FTP), Telnet, or any other protocol and/or port provided by the respective external data source160. The harvester module120may be communicatively coupled to the network102by a communications interface (not shown), such as the communication interface158ofFIG. 1B.

In some embodiments, the harvester120may be configured to determine a set of metadata163describing the data161. The metadata163may be used by the integration module122(described below) to parse the data161. The metadata163may be provided by the external data source(s)160, may be provided by the user104, and/or may be automatically determined by the harvester module120. For example, an external data source160may publish metadata163describing the data161provided thereby. The harvester module120may be configured to access the metadata163with the data161. In another example, the user104may access the external data source160directly, and may identify or otherwise indicate to the harvester module120which entries within the data source160are relevant to the user104, provide data type and/or formatting information, specify parsing directives, and the like (e.g., via the interface application112and/or as a plug-in to a browser application). The user-provided information may be used to define metadata163describing the data161obtained from the data source160. Alternatively, or in addition, the specification105provided by the user104(or canonical model derived therefrom) may provide information regarding the external data source(s)160from which the metadata163may be derived. In some embodiments, the harvester module120may automatically determine the metadata163by inter alia mapping data type and/or other information obtained from the external data source(s)160to concepts within an ontology134as described below.

The integration module122may be configured to preprocess the data161received from the external data source(s)160using inter alia the metadata163. The preprocessing may include identifying data that is relevant to the agent-based system within the data161(e.g., parsing the relevant data from a webpage), validating the data161(e.g., based upon data type information), removing corrupt data, qualifying the data161(e.g., based upon requirements defined in the specification105), filtering the data161, cleansing the data161, and so on.

The data161acquired by the harvester module120and preprocessed by the integration module122may be stored in a data store126, which may comprise computer-readable storage media, such as one or more discs, optical media, memory storage, and the like.

The machine learning module124may comprise one or more machine learning algorithms125, which may be used by the agent generator130to generate an agent according to the specification105. In some embodiments, the agent generator130may assemble (e.g., combine) multiple machine learning algorithms125provided by the machine learning module124into a single agent-based system. The agent generator130may be configured to adapt the machine learning algorithms125to perform the tasks defined in the specification105(e.g., by setting algorithm125parameters, combining algorithms125, etc.)

As discussed above, the agent generator module130may derive a canonical model from the specification105using the concept mapping module136and the ontology134. Using the canonical model, the agent generator130may generate an agent-based system comprising a set of transforms (provided by the harvester, integration, and/or machine learning modules120,122, and124). The transforms comprising the agent-based system may be selected according to the canonical model (e.g., the transforms may be selected to interact with data specified in the model, to achieve the tasks in the model, and so on).

In some embodiments, the agent generator module130may iteratively refine the agent-based system until an “optimal” set of transforms is identified. The iterative refinement may comprise iteratively modifying the transforms comprising the agent-based system until a termination criteria is satisfied (e.g., modifying the configuration of the transforms, the arrangement of the transforms, data flow between the transforms, and the like). The modifications may further include the addition, removal, and/or replacement of one or more candidate transforms.

An “optimal” set of transforms may be identified using a performance or fitness metric defined in the canonical model. The fitness metric may quantify how effective the set of transforms is at performing the task defined in the canonical model. The optimization process may comprise a “meta-machine learning technique,” which may include, but is limited to: a genetic algorithm; a local search; a distributed local search; or the like.

During the optimization process, the current state of the one or more sets of candidate transforms may be maintained in the agent data store132. The current state of the transforms system may refer to the configuration of the transforms comprising the system including, but not limited to: the set of candidate transforms included in the system, transform configuration parameters, transform structure parameters, transform structure, including data flow between different transforms, transform ordering, and so on.

In some embodiments, the agent data store132may represent the agent-based system as a two dimensional grid data structure. Each row in the grid may represent a different transform (a data access transform, a preprocessing transform, a machine learning transform, a structural transform, or the like). Columns within each row may represent variations of the transform (e.g., using different configuration parameters, thresholds, or the like). The agent generator130may perform a search within the grid to identify an optimally performing set of transforms.

FIG. 2shows one embodiment of a transform datastructure200. The transform datastructure200could be stored in the agent datastore132ofFIG. 1Afor use by the agent generator130to produce an “optimal” agent-based system. Each row210A-210J in the datastructure200may correspond to a particular transform. The columns212A-212G may correspond to different variants of the transform (e.g., a modification to one or more parameters of the transform or the like).

As discussed above, the transforms of rows210A-210J may correspond to data acquisition transforms, data preprocessing transforms, algorithmic transforms, and/or structural transforms. Although a particular set of transforms is discussed herein, the disclosure is not limited in this regard; the data structure200could be adapted to include any set of data transformations known in the art.

A data acquisition transform may include directives to read data from a data source (e.g., an external data source160ofFIG. 1A). For example, a data acquisition transform may include an instruction to read N number of records of a particular type from a data source at a particular Uniform Resource Indicator (URI) address.

The data structure200may include one or more preprocessing transforms, which may relate to preprocessing of data obtained from one or more data sources. For instance, preprocessing transforms may include, but are not limited to: a select transform to select a particular datum from a particular dataset; a filter transform to filter one or more datasets based on one or more filtering criteria; a derive transform to create a new datum from one or more datasets; an aggregate and/or merge transform to combine two or more datasets into a single set; a standardize transform to reformat a dataset into a particular standardized format; or the like.

Machine learning transforms may be represented within the data structure200. As discussed above, a machine learning transform may implement the data analysis and processing algorithms necessary to perform the tasks defined in the agent specification (e.g., identify “Inverted Cup” patterns within a set of stock quotes). For example, a row210A-210J of the data structure200may represent a decision tree algorithm, such as a Classification and Regression Tree (CART), Multivariate Adaptive Regression Spline (MARS), a C4.5 decision tree, or the like. Another row210A-210J may represent a clustering algorithm, such as a K-means algorithm, a Kohonen algorithm, or the like. Other rows210A-210J may correspond to other machine learning transforms including, but not limited to: a Bayes classifier (e.g., a naïve Bayes algorithm); a neural network algorithm (e.g. a back propagation neural network); a genetic algorithm; K-nearest neighbor; or the like.

Structural transforms may relate to the data flow between the transforms represented in the data structure200. For example, one or more structural transforms may cause an output of a first data acquisition transform to flow to an input of a preprocessing transform, and may cause the output of the preprocessing transform to flow to an input of a machine learning transform, and so on.

The columns212A-212G of each row210A-210J in the data structure200may comprise variants of the respective transform. The columns212A-212G may vary parameters of the transform, inputs to the transform, arrangements of other transforms, or the like. For example, the transform of row210A may comprise a data acquisition transform (implemented by the harvesting module120ofFIG. 1A) configured to obtain data from one or more data sources. The columns212A-212G of row210A may vary the Uniform Resource Indicator (URI) from which the harvest occurs, modify the data obtained at the various data sources, or the like. Other transforms may be varied in a similar manner. For instance, a “merge” data preprocessing transform may be varied according to the particular dataset fields that are merged, the nature of the merge (e.g., averaging, mean, etc.), or the like. Machine learning transforms may be varied by modifying the parameters of the various algorithmic transforms, modifying the datasets input into the transforms, modifying which dataset features are input to the transform, modifying thresholds applied to the transforms, and so on.

Each of the transforms within the datastructure200(e.g., rows210A-210J) may be modified according to a particular column212A-212G associated with the respective transform. In this way, an agent generator, such as the agent generator130ofFIG. 1, may permute one or more transforms to optimize an agent according to a particular specification. In some embodiments, the permutations available between transforms in the datastructure200may be represented as transforms themselves. Such transforms may be referred to as structural transforms. As discussed above, a structural transform may define which transforms may be combined into a particular agent, may determine data flow between agents, may determine how transforms are arranged (e.g., order processing), and so on. For instance, a structural transform may indicate that the output of a particular transform should flow to an input of another transform. For example, the output of a “harvest data” transform could flow to a “merge” transform to preprocess the data, and the output of the “merge” transform could flow to a machine learning transform (e.g., a K-nearest neighborhood transform or the like), and so on. Other structural transforms (“mutation” structural transforms) may call for the removal and/or addition of other transforms in the data structure200, replacement of a first transform with a second transform, or the like.

Referring back toFIG. 1A, the agent generator130may be configured to seed the agent datastore132with a set of candidate transforms, which may be selected according to the canonical model derived from the specification105. The candidate transforms may be represented within the agent data store in a grid data structure as described above. The agent generator130may search for an “optimal” set of transforms within the data structure200. In some embodiments, the searching may comprise the agent generator130iteratively modifying the candidate transforms responsive to testing.

Referring toFIG. 2, the search performed by the agent generator130may comprise iteratively modifying parameters of the transforms of210A-210J and/or the respective parameters212A-212G of the transforms and testing the resulting agent-based system against test and/or live datasets. In some embodiments, the transform modifications may be visualized as traversing the grid data structure (e.g., moving within the columns212A-212G of one or more of the transforms (rows210A-210J)). For example, a particular version212D of a transform210D may be modified according to a modification vector214to use a variant212B of the transform210D. Alternatively, or in addition, transforms may be iteratively added, removed, and/or replaced within the data structure200(e.g., by adding, removing, or replacing a transform in a row210A-210J of the data structure200according to a “mutation” structural transform). For example, a modification216may replace a particular transform210D with another transform210B. The nature of the modification to the transforms and/or transform replacements may be visualized as a localized search with the data structure200. Given the nature of the datastructure200, several independent, parallel optimization searches may be performed at once within different portions of the datastructure200. Accordingly, the optimization process of the agent generator (not shown) may be highly parallelizable.

After each modification, the performance of the resulting set of transforms may be evaluated. The evaluation may comprise applying a “fitness” function to a result produced by the set of transforms (according to user-defined performance criteria). The iterative modifications may continue until an “optimally performing” agent-based system is found. The process of selecting an “optimal” agent-based system, however, may have no closed-form solution. In fact, for the general problem of assembling an agent-based system, it may not be possible to define conditions or closed-form equations capable of identifying an optimal solution. As such, selection of an optimal set of transforms may not be possible using standard, closed form computing techniques (e.g., linear programming, etc.). Therefore, the agent generator130may be configured to use non-linear techniques, such as local search, genetic algorithms, generate and test, line search, Nelder-Mead simplex, gradient descent, Lagrange, and the like to select an optimal set of transforms. The optimization techniques may be adapted to avoid local maxima/minima, minimize processing time (e.g., avoid thrashing), avoid non-convergence, etc.

FIG. 3is a dataflow diagram implemented by one embodiment of an agent generator330, such as the agent generator130ofFIG. 1A. The agent generator330includes a programming module310, which may be configured to perform an optimization function. The agent generator330(including the programming and/or translation modules310and320) may be implemented on and/or in conjunction with a computing device. Accordingly, portions of the agent generator330may be implemented as computing device executable instructions embodied on a computer-readable storage medium (not shown).

The programming module310may comprise a non-linear optimization process, such as a genetic programming process, an evolutionary programming process, a local search, a generate and test programming process, a line search programming process, a Nelder-Mead simplex process, or the like.

The programming module310may receive canonical modeling data311, which, as discussed above, may comprise an ontological mapping between an agent specification and an ontology. The canonical modeling data311may further comprise information relating to one or more datasets to be processed by the agent-based system (e.g., identify ontological concepts corresponding to the data). In some embodiments, the canonical model311data may be determined using an ontology mapping module, such as the ontology mapping module136ofFIG. 1A.

The programming module310may also receive a functional model data312, which may comprise one or more transforms available to the programming module310, such as data preprocessing transforms, machine learning algorithm transforms, structural transforms, and the like provided by the harvester, integration, and machine learning modules120,122, and124ofFIG. 1A. In some embodiments, the functional model data312may be represented as a data structure, such as the data structure200ofFIG. 2.

The programming module310generates one or more candidate agents using the canonical modeling data311and the functional model312. A candidate agent-based system may comprise a set of interconnected transforms. The performance of the candidate agent-based systems may be evaluated using a fitness metric313. The fitness metric may be included and/or derived from the canonical model311. For example, if the canonical model311defines a task to be performed by the agent-based system, the fitness metric313may quantify the performance or “fitness” of a candidate agent-based system at implementing the task (e.g., quantify the ability of a system to identify “Inverted Cup” stock patterns). In some embodiments, the fitness metric313may be evaluated against one or more sets of training data. The training data may comprise data for which a set of “correct” results are known. The fitness metric313may be proportional to the number of “correct” results obtained by a candidate agent-based system. In other embodiments, real world data may be used. In this case, the evaluation of candidate agent performance may be based on an error rate of the candidate agent, as determined by a third-party data source, a human operator, or the like. The fitness metric313may include an efficiency metric, which may quantify the computing resources required by each candidate agent (e.g., quantify the processing time and/or computing resources required to implement each candidate agent).

A set of algorithm parameters314may be used by the programming module310to modify the transforms used by one or more candidate agents. The algorithm parameters314may be stored in an agent data store, such as the agent store module132ofFIG. 1A(e.g., in the two dimensional grid data structure200). The algorithm parameters314may relate to any modification of a candidate transform including, but not limited to: modifying a location (e.g., URI) from which data is read; modifying preprocessing instructions (e.g., filtering rules, data cleansing, etc.); modifying a transform arrangement (e.g., transform selection, ordering, dataflow, etc.); modifying machine learning algorithms parameters (e.g., thresholds, weights, etc.); modifying a structural relationships between transforms; adding, removing, and/or replacing transforms; and the like.

In some embodiments, the algorithm parameters314available to the programming module310may be determined by the capabilities of the transforms used to implement the agent-based system (e.g., by the functional model data312). For example, the functional model data312may indicate which parameters of a particular transform may be modified, provide modification thresholds, and so on.

The programming module310may further receive termination criteria315. As discussed above, the identification of an optimal agent-based system may be an iterative process having no closed-form solution. As such, it may be difficult for the programming module310to known when an optimal solution has been reached (e.g., as opposed to a local maxima/minima or the like). The termination criteria315may define when the programming module310is to stop iteratively searching for an “optimal” agent-based system. For example, the termination criteria315may specify a fitness threshold of an “optimal” system (e.g., minimal error on the training set and/or real-time data, iteration count, etc.). In some embodiments, the termination criteria315may comprise an iteration count to limit the number of permutations investigated by the programming module310. In other embodiments, the termination criteria315may comprise an improvement rate metric to terminate the search if successive iterations do not significantly improve the performance of the agents. Such a termination criteria315may comprise local minima and/or local maxima detection.

The programming module310may use the inputs311,312,313,314, and315to search for an optimal agent output316. As discussed above, the programming module310may use any of a plurality of different processes to determine an optimal agent316. Examples of such processes are described in additional detail below.

The output316of the programming module310may comprise an agent-based system capable of performing the tasks defined in the canonical model input311. The optimal agent output316may comprise a set of transforms executable by a computing system, such as a general purpose computing system (e.g., a personal computing system or the like), a special purpose computing system (e.g., an Application Specific Integrated Circuit (ASIC) based computing system, a Field Programmable Gate Array (FPGA) based computing system, or the like), a mobile computing system, or the like.

In some embodiments, the optimal agent output316may flow to a translation module320, which may be configured to translate the agent output316into a translation321of the optimal agent, which is configured to be executable by a particular type of computing device. For example, the optimal agent316may be translated into computing device executable code (e.g., compiled code). The translation321may be adapted to be executed by a computing device of a particular type (e.g., an X.86 processor, a particular type of RISC processor, a particular type of ASIC, or the like). In some embodiments, the translation321of the optimal agent316may comprise a plurality of computer executable modules capable of being executed by a plurality of computing devices (e.g., in a distributed computing environment, such a grid computing environment or the like). For example, the translation321may comprise a plurality of Enterprise Java Beans (EJB) executable by one or more J2EE servers or the like.

In some embodiments, the translation321may be embodied in a computing-device interpretable language that may be consumed (interpreted) by another computing device. For instance, the optimal agent316may be expressed as an XML data structure defining an agent-based system (e.g., defining the transforms comprising the system, the configuration of the transforms, the data flow and/or ordering of the transforms, and so on). The data structure in the translation321may be interpretable by another computing device (not shown) to implement the agent-based system defined thereby. Accordingly, the translation321produced by the translation module320may comprise an intermediate language interpretable by a plurality of different computing devices configured to interpret the data structure, to generate and/or obtain computing-device executable code corresponding to the transforms within the datastructure, and to implement the agent defined by the datastructure.

Although not shown inFIG. 3, the optimal agent output316and/or translation321may be stored in a computer-readable storage media (not shown), such as a database. In this way, the optimal agent316and the translation321thereof may be made available to one or more users and/or computing devices at a later time. Similarly, the optimal agent output316and/or translations321thereof may be transmitted to one or more users for use by the one or more users and/or remote computing devices over a data communications network, such as network102ofFIG. 1A.

FIG. 4is a flow diagram of one embodiment of a method for generating an agent-based system. The method400may be implemented by a programming module, such as the programming module310ofFIG. 3and/or an agent generator, such as the agent generator130ofFIG. 1A. The method400may comprise one or more computer-executable instructions. The instructions comprising the method400may be implemented as one or more distinct software modules. The instructions and/or software modules may be embodied on a computer-readable storage medium, such as a disc, optical storage medium, memory, or the like. In some embodiments, one or more steps of the method400may be tied to particular machine components, such as computer-readable storage media, communications interfaces, processing modules, or the like.

At step405, the method400may be initialized, which may comprise loading instructions comprising the method400from a computer-readable storage media, allocating resources for the process400, initializing allocated resources, and the like.

At step410, the method400may receive a request to generate an agent system. The request of step410may comprise a specification, such as the specification105ofFIG. 1A. The specification may be generated by a human user and/or may have been automatically generated by another process and/or computing device responsive to a user request (e.g., a search query or the like). The specification may identify one or more tasks to be performed by an agent-based system. Alternatively, or in addition, the specification may identify one or more data sources and/or data types to be processed by the agent-based system.

At step420, the tasks and/or data identified in the request may be mapped to one or more concepts within an ontology as described above. The mapping may comprise comparing one or more terms within the request to one or more concepts within the ontology. In some embodiments, the mapping may further comprise disambiguating between candidate concepts using a spreading activation algorithm or the like.

The concepts identified at step420may be used to form a canonical model of the request at step425. The canonical model may include an ontological representation of the agent specification received at step410. In some embodiments, the request received at step410may include a canonical model. For example, the request may be provided in an ontological format, such as CLF, RIF, OWL, or the like. If so, the mapping and modeling steps420and425may be omitted. Alternatively, or in addition, if the canonical model refers to a different ontology, a translation step may be included, which may translate the canonical model in the request into an ontology used by the method400.

At step430, a set of candidate transforms comprising an agent-based system may be selected. The candidate transforms comprising the agent-based system(s) may be selected using the canonical model determined at step425. (e.g., the transforms may be selected according to the tasks defined in the canonical model425, the data types specified in the model425, and so on). The selection of step430may be based upon a priori knowledge regarding which transforms are likely to be effective at performing the tasks and/or processing the data types specified in the canonical model. For example, if the canonical model calls for a group classification, the agent-based system may include a naïve Bayes machine learning transform.

The candidate transforms selected at step430may be represented as a set of interconnected transforms (e.g., in a grid data structure, such as the data structure200ofFIG. 2). Modifications to an agent-based system represented in graph form may be made by: modifying a particular transform in the graph (e.g., modifying a parameter of the transform or the like); modifying a relationship between transforms (e.g., changing the order of transforms within the graph or the like); adding and/or removing transforms from the graph; or any other graph- or grid-based operation.

As discussed above, the selection of the candidate transforms at step430may leverage stored expert knowledge expressed as one or more rules. For example, expert knowledge may indicate that a particular machine learning algorithm (e.g., transform) is effective at processing a particular data type and/or effective at performing a particular type of task. The method400may compare the canonical model to this expert knowledge to identify one or more transforms likely to yield an effective agent-based system.

At step440, the set of candidate transforms defined at step430may be used to identify an optimal agent. As such, at step440, the method400may iterate over one or more variations of the candidate transforms. The iteration of step440may be part of a non-linear, meta-machine learning algorithm, such as a genetic algorithm, an evolutionary programming algorithm, or the like. Accordingly, one iteration of the step440through448may comprise a single “generation” of the candidate transforms. As will be discussed below, each iteration of the steps440-448may cause one or more of the candidate transforms to be modified (e.g., mutated). The modification may result in a better performing agent-based system.

The various iterations and/or modifications of step440through448may be independent of one another. As such, the resulting iterations over steps440-448may be highly parallelizable. Accordingly, in some embodiments, multiple iterations of the steps of440-448may be performed concurrently using parallel threads (on a single and/or multi-core processor), on distributed processors within a particular computing device, on a plurality of distributed computing systems, or the like.

At step442, the performance of each set of candidate transforms may be evaluated. As discussed above, the performance evaluation may comprise providing an agent-based system (comprising a set of candidate transforms) with a set of input data and evaluating the results provided thereby. The performance of the candidate system may relate to the ability of the system to perform the tasks defined in the canonical model (e.g., based upon an error rate of the candidate transforms). The data may comprise a set of test data, for which a known solution exists. In other embodiments, the performance evaluation of step442may comprise applying real-world, “in-process” data to an agent and determining an error rate thereof (e.g., using a third-party service, another agent-based system, a human operator, or the like).

At step444, the method400may determine whether a particular set of candidate transforms should be retained. In embodiments employing algorithms having fixed population of candidates (e.g., genetic and/or evolutionary processes), one or more high performing members of the population may be retained across multiple iterations440. This may allow the highly performing candidates to mutate multiple times while preventing the method400from becoming “stuck” on a local minima. Additional candidates may be retained on a random basis and/or based on the performance of the candidate as compared to other candidates in the generation. If, at step444, the candidate should be retained, the flow may continue to step445, where the process may retain the candidate for further processing (e.g., by storing the candidate in a datastructure, marking a field in a datastructure associated with the candidate, or the like); otherwise, the candidate may be discarded.

At step446, termination criteria may be evaluated to determine whether the iteration of step440should continue. As discussed above, the iterative steps440-448may comprise a termination criteria indicating when the process400should stop looking for increasingly optimal results. The termination criteria may be associated with a maximum number of iterations, a target performance threshold, a rate of change metric, a derivative metric, or the like. If the termination criteria are satisfied, the flow may continue to step450; otherwise, the flow may continue to step448.

At step448, the current set of candidate transforms may be modified (e.g., mutated) according to the algorithm implemented by the process400. The mutation may comprise performing a grid-based modification as described above (e.g., implementing a variation defined within the data structure200ofFIG. 2). In some embodiments, the original (non-mutated) set of candidate transforms (or a record thereof) may be retained in the candidate pool. This may allow original, non-mutated set of candidate transforms to be reconstructed in the event that the method400determines that the current set of transforms is “optimal.”

In some embodiments, the modification of step448may comprise traversing the grid data structure200ofFIG. 2. As discussed above, in some embodiments, a set of candidate transforms may be embodied as a grid of transforms with rows representing transforms, and columns representing transform variations. A modification at step448may comprise selecting a variant of a particular transform by selecting an alternative column within the data structure200, selecting a different transform type by selecting an alternative row within the data structure200, or the like. Examples of such modifications are described above in conjunction withFIG. 2.

In other embodiments, an agent-based system may be represented in another data structure, such as an interconnected graph, in which transforms are represented as vertices and data flow by graph edges. In these embodiments, a modification at step448may comprise, but is not limited to: adding a new transformation to the graph (e.g., as a new graph vertex); removing a transformation from the graph (e.g., removing a graph vertex); adding and/or substituting a vertex in the graph; modifying an order of vertices within the graph; modifying vertex connections; and the like. Other transforms may comprise modifying a parameter of a transform by modifying a graph vertex.

Step448may impose preconditions defining which transformations may be made to the candidate transforms. For instance, certain structural modifications may result in an inoperable agent (e.g., removing all “harvest data” steps, placing incompatible transforms in series, and so on). Accordingly, the method400may include one or more preconditions, which may determine which modifications may be made to a set of candidate transforms and which may not. In addition, step448may comprise a validation step, in which the modified candidate transforms are validated as forming an operable agent-based system.

Following the modification of step448, the flow may continue to step440, where the iteration may continue.

At step450, the iteration of steps440-448may terminate. Responsive to the termination, the method400may select the “optimal” set of candidate transforms from the remaining candidates (or a previous recorded candidate transforms). The “optimal” candidate may be the highest performing candidate (e.g., the candidate having the highest performance according to one or more fitness metrics). In some embodiments, other factors may be used in determining which candidate is “optimal.” For example, a size and/or computational complexity of the agent-based systems may be evaluated. A simpler and/or faster agent-based system may be considered to be more optimal relative to a similarly performing larger and/or more computationally expensive system.

At step455, the selected agent-based system may be stored for use by one or more users and/or external processes. In addition, as discussed above, the selected agent may be translated into a format that is consumable by the one or more users and/or external processes. At step460, the flow may terminate.

The above description provides numerous specific details for a thorough understanding of the embodiments described herein. However, those of skill in the art will recognize that one or more of the specific details may be omitted, or other methods, components, or materials may be used. In some cases, operations are not shown or described in detail.

Furthermore, the described features, operations, or characteristics may be combined in any suitable manner in one or more embodiments. It will also be readily understood that the order of the steps or actions of the methods described in connection with the embodiments disclosed may be changed as would be apparent to those skilled in the art. Thus, any order in the drawings or Detailed Description is for illustrative purposes only and is not meant to imply a required order, unless specified to require an order.

Embodiments may include various steps, which may be embodied in machine-executable instructions to be executed by a general-purpose or special-purpose computer (or other electronic device). Alternatively, the steps may be performed by hardware components that include specific logic for performing the steps or by a combination of hardware, software, and/or firmware.

It will be understood by those having skill in the art that many changes may be made to the details of the above-described embodiments without departing from the underlying principles of the disclosure.