Intelligent sampling for neural network data mining models

A method, system, and computer program product provides automated determination of the size of the sample that is to be used in training a neural network data mining model that is large enough to properly train the neural network data mining model, yet is no larger than is necessary. A method of performing training of a neural network data mining model comprises the steps of: a) providing a training dataset for training an untrained neural network data mining model, the first training dataset comprising a plurality of rows of data, b) selecting a row of data from the training dataset for performing training processing on the neural network data mining model, c) computing an estimate of a gradient or cost function of the neural network data mining model, d) determining whether the gradient or cost function of the neural network data mining model has converged, based on the computed estimate of the gradient or cost function of the neural network data mining model, e) repeating steps b)-d), if the gradient or cost function of the neural network data mining model has not converged, and f) updating weights of the neural network data mining model, if the gradient or cost function of the neural network data mining model has converged.

FIELD OF THE INVENTION

The present invention relates to automated determination of the size of the sample that is to be used in training a neural network data mining model.

BACKGROUND OF THE INVENTION

Data mining is a technique by which hidden patterns may be found in a group of data. True data mining doesn't just change the presentation of data, but actually discovers previously unknown relationships among the data. Data mining is typically implemented as software in or in association with database systems. Data mining includes several major steps. First, data mining models are generated by based on one or more data analysis algorithms. Initially, the models are “untrained”, but are “trained” by processing training data and generating information that defines the model. The generated information is then deployed for use in data mining, for example, by providing predictions of future behavior based on specific past behavior.

One type of modeling that is useful in building data mining models is neural network modeling. Generally, a neural network is a set of connected input/output units where each connection has a weight associated with it. During the learning phase, the network learns by adjusting the weights so as to be able to more accurately generate an output based on the input samples.

Traditionally, neural network models are trained using batch methods, in which large amounts of data are used to train the models. However, problems arise with these batch-training methods because the size of the data sample to be used for training must be specified. For large datasets, if all the rows of data in the dataset are used, the computation of necessary information, such as gradient and cost function information, becomes too computationally expensive. One solution to this problem is to sample the data in the dataset and only use the sample to train the model. However, this present a problem because the proper sample size must be chosen for best results. If the sample chosen is too large, the computation is still too expensive, while if the sample chosen is too small, the trained model is not adequately predictive of the dataset. Thus, the sample size must be chosen intelligently. Because each model or type of model requires different sample sizes, there is no fixed sample size that will work properly for all cases.

A need arises for an automated technique that determines the size of the sample that is to be used in training a neural network data mining model.

SUMMARY OF THE INVENTION

The present invention is a method, system, and computer program product that provides automated determination of the size of the sample that is to be used in training a neural network data mining model. The present invention provides a subsample of the training dataset that is large enough to properly train the neural network data mining model, yet is no larger than is necessary

In one embodiment, a method of performing training of a neural network data mining model comprises the steps of: a) providing a training dataset for training an untrained neural network data mining model, the first training dataset comprising a plurality of rows of data, b) selecting a row of data from the training dataset for performing training processing on the neural network data mining model, c) computing an estimate of a gradient or cost function of the neural network data mining model, d) determining whether the gradient or cost function of the neural network data mining model has converged, based on the computed estimate of the gradient or cost function of the neural network data mining model, e) repeating steps b)-d), if the gradient or cost function of the neural network data mining model has not converged, and f) updating weights of the neural network data mining model, if the gradient or cost function of the neural network data mining model has converged.

In one aspect of the present invention, the selecting step comprises the step of randomly selecting the row of data from the training dataset for performing training processing on the neural network data mining model.

In one aspect of the present invention, the method further comprises the step of storing a number of rows of data that were selected.

In one aspect of the present invention, the method further comprises the step of performing additional training processing to the neural network data mining model using the training dataset, wherein the additional training processing is performed using a number of rows of data equal to the stored number of rows that were selected.

In one aspect of the present invention, the method further comprises the step of performing additional training processing to the neural network data mining model by repeating steps b)-f) until a decrease in an error of the neural network data mining model is less than a predefined threshold.

