US 8,209,274 B1Grant
Predictive model importation
Issue Date:2012-06-26
•27 Claims
•6 Drawing Sheets
Abstract
Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for obtaining a plurality of representations of predictive models, each representation having been received from a different client wherein each representation is associated with a respective user and comprises a description of a respective predictive model, and selecting a model implementation from a plurality of model implementations for each of the obtained representations.
Metadata
Assignee
- Google Inc.
Inventors
- Wei-Hao Lin
- Travis H. K. Green
- Robert Kaplow
- Gang Fu
- Gideon S. Mann
Application Information
Application Number:US 13/277,052
Filing Date:2011-10-19
Priority Date:2011-05-09
Art Unit:2129
Classifications
IPC:
G06F15/18G06E1/00G06E3/00G06G7/00
Patent Drawings (6 sheets)
Description
Cross-Reference to Related Applications
[0001] Under 35 U.S.C. §119, this application claims benefit of pending U.S. Provisional Application Ser. No. 61/484,157, filed May 9, 2011, the entire contents of which are hereby incorporated by reference.
Background
[0002] This specification relates to importation and use of predictive models.
[0003] Predictive modeling generally refers to techniques for extracting information from data to build a model that can predict an output from a given input. Predicting an output can include predicting future trends or behavior patterns, or performing sentiment analysis, to name a few examples. Various types of predictive models can be used to analyze data and generate predictive outputs. Examples of predictive models include Naive Bayes classifiers, k-nearest neighbor classifiers, support vector machines, and logistic regression techniques, for example. Typically, a predictive model is trained with training data that includes input data and output data that mirror the form of input data that will be entered into the predictive model and the desired predictive output, respectively. The amount of training data that may be required to train a predictive model can be large, e.g., in the order of gigabytes or terabytes. The number of different types of predictive models available is extensive, and different models behave differently depending on the type of input data. Additionally, a particular type of predictive model can be made to behave differently, for example, by adjusting the hyper-parameters or via feature induction or selection.
Summary
[0004] In various implementations, predictive models can be imported into a system that selects implementations for the models based on factors such as a user's status, for instance. Different model implementations of a particular model (e.g., a Naive Bayes classifier) vary in the amount of parallelization they can achieve. Larger model implementations can utilize a large number of servers, for example. Model implementations can be associated with nodes in a graph so that the output of one model serves as the input to another. The order of model implementation execution is prescribed by the graph and, depending on the edges the graph, may allow some models implementations to be executed in parallel with each other.
[0005] In various implementations, predictive models can be imported into a system that selects implementations for the models based on factors such as a user's status, for instance. Different model implementations of a particular model (e.g., a Naive Bayes classifier) vary in the amount of parallelization they can achieve. Larger model implementations can utilize a large number of servers, for example. Model implementations can be associated with nodes in a graph so that the output of one model serves as the input to another. The order of model implementation execution is prescribed by the graph and, depending on the edges the graph, may allow some models implementations to be executed in parallel with each other.
[0006] In general, one aspect of the subject matter described in this specification can be embodied in methods that include the actions of obtaining a plurality of representations of predictive models, each representation having been received from a different client wherein each representation is associated with a respective user and comprises a description of a respective predictive model; selecting a model implementation from a plurality of model implementations for each of the obtained representations based on a status of the representation's respective user, the model implementation comprising one or more computer programs operable to execute on one or more computing devices; and associating each of one or more of the model implementations with a node in a directed graph wherein for one or more ordered pairs of nodes in the graph the prediction output of a model implementation associated with a first node in the pair serves as input to a model implementation associated with a second node in the pair. Other embodiments of this aspect include corresponding systems, apparatus, and computer programs.
[0007] These and other aspects can optionally include one or more of the following features. Each associated model implementation can be executed in an order prescribed by the graph. A particular model representation can be a Predictive Model Markup Language document. A particular model representation can be a textual representation. A predictive model can be a Naive Bayes classifier, a k-nearest neighbor classifier, a support vector machine, or a predictive model that uses a logistic regression technique. At least two of the predictive models can be different. A particular model implementation can be a map-reduce implementation. A number of computing devices used for a particular model implementation can be based at least in part on the status of the representation's respective user. Obtaining the plurality of representations further comprises performing pre-processing or post-processing operations in parallel for a particular representation in the plurality of representations.
[0008] Particular embodiments of the subject matter described in this specification can be implemented so as to realize one or more of the following advantages. Predictive models can be trained in third party systems and imported for use in systems described herein. Model implementations can be selected based user properties, available resources, other information, or combinations of these. Model implementations can be executed in concert with each other based on the order prescribed by a directed graph. This allows the prediction output of some models to serve as the input to other models. For example, a model that determines the sentiment of an article can provide a prediction of the sentiment to another model that predicts who the author of the document is.
[0009] The details of one or more embodiments of the subject matter described in this specification are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the subject matter will become apparent from the description, the drawings, and the claims.
Brief Description of the Drawings
[0010] FIG. 1 illustrates the importation of a predictive model into an example system.
[0011] FIG. 2 illustrates an example predictive modeling system.
[0012] FIG. 3 illustrates an example directed graph for use in executing predictive models.
[0013] FIG. 4 is a flowchart of an example process for executing predictive models.
[0014] FIG. 5 is a schematic diagram of an example server.
[0015] Like reference numbers and designations in the various drawings indicate like elements.
Detailed Description
[0016] In various implementations, a predictive model (or “model”) is either a categorical model if its predictions are categories, or is a regression model if its predictions are numeric. A predictive model is trained using training data. Training data encompasses examples that each comprise one or more data fields plus an answer (a category or a numeric value) for that example. By way of illustration, the training data in TABLE 1 consists of examples that are email message subject lines and a category that indicates whether each example represents SPAM or not.
[0017]
| TABLE 1 | ||
|---|---|---|
| EMAIL SUBJECT LINE | ANSWER | |
| “You have won $$$” | “spam” | |
| “Lose weight fast!” | “spam” | |
| “Lowest interest rates ever!” | “spam” | |
| “How are you?” | “not spam” | |
| “Trip to New York” | “not spam” | |
[0018] After a model has been trained against training data, queries can be submitted to the model. In some implementations, queries are similar in form to training examples: that is, a query has the same or fewer data fields but does not include the answer. The trained model uses patterns that it learned from the training data to either find the closest category for the submitted query (if it is a categorical model) or estimate a value for the query (if it is a regression model), and returns the category or value.
[0019] A model can be expressed as a model representation to allow models to be exchanged between systems. In some implementations, the model representation is a Predictive Model Markup Language (PMML) document. PMML is an eXtensible Markup Language (XML)-based language. Other model representations are possible such as, for example, formatted or unformatted text, an database (e.g., an SQL database), or a sparse vector. The PMML specification is an XML schema. Instances of models are XML documents that conform to the schema. A PMML document can represent more than one model. Generally speaking, a PMML document can contain some or all of the information described in TABLE 2. The PMML document can also contain information not described in TABLE 2.
[0020]
| TABLE 2 | ||
|---|---|---|
| SECTION | DESCRIPTION | |
| Header | The header contains general information | |
| about the PMML document, such as | ||
| copyright information for the model, its | ||
| description, and information about the | ||
| application used to generate the model. | ||
| Data Dictionary | The data dictionary contains definitions | |
| for all the possible fields used by the | ||
| model. | ||
| Data | The data transformations specify | |
| Transformations | mappings of user data into different | |
| forms to be used by the model. | ||
| Model | Contains the definition of the particular | |
| model. | ||
| Mining Schema | The mining schema lists all fields used | |
| in the model. This can be a subset of the | ||
| fields as defined in the data dictionary. | ||
| It contains specific information about | ||
| each field, such as the field's name and | ||
| what should happened when there is a | ||
| missing value. | ||
| Targets | Targets specify post-processing for the | |
| predicted value. | ||
| Output | The output provides a name any output | |
| fields expected from the model, including | ||
| the predicted value. | ||
[0021] FIG. 1 illustrates the importation of a predictive model into an example system 100. A user 102 interacts with a client computing device 104 (or “client”) to access a model importer 110 web application for importing a model representation 116. A web application executes on one or more server computing devices (or “servers”) that are accessed over a network 106, such as the Internet, by the user 102. Software that implements the model importer 110 executes on one or more servers in a data warehouse 108, for instance, that houses hundreds or thousands of servers. The user 102 can interact with the model importer 110 by using a web browser or other software that executes on the client 104. User data files such as model representations (e.g., model representation 116) that are accessed, modified or created by the model importer 110 can be stored in repositories that are accessible to the servers. The model importer 110 can provide a graphical user interface (GUI) to the client 104 by sending the client 104 Hypertext Markup Language (HTML) documents or other information that can be used to render the GUI.
[0022] The model importer 110 interprets the model representation 116 and either emits a intermediate representation 112 or a model implementation 114. By way of illustration, if the model representation 116 is a PMML document, an XML parser can be used to translate the document into the intermediate representation 112. The intermediate representation 112 is an internal representation of the model representation 116 from which a model implementation 114 can be generated or selected (if the implementation has already been generated). In some implementations, the intermediate representation 112 is a data structure that encodes the information of the model representation 116 to allow for rapid generation or selection of a model implementation 114.
[0023] A model implementation 114 can be generated or selected directly from the model representation 116 or from the intermediate representation 112. The model implementation 114 is one or more computer programs that execute on one or more servers. In some implementations, the type of model implementation 114 is chosen based on the user's status, available resources, or both. This is described further below with reference to FIG. 2 . For example, the model implementation can be a computer program that is designed to execute on a single server or it can be designed to execute on multiple servers. An example of the later approach is a model implemented as a map-reduce system. A map-reduce system includes application-independent map modules configured to read input data and to apply at least one application-specific map operation to the input data to produce intermediate data values. The map operation is automatically parallelized across multiple servers. Intermediate data structures are used to store the intermediate data values. Application-independent reduce modules are configured to retrieve the intermediate data values and to apply at least one application-specific reduce operation to the intermediate data values to provide output data. The map-reduce system is described further in U.S. Pat. No. 7,650,331, entitled “System and method for efficient large-scale data processing,” which is incorporated by reference herein in its entirety.
[0024] FIG. 2 illustrates an example predictive modeling system 200. The system 200 includes one or more clients (clients 202, 204 and 206) that can communicate through one or more networks 106 with a collection of remote servers, such as servers deployed in a data center 108 or in different geographic locations. A given server comprises one or more data processing apparatus. The servers can communicate with each other and with storage systems (e.g., model representation storage system 214 and model graph storage system 216) at various times using one or more computer networks or other communication means. For example, the servers in the data center 108 can be coupled to an intranet. A computer program can execute on a single server or, alternatively, the program can be organized into components that execute on multiple servers. There can be more than one instance or copy of a given computer program executing on the collection of servers at any given time. Multiple copies of a computer program that implements a model implementation or a model executor, for instance, can be executing at the same time on one or more servers.
[0025] Computer programs can be executed in parallel by the servers. Two computer programs are executed in parallel if they are executed on different servers and if at least a portion of their execution occurs at the same time. For example, assume that computer program A is executed on server S1 and computer program B is executed on server S2. If some period of time exists where program A and B are both being executed, then the programs are executed in parallel.
[0026] The servers execute computer programs that implement model implementations 208, an implementation selector 210, and model executors 212. The model executors 212 can use the implementation selector 210 to select model implementations 208 to execute based on various factors. A given model (e.g., a support vector machine) can have a number of different possible model implementations. In some implementations, there are predetermined model implementations. For example, there can be small, medium and large implementations. A small model implementation uses the resources of a single server, a medium model implementation has a parallelized implementation (e.g., a map-reduce model implementation) that uses the resources of N servers, and a large implementation has a parallelized implementation that uses the resources of P servers, where P>N. Of course, P and N can be varied dynamically based on the available resources of the system 200 (e.g., the number of a servers that are available to execute a portion of the model implementation) and other factors. Some model implementations can also perform pre-processing (see “data transformations” in TABLE 2) and post-processing (see “targets” in TABLE 2) in parallel. Model training and prediction can be performed faster on models implementations that utilize more servers those that utilize fewer. In some implementations the user can choose which model implementation they desire.
[0027] The implementation selector 210 is used by the predictive model importer 110 (FIG. 1 ) or by the model executors 212 to select a specific implementation for an imported model representation based on user properties, available resources, other information, or combinations of these. (Model executors 212 are described further below.) One user property is a user's status. Users (e.g., users 202a, 204a, and 206a) can each be associated with a respective status to indicate the type of user they are such as, for example, “very important user”, “test user”, and so on. Other types of user status are possible. A model implementation can be selected based on the user's status. Users who are very important, for instance, can be assigned a model implementation that executes faster than model implementations for test users. In various implementations, larger model implementations (e.g., medium or large) are selected for very important users whereas smaller model implementations (e.g., small) are selected for users of lesser status.
[0028] Other user properties are the amount of system 200 resources the user has consumed over a given time period, the time of day the user typically trains or queries their models, and the amount of money the user has paid to utilize the system 200. The amount of resources consumed can be—for one or more servers—the amount of computer memory consumed, the amount of CPU processing time consumed, the amount of information sent or received on a computer network, or combinations of these. In some implementations, users are assigned resource quotas and model implementations are selected based the amount of unused resources according to the user's quota. For example, a user may configure the system to provide the fastest model implementation that is estimated not to exceed the user's unused resource quota.
[0029] The time of day that a user typically trains or queries their models can, in some implementations, determine the speed of the model implementation used. During off peak hours faster and/or more computationally-intensive model implementations can be used, for example. The amount of money a user has paid to utilize the system 200 can be a flat rate, or based on actual usage. In the former case, the user may pay for a level or grade of service which determines the size of model implementations that are available to them. In the latter case, the user is charged for the system 200 resources they consume so that if the user (or the system 200) selects larger model implementations, the user will be charged accordingly. In some implementations, the user's remaining account balance determines which model implementations are selected based an estimate of what the user will be charged for the usage. That is, the most accurate and fastest model implementation possible is selected that is not estimated to result in a negative account balance based on system 200 usage.
[0030] The model executors 212 execute the model implementations according to an order prescribed by respective directed graphs assigned to the model executors 212. A directed graph or digraph is a pair G=(V, E) where V is a set nodes and E is a set of ordered pairs of nodes or “edges”. An edge e=(x, y) is considered to be directed from node x to node y; y is called the head and x is called the tail of the edge; y is said to be a direct successor of x, and x is said to be a direct predecessor of y. If a path made up of one or more successive edges leads from x to y, then y is said to be a successor of x, and x is said to be a predecessor of y. FIG. 3 illustrates an example directed graph 300 for use in executing predictive models. The graph 300 contains nodes A 302, B 306, C 304, D 308 and E 310. The edges of the graph 300 are indicated by directed lines between nodes and are as follows: (A, C), (B, D), (C, D), and (D, E).
[0031] In various implementations, each node of the graph 300 is associated with a model implementation. A model executor executes model implementations by following the edges in the graph 300. The prediction output of a model implementation associated with a direct predecessor serves as input to the model implementation associated with the direct successor. In this example, the output of the model implementation associated with node A 302 serves as input to the model implementation associated with node C 304. The input to the model implementation associated with node D 308 is the output of the model implementations associated with nodes C 304 and B 306. The output of the model implementation associated with node D 308 serves as input to the model implementation associated with node E 310. The model executor can utilize dependencies in the graph to determine if model implementations can be executed in parallel. For example, the execution of the model implementation associated with node B 306 can occur in parallel with the execution of the model implementations associated with nodes A 302 and C 304 since there are no edges between A 302 and B 306, and between C 304 and B 306.
[0032] FIG. 4 is a flowchart of an example process 400 for executing predictive models. Representations (e.g., model representation 116) of predictive models are obtained from clients (e.g., clients 202, 204 and 206) by, for example, the model importer 110 (step 402). Each representation is associated with a user (e.g., users 202a, 204a, and 206a) and comprises a description of a respective predictive model, such as a PMML document. A model implementation is selected for each of the model representations (e.g., by the implementation selector 220; step 404). The model implementations can be selected based on a status of the associated user, for example, or other properties. Each model implementation is associated with a node in a graph, such as graph 300 (step 406). The model implementations are then executed by the model executor 212, for example, in the order prescribed by the graph (step 408).
[0033] FIG. 5 is a schematic diagram of an example server. The server 502 is optionally connected to one or more user or client computers 590 through a network 580. The server 502 consists of one or more data processing apparatuses. While only one data processing apparatus is shown in FIG. 5 , multiple data processing apparatus can be used. The server 502 includes various software modules, e.g. executable software programs or libraries, including one or more of: a model importer 504, a model implementation 506, an implementation selector 508, and a model executor 510. Although several software modules are illustrated, there may be fewer or more software modules. Moreover, the software modules can be distributed on one or more data processing apparatus connected by one or more networks or other suitable communication mediums.
[0034] The server 502 also includes hardware or firmware devices including one or more processors 512, one or more additional devices 514, a computer readable medium 516, a communication interface 518, and one or more user interface devices 520. Each processor 512 is capable of processing instructions for execution within the server 502. In some implementations, the processor 512 is a single or multi-threaded processor. Each processor 512 is capable of processing instructions stored on the computer readable medium 516 or on a storage device such as one of the additional devices 514. The server 502 uses its communication interface 518 to communicate with one or more computers 590, for example, over a network 580. Examples of user interface devices 520 include a display, a camera, a speaker, a microphone, a tactile feedback device, a keyboard, and a mouse. The server 502 can store instructions that implement operations associated with the modules described above, for example, on the computer readable medium 516 or one or more additional devices 514, for example, one or more of a floppy disk device, a hard disk device, an optical disk device, or a tape device.
[0035] Embodiments of the subject matter and the operations described in this specification can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the subject matter described in this specification can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions, encoded on computer storage medium for execution by, or to control the operation of, data processing apparatus. Alternatively or in addition, the program instructions can be encoded on an artificially-generated propagated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode information for transmission to suitable receiver apparatus for execution by a data processing apparatus. A computer storage medium can be, or be included in, a computer-readable storage device, a computer-readable storage substrate, a random or serial access memory array or device, or a combination of one or more of them. Moreover, while a computer storage medium is not a propagated signal, a computer storage medium can be a source or destination of computer program instructions encoded in an artificially-generated propagated signal. The computer storage medium can also be, or be included in, one or more separate physical components or media (e.g., multiple CDs, disks, or other storage devices).
[0036] The operations described in this specification can be implemented as operations performed by a data processing apparatus on data stored on one or more computer-readable storage devices or received from other sources.
[0037] The term “data processing apparatus” encompasses all kinds of apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, a system on a chip, or multiple ones, or combinations, of the foregoing The apparatus can include special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit). The apparatus can also include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, a cross-platform runtime environment, a virtual machine, or a combination of one or more of them. The apparatus and execution environment can realize various different computing model infrastructures, such as web services, distributed computing and grid computing infrastructures.
[0038] A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, declarative or procedural languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, object, or other unit suitable for use in a computing environment. A computer program may, but need not, correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language resource), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub-programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network.
[0039] A system of one or more computers can be configured to perform particular operations or actions by virtue of having software, firmware, hardware, or a combination of them installed on the system that in operation causes or cause the system to perform the actions. One or more computer programs can be configured to perform particular operations or actions by virtue of including instructions that, when executed by data processing apparatus, cause the apparatus to perform the actions.
[0040] The processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform actions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit).
[0041] Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read-only memory or a random access memory or both. The essential elements of a computer are a processor for performing actions in accordance with instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto-optical disks, or optical disks. However, a computer need not have such devices. Moreover, a computer can be embedded in another device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio or video player, a game console, a Global Positioning System (GPS) receiver, or a portable storage device (e.g., a universal serial bus (USB) flash drive), to name just a few. Devices suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.
[0042] To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. In addition, a computer can interact with a user by sending resources to and receiving resources from a device that is used by the user; for example, by sending web pages to a web browser on a user's client device in response to requests received from the web browser.
[0043] Embodiments of the subject matter described in this specification can be implemented in a computing system that includes a back-end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front-end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the subject matter described in this specification, or any combination of one or more such back-end, middleware, or front-end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), an inter-network (e.g., the Internet), and peer-to-peer networks (e.g., ad hoc peer-to-peer networks).
[0044] The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other. In some embodiments, a server transmits data (e.g., an HTML page) to a client device (e.g., for purposes of displaying data to and receiving user input from a user interacting with the client device). Data generated at the client device (e.g., a result of the user interaction) can be received from the client device at the server.
[0045] While this specification contains many specific implementation details, these should not be construed as limitations on the scope of any inventions or of what may be claimed, but rather as descriptions of features specific to particular embodiments of particular inventions. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination.
[0046] Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.
[0047] Thus, particular embodiments of the subject matter have been described. Other embodiments are within the scope of the following claims. In some cases, the actions recited in the claims can be performed in a different order and still achieve desirable results. In addition, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In certain implementations, multitasking and parallel processing may be advantageous.
Claims
Certificate of Correction present
The claims shown below may not include correction changes. Use the corrected PDF for authoritative text.
What is claimed is:
1. A computer-implemented method, the method comprising:
obtaining a plurality of representations of predictive models, each representation having been received from a different client wherein each representation is associated with a respective user and comprises a description of a respective predictive model;
selecting a model implementation from a plurality of model implementations for each of the obtained representations based on a status of the representation's respective user, the model implementation comprising one or more computer programs operable to execute on one or more computing devices; and
associating each of one or more of the model implementations with a node in a directed graph wherein for one or more ordered pairs of nodes in the graph the prediction output of a model implementation associated with a first node in the pair serves as input to a model implementation associated with a second node in the pair.
2. The method of claim 1, further comprising executing each associated model implementation in an order prescribed by the graph.
3. The method of claim 1 wherein a particular representation is a Predictive Model Markup Language document.
4. The method of claim 1 wherein a particular representation is a textual representation.
5. The method of claim 1 wherein a particular predictive model is a Naive Bayes classifier, a k-nearest neighbor classifier, a support vector machine, or a predictive model that uses a logistic regression technique.
6. The method of claim 5 wherein at least two of the predictive models are different.
7. The method of claim 1 a particular model implementation is a map-reduce implementation.
8. The method of claim 1 a number of computing devices for a particular model implementation is based at least in part on the status of the representation's respective user.
9. The method of claim 1 wherein obtaining the plurality of representations further comprises performing pre-processing or post-processing operations in parallel for a particular representation in the plurality of representations.
10. A system comprising:
data processing apparatus configured to execute instructions which cause the data processing apparatus to perform operations comprising:
obtaining a plurality of representations of predictive models, each representation having been received from a different client wherein each representation is associated with a respective user and comprises a description of a respective predictive model;
selecting a model implementation from a plurality of model implementations for each of the obtained representations based on a status of the representation's respective user, the model implementation comprising one or more computer programs operable to execute on one or more computing devices; and
associating each of one or more of the model implementations with a node in a directed graph wherein for one or more ordered pairs of nodes in the graph the prediction output of a model implementation associated with a first node in the pair serves as input to a model implementation associated with a second node in the pair.
11. The system of claim 10, further comprising executing each associated model implementation in an order prescribed by the graph.
12. The system of claim 10 wherein a particular model representation is a Predictive Model Markup Language document.
13. The system of claim 10 wherein a particular model representation is a textual representation.
14. The system of claim 10 wherein a particular predictive model is a Naive Bayes classifier, a k-nearest neighbor classifier, a support vector machine, or a predictive model that uses a logistic regression technique.
15. The system of claim 14 wherein at least two of the predictive models are different.
16. The system of claim 10 wherein a particular model implementation is a map-reduce implementation.
17. The system of claim 10 wherein a number of computing devices used by a particular model implementation is based at least in part on the status of the representation's respective user.
18. The system of claim 10 wherein obtaining the plurality of representations further comprises performing pre-processing or post-processing operations in parallel for a particular representation in the plurality of representations.
19. A storage medium having instructions stored thereon that, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising:
obtaining a plurality of representations of predictive models, each representation having been received from a different client wherein each representation is associated with a respective user and comprises a description of a respective predictive model;
selecting a model implementation from a plurality of model implementations for each of the obtained representations based on a status of the representation's respective user, the model implementation comprising one or more computer programs operable to execute on one or more computing devices; and
associating each of one or more of the model implementations with a node in a directed graph wherein for one or more ordered pairs of nodes in the graph the prediction output of a model implementation associated with a first node in the pair serves as input to a model implementation associated with a second node in the pair.
20. The storage medium of claim 19, further comprising executing each associated model implementation in an order prescribed by the graph.
21. The storage medium of claim 19 wherein a particular model representation is a Predictive Model Markup Language document.
22. The storage medium of claim 19 wherein a particular model representation is a textual representation.
23. The storage medium of claim 19 wherein a particular predictive model is a Naive Bayes classifier, a k-nearest neighbor classifier, a support vector machine, or a predictive model that uses a logistic regression technique.
24. The storage medium of claim 23 wherein at least two of the predictive models are different.
25. The storage medium of claim 19 wherein a particular model implementation is a map-reduce implementation.
26. The storage medium of claim 19 wherein a number of computing devices used by a particular model implementation is based at least in part on the status of the representation's respective user.
27. The storage medium of claim 19 wherein obtaining the plurality of representations further comprises performing pre-processing or post-processing operations in parallel for a particular representation in the plurality of representations.
Patent Citations (17)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US7349919(B2) | 2008-03-01 | Russell et al. | Applicant |
| US7565304(B2) | 2009-07-01 | Casati et al. | Examiner |
| US7590589(B2) | 2009-09-01 | Hoffberg | Examiner |
| US7606924(B2) | 2009-10-01 | Raz et al. | Examiner |
| US7668740(B1) | 2010-02-01 | Baggett et al. | Examiner |
| US7813870(B2) | 2010-10-01 | Downs et al. | Examiner |
| US7899611(B2) | 2011-03-01 | Downs et al. | Examiner |
| US7912628(B2) | 2011-03-01 | Chapman et al. | Examiner |
| US7930266(B2) | 2011-04-01 | Tuv et al. | Examiner |
| US7970721(B2) | 2011-06-01 | Leskovec et al. | Examiner |
| US7979365(B2) | 2011-07-01 | Goldberg et al. | Examiner |
| US8027854(B2) | 2011-09-01 | Baggett et al. | Examiner |
| US8065073(B2) | 2011-11-01 | Downs et al. | Examiner |
| US8090524(B2) | 2012-01-01 | Chapman et al. | Examiner |
| US2003/0212851(A1) | 2003-11-01 | Drescher et al. | Applicant |
| US2005/0234753(A1) | 2005-10-01 | Pinto et al. | Applicant |
| US2009/0106178(A1) | 2009-04-01 | Chu | Applicant |
Non-Patent Literature (43)
- Dag consistent parallel simulation: a predictable and robust conservative algorithm, Wentong Cai; Letertre, E.; Turner, S.J.; Parallel and Distributed Simulation, 1997. Proceedings. 11th Workshop on Digital Object Identifier: 10.1109/PADS.1997.594604 Publication Year: 1997 , pp. 178-181.Examiner
- Stochastic models for the Web graph, Kumar, R.; Raghavan, P.; Rajagopalan, S.; Sivakumar, D.; Tomkins, A.; Upfal, E.; Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on Digital Object Identifier: 10.1109/SFCS.2000.892065 Publication Year: 2000 , pp. 57-65.Examiner
- Explicit modeling of mode transition constraints for model predictive control, Kobayashi, K.; Hiraishi, K.; SICE Annual Conference, 2008 Digital Object Identifier: 10.1109/SICE.2008.4654911 Publication Year: 2008 , pp. 1569-1574.Examiner
- Research on prediction technique of network situation awareness, Juan Wang; Zhi-Guang Qin; Li Ye; Cybernetics and Intelligent Systems, 2008 IEEE Conference on Digital Object Identifier: 10.1109/ICCIS.2008.4670783 Publication Year: 2008 , pp. 570-574.Examiner
- U.S. Appl. No. 12/780,751, Mann et al., Predictive Analytic Modeling Platform, filed May 14, 2010.Applicant
- U.S. Appl. No. 12/782,689, Mann et al., Predictive Analytic Modeling Platform, filed May 18, 2010.Applicant
- U.S. Appl. No. 13/014,252, Breckenridge et al., Dynamic Predictive Modeling Platform, filed Jan. 26, 2011.Applicant
- U.S. Appl. No. 13/014,223, Breckenridge et al., Updateable Predictive Analytical Modeling, filed Jan. 26, 2011.Applicant
- U.S. Appl. No. 13/245,564, Breckenridge et al., Updateable Predictive Analytical Modeling, filed Sep. 26, 2011.Applicant
- U.S. Appl. No. 13/170,067, Breckenridge et al., Customized Predictive Analytical Model Training, filed Jun. 27, 2011.Applicant
- U.S. Appl. No. 13/171,423, Breckenridge et al., Predictive Analytical Model Training, filed Jun. 28, 2011.Applicant
- U.S. Appl. No. 13/172,714, Wei-Hao Lin et al., Predictive Analytical Model Matching, filed Jun. 29, 2011.Applicant
- U.S. Appl. No. 13/246,229, Wei-Hao Lin et al., Predictive Analytical Model Matching, filed Sep. 27, 2011.Applicant
- U.S. Appl. No. 13/101,040, Wei-Hao Lin et al., Predictive Analytical Modeling Accuracy Assessment, filed May 4, 2011.Applicant
- U.S. Appl. No. 13/246,541, Wei-Hao Lin et al., Predictive Analytical Modeling For Databases, filed Sep. 27, 2011.Applicant
- U.S. Appl. No. 13/246,410, Wei-Hao Lin et al., Predictive Analytical Model Selection, filed Sep. 27, 2011.Applicant
- U.S. Appl. No. 13/223,067, Lin et al., Training Data Expansion, filed Aug. 31, 2011.Applicant
- U.S. Appl. No. 13/101,048, Wei-Hao Lin et al., Predictive Analytical Modeling Data Selection, filed May 4, 2011.Applicant
- U.S. Appl. No. 13/248,474, Wei-Hao Lin et al., Score Normalization, filed Sep. 29, 2011.Applicant
- U.S. Appl. No. 13/250,394, Lin et al., Predictive Model Application Programming Interface, filed Sep. 30, 2011.Applicant
- U.S. Appl. No. 13/252,063, Wei-Hao Lin et al., Combining Predictive Models in Predictive Analytical Modeling, filed Oct. 3, 2011.Applicant
- U.S. Appl. No. 13/209,358, Wei-Hao Lin et al., Determining a Type of Predictive Model for Training Data, filed Aug. 12, 2011.Applicant
- U.S. Appl. No. 13/159,882, Wei-Hao Lin et al., Predictive Model Caching, filed Jun. 14, 2011.Applicant
- U.S. Appl. No. 13/246,596, Wei-Hao Lin et al. Hosting Predictive Models, filed Sep. 27, 2011.Applicant
- U.S. Appl. No. 13/195,349, Wei-Hao Lin et al., Improving Predictive Modeling Accuracy, filed Aug. 1, 2011.Applicant
- U.S. Appl. No. 13/179,204, Wei-Hao Lin et al., Generating Training Data for Predictive Models, filed Jul. 8, 2011.Applicant
- U.S. Appl. No. 13/198,900, Wei-Hao Lin et al., Anomaly Detection, filed Aug. 5, 2011.Applicant
- U.S. Appl. No. 13/272,178, Wei-Hao Lin et al., Confidence Scoring in Predictive Modeling, filed Oct. 12, 2011.Applicant
- U.S. Appl. No. 13/218,623, Wei-Hao Lin et al., Multi-Label Modeling, filed Aug. 26, 2011.Applicant
- U.S. Appl. No. 13/228,365, Lin et al., Suggesting Training Examples, filed Sep. 8, 2011.Applicant
- U.S. Appl. No. 13/245,688, Lin et al., Suggesting Training Examples, filed Sep. 26, 2011.Applicant
- U.S. Appl. No. 13/249,725, Wei-Hao Lin et al., Predictive Model Training on Large Datasets, filed Sep. 30, 2011.Applicant
- U.S. Appl. No. 13/224,245, Robert Kaplow et al., Predictive Model Evaluation and Training Based on Utility, filed Sep. 1, 2011.Applicant
- Duchi, John, et al., “Boosting with Structural Sparsity”, 2009, cs.berkeley.edu [online]. [Retrieved on Jan. 25, 2011]. Retrieved from the Internet: <URL: http://www.cs.berkeley.edu/˜jduchi/projects/DuchiSi09d.pdf>, 41 pages.Applicant
- Duchi, John, et al., “Boosting with Structural Sparsity”, Proceedings of the 26th International Conference on Machine Learning, Montreal, Canada, 2009, cs.berkeley.edu [online]. [Retrieved on Jan. 25, 2011]. Retrieved from the Internet: <URL: http://www.cs.berkeley.edu/˜jduchi/projects/DuchiSi0 9a.pdf>, 8 pages.Applicant
- R-Project web pages, 190 pages [online]. [Retrieved on May 18, 2010]. Retrieved from the Internet: <URL: http://www.r-project.org/>, 190 pages.Applicant
- Uclassify web pages, [online]. [Retrieved on May 18, 2010]. Retrieved from the Internet: <URL: http://www.uclassify.com>, 16 pages.Applicant
- Zementis web pages [online]. [Retrieved on May 18, 2010]. Retrieved from the Internet: <URL: http://www.zementis.com>, 34 pages.Applicant
- Weiss, Integrating Real-Time Predictive Analytics into SAP Applications [online], Dec. 30, 2009 [retrieved on Sep. 29, 2011], Retrieved from the Internet:,URL:http://www.sdn.sap.com/irj/scn/go/portal/prtroot/docs/library/uuid/a07faefd-61d7-2c10-bba6-89ac5ffc302c?QuickLink=index&overridelayout=true>, 1 page.Applicant
- Hutter, et al., “Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms,”, Principles and Practice of Constraint Programing, Lecture Notes in Computer Science, 2006, 15 pages.Applicant
- SAS Rapid Predictive Modeler, Overview, 2010, 4 pages.Applicant
- Postema, et al., “A Decision Support Tool for Tuning Parameters in a Machine Learning Algorithm”, Nanyang Techonological University, 1997, 9 pages.Applicant
- “Active learning (machine learning),” Wikipedia, the free encyclopedia, [online] [retrieved on Sep. 8, 2011]. Retrieved from the Internet: http://en.wikipedia.org/wiki/Active learning (machine learning), 3 pages.Applicant