Abstract:
A method for estimating a real function that describes a phenomenon occurring in a space of any dimensionality. The function is estimated by taking a series of measurements of the phenomenon being described and using those measurements to construct an expansion that has a manageable number of terms. A reduction in the number of terms is achieved by using an approximation that is defined as an expansion on kernel functions, the kernel functions forming an inner product in Hilbert space. By finding the support vectors for the measurements one specifies the expansion functions. The number of terms in an estimation according to the present invention is generally much less than the number of observations of the real world phenomenon that is being estimated.

Description:
FIELD OF THE INVENTION 
     This invention relates to the fields of function approximation, regression estimation and signal processing. More particularly, the invention relates to practical methods and apparatus for carrying out the method for estimating functions of any dimensionality to thereby permit such apparatus to provide a superior performance. 
     BACKGROUND OF THE INVENTION 
     Function estimation is a branch of mathematics having many real world applications. For example, function estimation may be applied to a finite number of noisy measurements (or &#34;observations&#34;) for the purpose of approximating a function that describes the phenomenon being measured. Existing techniques of function estimation generally use the expansion: ##EQU1## where f(x) is the approximating function, φ i  (x) are a plurality of a priori chosen functions, α i  are scalars, and &#34;N&#34; is the number of terms in the expansion. Accordingly, to estimate a function using equation (1), one must estimate the scalars α i . The equation may be readily applied to one or two dimensional data, however its application to data of three or more dimensions is limited by the &#34;curse of dimensionality&#34;. 
     The curse of dimensionality is well known among mathematicians. It refers to the exponential increase in complexity of the estimating function that occurs as the dimensionality of the data being estimated increases. For example, if a one dimensional curve may be estimated with reasonable accuracy by using 20 terms (N=20), then the estimation of a two dimensional surface with reasonable accuracy requires 20 2  terms (N=20 2 ). A three dimensional surface requires 20 3  terms, and so on. Thus, as the dimension of the function to be estimated increases, the number of terms required rapidly reaches the point where even the most powerful computers can not handle the estimation in a timely manner. 
     SUMMARY OF THE INVENTION 
     The present invention provides a method for approximating functions of any dimensionality by an estimating function having a manageable number of terms. The reduction in the number of terms is achieved by using the expansion: ##EQU2## where K(x,x i ) is a positively defined kernel function having two vector variables that define an inner product in some Hilbert space. The a i  are scalars, and the x i  are subsets of the measured data called support vectors. The number of terms required when approximating a function with this expansion depends on the complexity of the function being estimated and on the required accuracy of the approximation, but not on the dimensionality of the function being estimated. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a flow chart depicting the steps taken in estimating a function according to the present invention. 
     FIG. 2 is a block diagram of a system for estimating real functions according to the present invention. 
     FIG. 3 is a graph that illustrate the cost generated by the cost function as a function of the estimation error. 
     FIG. 4 is a graph that illustrate the cost function insensitive to ε. 
    
    
     DETAILED DESCRIPTION 
     As stated above, function estimation is often applied with a number of measurements or observations are available, and the desire is to develop a function that describes the behavior of a system. To elaborate there are many applications where measurements improve the operation of a system. One very common example is found in today&#39;s modems. When a one modem is initially connected to another modem, the two modems exchange &#34;training signals&#34;. Those signals are used by the receiving modems to set gain and echo cancellation parameters so that the modems can exchange data at the highest bit rate that the communication path can sustain. The modem example illustrates a system that makes measurements, implicitly evaluates parameters, and adjusts itself. 
     A number of observations may be made about this conventional use of measurements. First, whatever is ascertained in consequence of evaluating the measurements need not be limited to use within the apparatus that performs the measurements and the evaluations. It can be a used by apparatus outside the apparatus that performs the calculations and develops the evaluations from received measurement. Second, whatever is ascertained in consequence of evaluating the measurements need not be limited to immediate use. It can be a future use of the evaluations, within the apparatus the performs the evaluations, or outside it. Third, the parameters that control a modem&#39;s operation and which are evaluated in the modem assumed to be static. Therefore, the control signals developed for control the operation of the modem after the training session are also static. They are evaluated once, and the modem&#39;s operation is set based on those static control signals. 
     This invention a) permits the information developed in response to measurements to be used within the apparatus the performs the calculations on the measurement, or outside it; b) permits the developed information to be used immediately, or stored for future use; c) permits the developed information to represent behavior that is functionally related to past behavior; and d) permits the developed information to be translated to software control signals or to electronic control signals, with the latter controlling other hardware, including a display monitor. 
     As already mentioned, the capabilities of this invention are achieved by developing a function estimate of the measured behavior. This function estimate permits decisions to be made about incoming information based on the function estimate, and to also augment, or improve, the estimate based on the incoming information. In the context of a modem, for example, this invention permits the control signals to be set based not so much on the state of the relevant transmission parameters at one moment of measurements (training session) but on an entire history of the communication path measurements. The decision may be to modify the control parameters of the circuitry that decides whether the information on an incoming signal is a &#34;1&#34; or a &#34;0,&#34; but it can also be intimately involved with the actual atomic decision process. 
     On a more macroscopic scale, this invention may be used in applications where users want assistance with everyday decisions. For example, unsolicited e-mail is a common e-mail problem (which some people believe will worsen with time). Employing the principles disclosed herein, a multi-dimensional function estimate can be developed based on information of past-received unsolicited e-mail, and that function estimate may be applied to a program that would evaluate an incoming e-mail message and decide whether it is of the unsolicited e-mail variety or not. It might flag the e-mail and, if the user selects a deletion option, might delete the e-mail outright. Such a multi-dimensional function might illustratively take into account the time the e-mail was sent, the length of the message, the salutation of the message, various key words in the message, etc. In such an application, 
     Another illustrative use may involves complex, feature-based, analyses. For example one way to analyze images is to extract agreed-upon features from the image, to classify the images, and to analyze the collection of features so that some statement can be made about the image. A very simple example of that of admission of personnel to a secure location based on a video camera image of the person seeking admission. Normally, each day the person looks a bit different, and the challenge is to correctly identify the person based on knowledge of the variations in that person&#39;s image; i.e., based on some function that estimates the variability in that person&#39;s image. Of course, in the course is employing the function estimate to admit (or not admit) the person to the secure location, the currently received image can be incorporated within the function estimation disclosed below to improve the function estimate. 
     Yet another illustration of function estimate use may be prediction, such as predicting the behavior of stock values, weather, and similar systems which, at least currently, are deemed to be stochastic. With the enhancements made available by this invention, many more dimensions can be handled to form a multi-dimensional function estimate that may estimate the weather (say, for the next 12 hours), or the movement of the stock marks (say, for the next day). In an arrangement, it is possible that some functional operations are performed in response to incoming information and the function estimate--such as having a computer execute &#34;buy&#34; or &#34;sell&#34; orders on the stock market, or automatically broadcast tornado warnings. However, but it is also possible that no functional operations are performed. Rather, it is possible for the developed multi-dimensional function to be displayed to a user, and allow the user to make decisions in response to what is displayed. 
     FIG. 1 is a flow chart depicting the steps taken in estimating a real function according to the present invention. The real function to be estimated will generally be descriptive of some physical phenomenon that occurs in an &#34;n&#34; dimensional space. Accordingly, the first step in estimating a real function is to take measurements of the phenomenon that is to be described by the estimated function (step 10). For purposes of illustration, the number of measurements is assigned the symbol &#34;1&#34;. Each of the 1 measurements is described by a vector &#34;x&#34; and a value &#34;y&#34;. The vector x i  describes the position within the n dimensional space at which the i th  measurement occurs, and therefore x i  is an n dimensional vector. The value y i  describes the value of the i th  measurement. Thus, the measured data is denoted as (x 1 ,y 1 ), (x 2 ,y 2 ) . . . (x i ,y i ). 
     Once the measurements have been acquired, the following functional is formed (step 12) and minimized (step 14). ##EQU3## (ω, ω) is the inner product of two vectors, γ is some constant, and f(x, ω) is a set of functions that can be described as follows ##EQU4## The ε referred to in equations (3) and (4) is an error tolerance which is chosen a priori. It describes the maximum amount that the estimated function may deviate from the actual function described by the measured data. This is an unusual approach to estimation. Conventionally, a function is estimated by forming a cost function for the difference between the estimated function and the estimating function, and that cost is sought to be minimized. The best is estimate is reached when the cost is zero. 
     This is illustrated by curve 21 of FIG. 3, where the described function shows the cost generated by the cost function as a function of the estimation error. A careful reading of the above would reveal to a skilled artisan that the cost function of equation (3) is more like the curve shown in FIG. 4. From FIG. 4 is can be easily observed that the cost function is insensitive to ε, in the sense that once ε is lower than a certain level (point 17) it does not matter whether ε is reduced further. When the function to be estimated is multi-dimensional, equation (3) effectively described a multi-dimensional tube centered about the function to be estimated. This is shown in FIG. 4 for a one-dimensional function where curve 19 is the curve to be estimated, and curves 13 and 15 are curves that estimate curve 19 within ε. Note the marked difference between curves 13 and 15. The fact that markedly different curves meet the same given cost criterion provides a great degree of flexibility, providing an advantage users of this invention over users of prior art methods. 
     The function that minimizes the functional described in (3) is: ##EQU5## where α i  *,α i  ≧0 with α i  α i  =0; and (Φ(x i ),Φ(x)) is the inner product of two elements of Hilbert space, where Φ(x) is defined as Φ(x)=(Φ 1  (x),Φ 2  (x) . . . Φ k  (x), . . . ). 
     Thus, in order to minimize the functional, coefficients α i  * and α i  of equation (3) must be determined (step 16). This is done by solving the following quadratic optimization problem: ##EQU6## subject to the constraints ##EQU7## 
     With respect to the solution of equation (6) it is important to note that only some of the coefficients α i  *-α i  differ from zero. Also, in equation (6) the vectors x i  are called Support Vectors (SV) and equation (6) is said to describe an expansion on SV. 
     In both equations (6) and (7), one can evaluate the inner products (Φ((x i ), Φ(x)) by using the general form of the inner product in Hilbert space. According to Hilbert space theory, to guarantee that a symmetric function K(u, v) has an expansion ##EQU8## with positive coefficients a k  &gt;0, i.e. to guarantee that K(u, v) is an inner product in some feature space Φ, it is necessary and sufficient that the conditions 
     
         ∫K(u,v)g(u)g(v)dudv&gt;0                                 (10) 
    
     be valid for any non-zero function g on the Hilbert space (Mercer theorem). Therefore, equation (6) can be replaced with ##EQU9## where the inner product (Φ(x i ), Φ(x)) is defined through a kernel K( i ,x). In which case, to find coefficients α i  * and α i  one has to maximize the function ##EQU10## subject to the constraints of equation (8). 
     Coefficients α i  * and α i  are scalars, and therefore equation (11) may be rewritten as ##EQU11## where K(x,x i ) is a positively defined kernel function having two vector variables that define an inner product in some Hilbert space. The a i  in equation (13) are scalars, and the x i  are subsets of the measured data called support vectors. The number of terms required when approximating a function with the expansion of equation (13) depends on the complexity of the function being estimated and on the required accuracy of the approximation, but not on the dimensionality of the function being estimated. 
     FIG. 2 is a block diagram of a system for estimating real functions according to the present invention. As mentioned above, the function being estimated will generally describe an &#34;n&#34; dimensional phenomenon of which &#34;1&#34; measurements have been taken. In the system of FIG. 2, these measurements are provided to a function estimator 20 through a data source 22. The estimator operates on the measured data to generate the estimating function. 
     The data source and function estimator may take many forms. For example, the data source may be the measuring instrument used to generate the measured data, or it may merely be a storage device, such as a disk drive, where measured data is stored. The function estimator may be computer, such as a personal computer, or it may be a single circuit board, such as an expansion board for a personal computer. 
     In any event, the function estimator includes an input device 24 that receives the measurements from the data source. An example of an input device is an RS-232 port (commonly available on many personal computers). The input device, in turn, relays the measurements to a processing unit 26, where the estimation process of forming a functional, minimizing the functional, and determining the coefficients of the minimizing function is implemented. 
     In a preferred embodiment, the processing unit includes a memory 28, one or more stored programs 30, and a processor 32. The memory is used to store measurement data received through the input device. It may be, for example, the Random Access Memory (RAM) of a computer. The stored programs are those programs necessary for implementing the estimation process. They may be stored in the Read Only Memory (ROM) of a computer. The processor, which may be the Central Processing Unit (CPU) of a computer, implements the estimation process according to instructions set forth in the stored programs. 
     In a preferred embodiment, the function estimator includes an output device 34. The output device is used to provide information to the user of the function estimator by, for example, providing a plot of the estimated function superimposed on a plot of the measured data. An example of an output device suitable for use with the invention is a computer display monitor. Use of a monitor as the output device is but one option for an output device. As discussed above, a monitor may be an ideal output device in situations where incoming information is not processed in any way other than as part of the function estimation, and that the results of the determinations--i.e., the function estimate--is sought to be provided to the user so that the user can make some decision(s), such as to issue weather warnings, issue &#34;buy&#34; or &#34;sell&#34; orders on the stock market, etc. Of course, if it is desired for decisions to be made by some processing equipment, output device 34 may be a message communication means, such as a programmed processor to perform computations leading to a decision, and communication apparatus such as a modem under control of the programmed processor. As indicated, above, the results obtained from the function estimation can be used also to directly control whatever function processing is needed to be performed on the incoming data. This is demonstrated in FIG. 2 by element 30, which is responsive to the data of element 22 and to the output of output device 34. 
     Several embodiments for the invention have been described in detail. However, it should be obvious that there are may further variations evident to persons skilled in the art. The invention is more particularly defined in the appended claims.