In one embodiment, a method of performing training of a neural network data mining model comprises the steps of: a) providing a training dataset for training an untrained neural network data mining model, the first training dataset comprising a plurality of rows of data, b) selecting, in each of a plurality of threads, a row of data from the training dataset for performing training processing on the neural network data mining model, c) computing, in each of the plurality of threads, an estimate of a gradient or cost function of the neural network data mining model, d) consolidating the computed estimate of the gradient or cost function of the neural network data mining model from each thread to form a consolidated gradient or cost function, e) determining whether the consolidated gradient or cost function of the neural network data mining model has converged, based on the consolidated computed estimate of the gradient or cost function of the neural network data mining model, e) repeating steps b)-d), if the consolidated gradient or cost function of the neural network data mining model has not converged, and f) updating weights of the neural network data mining model, if the consolidated gradient or cost function of the neural network data mining model has converged.

In one aspect of the present invention, the selecting step comprises the step of randomly selecting, in each of the plurality of threads, the row of data from the training dataset for performing training processing on the neural network data mining model.

In one aspect of the present invention, the method further comprises the steps of consolidating a number of rows of data that were selected by each thread to from a consolidated gradient or cost function, and storing the consolidated number of rows.

In one aspect of the present invention, the method further comprises the steps of performing additional training processing to the neural network data mining model using the training dataset, wherein the additional training processing is performed using a number of rows of data equal to the stored consolidated number of rows.

In one aspect of the present invention, each thread processes an equal portion of the number of rows of data processed.

In one aspect of the present invention, the method further comprises the steps of performing additional training processing to the neural network data mining model by repeating steps b)-f) until a decrease in an error of the neural network data mining model is less than a predefined threshold.

DETAILED DESCRIPTION OF THE INVENTION

An exemplary data mining system100, in which the present invention may be implemented, is shown inFIG. 1. System100includes a database/data mining system102that is connected to a variety of sources of data. For example, system102may be connected to a plurality of internal or proprietary data sources, such as systems104A-104N. Systems104A-104N may be any type of data source, warehouse, or repository, including those that are not publicly accessible. Examples of such systems include inventory control systems, accounting systems, scheduling systems, etc. System102may also be connected to a plurality of proprietary data sources that are accessible in some way over the Internet108. Such systems include systems106A-106N, shown inFIG. 1. Systems106A-106N may be publicly accessible over the Internet108, they may be privately accessible using a secure connection technology, or they may be both publicly and privately accessible. System102may also be connected to other systems over the Internet108. For example, system110may be privately accessible to system102over the Internet108using a secure connection, while system112may be publicly accessible over the Internet108.

The common theme to the systems connected to system102is that the connected systems all are potential sources of data for system102. The data involved may be of any type, from any original source, and in any format. System102has the capability to utilize and all such data that is available to it.

An exemplary block diagram of a database/data mining system102, shown inFIG. 1, is shown inFIG. 3. Database/data mining system102is typically a programmed general-purpose computer system, such as a personal computer, workstation, server system, and minicomputer or mainframe computer. Database/data mining system102includes processor (CPU)302, input/output circuitry304, network adapter306, and memory308. CPU302executes program instructions in order to carry out the functions of the present invention. Typically, CPU302is a microprocessor, such as an INTEL PENTIUM® processor, but may also be a minicomputer or mainframe computer processor. Input/output circuitry304provides the capability to input data to, or output data from, database/data mining system102. For example, input/output circuitry may include input devices, such as keyboards, mice, touchpads, trackballs, scanners, etc., output devices, such as video adapters, monitors, printers, etc., and input/output devices, such as, modems, etc. Network adapter306interfaces database/data mining system102with network310. Network310may be any standard local area network (LAN) or wide area network (WAN), such as Ethernet, Token Ring, the Internet, or a private or proprietary LAN/WAN.

Memory308includes data206, database management processing routines312, data mining processing routines314, and operating system316. Data206includes data, typically arranged as a plurality of data tables, such as relational database tables, as well as indexes and other structures that facilitate access to the data. Database management processing routines312are software routines that provide database management functionality, such as database query processing. Data mining processing routines314are software routines that implement the data mining processing performed by the present invention. In particular, data mining processing routines314include software routines that perform the center based cluster analysis of the present invention. Preferably, this data mining processing is integrated with database management processing. For example, data mining processing may be initiated by receipt of a database query, either in standard SQL or in the form of extended SQL statements, or data mining processing may be initiated from a programming language, such as JAVA. Operating system320provides overall system functionality.

Although the example shown inFIG. 3illustrates a single processor system, the present invention contemplates implementation on a system or systems that provide multi-processor, multi-tasking, multi-process, and/or multi-thread computing. Multi-processor computing involves performing computing using more than one processor. Multi-tasking computing involves performing computing using more than one operating system task. A task is an operating system concept that refers to the combination of a program being executed and bookkeeping information used by the operating system. Whenever a program is executed, the operating system creates a new task for it. The task is like an envelope for the program in that it identifies the program with a task number and attaches other bookkeeping information to it. Many operating systems, including UNIX®, OS/2®, and WINDOWS®, are capable of running many tasks at the same time and are called multitasking operating systems. Multi-tasking is the ability of an operating system to execute more than one executable at the same time. Each executable is running in its own address space, meaning that the executables have no way to share any of their memory. This has advantages, because it is impossible for any program to damage the execution of any of the other programs running on the system. However, the programs have no way to exchange any information except through the operating system (or by reading files stored on the file system). Multi-process computing is similar to multi-tasking computing, as the terms task and process are often used interchangeably, although some operating systems make a distinction between the two.

In most operating systems, there is a one-to-one relationship between the task and the program, but some operating systems allow a program to be divided into multiple tasks. Such systems are called multithreading operating systems. A thread—sometimes called an execution context or a lightweight process—is a single sequential flow of control within a program. A thread itself is not a program; it cannot run on its own. Rather, it runs within a program. A thread is similar to a real process in that a thread and a running program are both a single sequential flow of control. However, a thread is considered lightweight because it runs within the context of a full-blown program and takes advantage of the resources allocated for that program and the program's environment. As a sequential flow of control, a thread must carve out some of its own resources within a running program. (It must have its own execution stack and program counter for example.) The code running within the thread works only within that context. A thread may also be referred as a lightweight process or as an execution context.

A thread is a semi-process, which has its own stack, and executes a given piece of code. Unlike a real process, the thread normally shares its memory with other threads (where as for processes we usually have a different memory area for each one of them). A Thread Group is a set of threads all executing inside the same process. They all share the same memory, and thus can access the same global variables, same heap memory, same set of file descriptors, etc. All these threads execute in parallel (i.e. using time slices, or if the system has several processors, then really in parallel).

The advantage of using a thread group instead of a normal serial program is that several operations may be carried out in parallel, and thus events can be handled immediately as they arrive (for example, if we have one thread handling a user interface, and another thread handling database queries, we can execute a heavy query requested by the user, and still respond to user input while the query is executed).

The advantage of using a thread group over using a process group is that context switching between threads is much faster then context switching between processes (context switching means that the system switches from running one thread or process, to running another thread or process). Also, communications between two threads is usually faster and easier to implement then communications between two processes. On the other hand, because threads in a group all use the same memory space, if one of them corrupts the contents of its memory, other threads might suffer as well. With processes, the operating system normally protects processes from one another, and thus if one corrupts its own memory space, other processes won't suffer. Another advantage of using processes is that they can run on different machines, while all the threads have to run on the same machine (at least normally).

An exemplary data flow diagram of a data mining process, including building and scoring of models and generation of predictions/recommendations, is shown inFIG. 4. The training/model building step402involves generating the models that are used to perform data mining recommendation and prediction. The inputs to training/model building step402include training parameters404, training data406, and untrained models408. Untrained models408include algorithms that process the training data406in order to actually build the models. In particular, untrained models408includes algorithms that are used to build data mining models that are based on neural networks. Training parameters404are parameters that are input to the data-mining model building algorithms to control how the algorithms build the models. Training data406is data that is input to the algorithms and which is used to actually build the models.

Training/model building step402invokes the data mining model building algorithms included in untrained models408, initializes the algorithms using the training parameters404, processes training data406using the algorithms to build the model, and generates trained model410. Trained model410includes information, such as functions, that implements the conditions and decisions that make up an operational model. In particular, neural network models implement a mapping between the input space and the output space. This mapping may be implemented, for example, by a combination of basis functions, which define the neural network topology, and transfer functions, which define the transfer of information between nodes in the network. Trained model410may also be evaluated and adjusted in order to improve the quality, i.e. prediction accuracy, of the model. Trained model410is then encoded in an appropriate format and deployed for use in making predictions or recommendations.

Scoring step412involves using the deployed trained model410to make predictions or recommendations based on new data that is received. Trained model410, prediction parameters414, and prediction data416are input to scoring step412. Trained models410include information defining the model that was generated by model building step402. Prediction parameters414are parameters that are input to the scoring step418to control the scoring of scoring data416against trained model410and are input to the selection and prediction/recommendation step420to control the selection of the scored data and the generation of predictions and recommendations

Scoring data416is processed according trained model410, as controlled by prediction parameters414, to generate one or more scores for each row of data in scoring data416. The scores for each row of data indicate how closely the row of data matches attributes of the model, how much confidence may be placed in the prediction, how likely each output prediction/recommendation to be true, and other statistical indicators. Scored data418is output from scoring step412and includes predictions or recommendations, along with corresponding probabilities for the scored data.

Scored model418is input to selection and prediction/recommendation generation step, which evaluates the probabilities associated with the predictions/recommendations and selects at least a portion of the predictions/recommendations. The selected predictions/recommendations are those having probabilities meeting the selection criteria. The selection criteria may be defined by desired results data and/or by predefined or default criteria included in selection/generation step420. In addition, the selection criteria may include a limit on the number of predictions/recommendations that are to be selected, or may indicate that the predictions/recommendations are to be sorted based on their associated probabilities. The selected predictions/recommendations are output422from step420for use in data mining.

An example of an artificial neural network of the type that may be used in a neural network data mining model is shown inFIG. 5. Neural networks, such as network500, are typically organized in layers. Layers are made up of a number of interconnected nodes, such as nodes502A and502B, each of which contains an activation function. Patterns are presented to the network via the input layer504, which communicates to one or more hidden layers506where the actual processing is done via a system of weighted connections508. The hidden layers then link to an output layer510where the answer is output.

Most artificial neural networks contain some form of learning rule, which modifies the weights of the connections according to the input patterns that are presented. In a sense, artificial neural networks learn by example as do their biological counterparts.

There are many different kinds of learning rules used by neural networks. A typical well-known learning rule is the delta rule. The delta rule is often utilized by the most common class of artificial neural networks, which are called backpropagational neural networks (BPNNs). Backpropagation refers to the backwards propagation of error in the neural network.

With the delta rule, as with other types of backpropagation, learning is a supervised process that occurs with each cycle or epoch. This backpropagation learning process is shown inFIG. 6. Each time the network is presented with a new input pattern602(a new cycle or epoch), the input is filtered through a weight function604, such as the function: I=f(ΣWi·Input), where Wiare the weights. The output606is generated by a combination of various nodes in the hidden layers608. Within each hidden layer node is an activation function that polarizes network activity and helps stabilize it. The weights are adjusted through a forward activation flow of outputs, and the backwards error propagation of weight adjustments using a backpropagation function, such as

Wnew=Wold-β⁢⁢∇E.W
More simply, when a neural network is initially presented with a pattern, it makes a random guess as to what it might be. It then sees how far its answer was from the actual one and makes an appropriate adjustment to its connection weights.

Backpropagation performs a gradient descent within the solution's vector space towards a global minimum along the steepest vector of the error surface. The global minimum is that theoretical solution with the lowest possible error. The error surface itself is a hyperparaboloid but is seldom smooth. Indeed, in most problems, the solution space is quite irregular with numerous ‘pits’ and ‘hills’, which may cause the network to settle down in a local minimum, which is not the best overall solution. When the error has reached the global minimum, or at least a local minimum of acceptable quality, the error function may be said to have converged. Alternatively to using just the error function, a cost function that takes into account the cost of the various nodal transitions, as well as the error, may be used.

An exemplary flow diagram of a subsampling process700, for use in a single threaded embodiment of the present invention, is shown inFIG. 7. Process700begins with step702, in which a training epoch is started. In step704, a randomly selected row of data in the training dataset is processed for training of a neural network model. In step706, an estimate of the gradient of an error or cost function of the neural network model being trained is computed. For example, error or cost functions, such as those described above, may be used. In step708, it is determined whether the gradient descent of the error or cost functions has converged. The determination of whether the gradient descent of the error or cost functions has converged is performed at regular intervals of N rows, where N≧1. Where N=1, the determination is performed for each row. Where N>1, the determination is performed less frequently, which improves processing performance of the system. If the gradient descent of the error or cost functions has not converged, then the process loops back to step704, and an additional row of data in the training dataset is processed. If the gradient descent of the error or cost functions has converged, then the process continues with step710, in which the weights of the neural network model are updated. In addition, the number of rows that were processed in order to achieve convergence is made available. The number of rows that were processed are a subset of the total number of rows in the training dataset, yet convergence of the neural network data mining model has been achieved. Thus, process700provides a subsample of the training dataset that is large enough to properly train the neural network data mining model, yet is no larger than is necessary.

In step712, it is determined, for each training epoch, whether the error of the neural network data mining model has decreased significantly from the previous training epoch. A significant decrease is typically defined as being greater than a predefined threshold; thus, a decrease that is not significant is a decrease that is less than the predefined threshold. If, in step714, it is determined that the decrease in the error of the neural network data mining model is significant, then the process continues with step714, in which at least one additional training epoch is performed. If, in step712, it is determined that the decrease in the error of the neural network data mining model is not significant, then the process continues with step716, in which the training of the neural network data mining model is complete.

In step714, additional training epochs are performed. Each additional training epoch uses the same dataset, but, since in step704, the rows of data actually processed are randomly selected, each epoch uses a different selection of rows of data. In one embodiment, the number of rows of data used in each successive training epoch is the number of rows that were processed in order to achieve convergence in the first training epoch. Processing of this number of rows will provide to each later epoch a subsample of the training dataset that is large enough to properly train the neural network data mining model, yet is no larger than is necessary. Alternatively, steps702-712may be repeated by later training epochs, in order to more precisely tailor the number of rows of data processed to the particular rows of data that are selected in the epoch. Repeating steps702-712will ensure that the neural network data mining model will properly converge, even if the data selected in later training epochs differs significantly from the data selected in the initial training epoch.

Process700may be implemented in a single-threaded computing environment, or may also be advantageously implemented in a multi-threaded environment. In a multi-threaded environment, process700begins with step702, in which a training epoch is started. In step704, each thread processes a randomly selected row of data in the training dataset for training of a neural network model. In step706, each thread computes an estimate of the gradient of an error or cost function of the neural network model being trained. For example, error or cost functions, such as those described above, may be used. In step708, the computed gradients from each thread are consolidated to form a single gradient, and it is determined whether the consolidated gradient descent of the error or cost functions has converged. The determination of whether the gradient descent of the error or cost functions has converged is performed at regular intervals of N rows, where N≧1. Where N=1, the determination is performed for each row. Where N>1, the determination is performed less frequently, which improves processing performance of the system. If the gradient descent of the error or cost functions has not converged, then the process loops back to step704, and each thread processes an additional row of data in the training dataset. If the gradient descent of the error or cost functions has converged, then the process continues with step710, in which the weights of the neural network model are updated. In addition, the number of rows that were processed by each thread in order to achieve convergence is consolidated and made available. The consolidated number of rows that were processed are a subset of the total number of rows in the training dataset, yet convergence of the neural network data mining model has been achieved. Thus, process700provides a subsample of the training dataset that is large enough to properly train the neural network data mining model, yet is no larger than is necessary.

In step712, it is determined, for each training epoch, whether the error of the neural network data mining model has decreased significantly from the previous training epoch. A significant decrease is typically defined as being greater than a predefined threshold; thus, a decrease that is not significant is a decrease that is less than the predefined threshold. If, in step714, it is determined that the decrease in the error of the neural network data mining model is significant, then the process continues with step714, in which at least one additional training epoch is performed. If, in step712, it is determined that the decrease in the error of the neural network data mining model is not significant, then the process continues with step716, in which the training of the neural network data mining model is complete.

In step714, additional training epochs are performed. Each additional training epoch uses the same dataset, but, since in step704, the rows of data actually processed are randomly selected, each epoch uses a different selection of rows of data. In one embodiment, the number of rows of data used in each successive training epoch is the consolidated number of rows that were processed by all threads in order to achieve convergence in the first training epoch. Processing of this number of rows will provide to each later epoch a subsample of the training dataset that is large enough to properly train the neural network data mining model, yet is no larger than is necessary. The consolidated number of rows is used as the total number of rows, and an equal portion of that total number of rows may be processed by each thread. Alternatively, steps702-712may be repeated by later training epochs, in order to more precisely tailor the number of rows of data processed to the particular rows of data that are selected in the epoch. Repeating steps702-712will ensure that the neural network data mining model will properly converge, even if the data selected in later training epochs differs significantly from the data selected in the initial training epoch.