Patent ID: 12236358

DETAILED DESCRIPTION

FIG.1is an illustration of an exemplary environment100for determining a surrogate model. The environment100includes a surrogate model engine110that is adapted to generate a surrogate model145using two or more models105. The models105may be linear models105(also referred to as classifiers) and may have been trained using feature vectors109from a dataset102. Depending on the embodiment, each model105may have been trained using the same, or different, dataset102.

The dataset102may include a plurality of feature vectors109. Each feature vector109may be a set of values. The models105may be trained to receive as an input a feature vector109and to output a determined class or class value. Depending on the embodiment, each class may have a binary value (e.g., 0 or 1), or may have multiple possible values.

As shown, the surrogate model engine110includes several components or modules including, but not limited to, a model selector120, a neighborhood selector130, a model combiner140, and a heatmap generator150. More or fewer models may be supported. While shown as part of the surrogate model engine110, each component or module may be implemented on a same or different computing device as the surrogate model engine110. A suitable computing device is the computing device400illustrated with respect toFIG.4.

The model selector120may select a plurality of models105for consideration. The models105may be linear models105. The model selector120may select n models105(or interpretations) where all interpretations are concurrent for a same observation of interest107. The observation of interest107may selected from the dataset102. In particular, the model selector120may select n local linear models105where y1=ϕi(mi{right arrow over (x)}+bi) for 1≤i≤n, and where all n interpretations are for the same observation of interest107({right arrow over (x)}*, y*). In some embodiments, all of the models105may be the same model105.

The neighborhood selector130may select points (i.e., feature vectors109) from the dataset102that are close to the observation of interest107. In particular, the neighborhood selector may select points that are within a selected distance of the observation of interest107in the dataset102. Depending on the embodiment, the points may be randomly selected from the dataset102. Other methods for selecting the points may be used. The points or feature vectors109that are selected are referred to herein as the neighborhood of the observation of interest107.

In some embodiments, the neighborhood selector130may determine the distance of a point z to the observation of interest107using the function π{right arrow over (x)}*(z)=exp(−∫(D({right arrow over (x)}*, z))), where D({right arrow over (x)}*,z) is the distance of Z from {right arrow over (x)}*, and ∫ is a damping function based on the application. In one embodiment, the damping function may be: ∫(D({right arrow over (x)}*, z)=−D({right arrow over (x)}*, z)2/σ2for some user defined D and σ. Other damping functions may be used.

The neighborhood selector130may select points that are within a distance E of the observation of interest107for the neighborhood of the observation of interest107. The ϵ-faithful neighborhood {right arrow over (x)}*(of the observation of interest107) is defined as the set of all points z for which π{right arrow over (x)}*(z)≥ϵ where ϵ is chosen based on the application that the resulting surrogate model145may be used.

The model combiner140may use the feature vectors109corresponding to the points in the neighborhood to combine the models105into a surrogate model145. Depending on the embodiment, the surrogate model105may be one or more of a mean local surrogate model or a linearly weighted local surrogate model. How the model combiner140generates each type of surrogate model145is described below.

With respect to the mean local surrogate model, the model combiner140may use each of the models105to generate output classes y based on each of the feature vectors109in the neighborhood. The model combiner140may then use the output classes and feature vectors109to generate the local surrogate model145. The mean local surrogate model145may be represented by the following equation (1):

ym⁢e⁢a⁢n=ϕm⁢e⁢a⁢n(mq⁢x+bq)⁢where⁢mq=1n⁢∑i=1nmi,bq=1n⁢∑i=1nbi,and⁢ϕm⁢e⁢a⁢n(z)=Majorityi=1n⁢{ϕi(z)}(1)
(breaking ties arbitrarily). The observation of interest107({right arrow over (x)}*, y*) satisfies equation (1) for all models105that agree with the majority prediction.

With respect to the linearly weighted local surrogate model, the model combiner140may similarly generate the classes y. The model combiner140may then create the linear-weighted local surrogate model145based on the classes y, the feature vectors109, and the linear models105. For purposes of simplification, the process is described for combining only two models105. For a first model105, a hypothetical point (i.e., feature vector109) above the line m1{right arrow over (x)}+b1would be placed in a class 1, while a hypothetical point below the line would be placed in a class 0. For a second model105, a hypothetical point above the line m2{right arrow over (x)}+b2would be placed in a class 0, while a hypothetical point below the line would be placed in a class 1. The linear-weighted local surrogate model145may be represented by the following equation (2):

yw⁢e⁢i⁢g⁢h⁢t=ϕw⁢e⁢i⁢g⁢h⁢t(x→)={ϕi(m1⁢x→+b1)⁢with⁢probability⁢⁢p1(x→)ϕi(m2⁢x→+b2)⁢with⁢probability⁢1-p1(x→)(2)
where p1({right arrow over (x)}) is proportional to the inverse of the distance of point {right arrow over (x)} from the line m1{right arrow over (x)}+b1. To avoid a division by zero error, the model combiner may use a smoothing parameter τ>0.

Let d1({right arrow over (x)}) represent the perpendicular distance of {right arrow over (x)} from the line m1{right arrow over (x)}+b1, and let

wi(x→)=1di(x→)+τ.
Thus,

p1(x→)=w1(x→)Σj=12⁢wj(x→)
assuming there are who classes (i.e., class 1 and class 0).

The equation (2) may be extended to allow the model combiner140to combine more than two linear models105. Given n interpretations y1({right arrow over (x)})=ϕi(mi{right arrow over (x)}+bi) for 1≤i≤n, the weighted model ϕweight({right arrow over (x)}) reports the outcome of y1({right arrow over (x)}) with probability p1({right arrow over (x)}) is proportional to the inverse of the distance of point ({right arrow over (x)}) from the line mi{right arrow over (x)}+bi. In addition,

p1(x→)=wi(x→)Σj=1n⁢wj(x→),where⁢wi(x→)=1di(x→)+τ.

Based on the above, the linear-weighted local surrogate model145may be represented by the following equation (3):

yw⁢e⁢i⁢g⁢h⁢t=ϕw⁢e⁢i⁢g⁢h⁢t(x→)={ϕi(m1⁢x→+b1)with⁢probability⁢⁢p1(x→)⋮⋮ϕi(m2⁢x→+b2)with⁢probability⁢pn(x→)(3)

To compute the probability that the surrogate model145returns a class value C given a point {right arrow over (x)}, the probabilities of all models105that return the class value C given {right arrow over (x)} can be computed by the model combiner145as shown in equation (4):

Pr⁡(ϕw⁢e⁢i⁢g⁢h⁢t=c)=∑1≤i<ns.t.yi(x→)=cpi(x→)(4)

The heatmap generator150may generate a heatmap155that visualizes the output of a surrogate model145, and more specifically a linearly weighted local surrogate model145. A heatmap155is a way to visualize the classes output by the surrogate model145for each point (i.e., feature vectors109). The heatmap155may include a color for each class value with an intensity that is based on the probability that the particular class value is returned by the surrogate model145. The probability of a particular class value may be determined by the heatmap generator150using the equation (4) shown above.

For example, for a surrogate model145that outputs the class values of 1 or 0, the heatmap generator150may assign the color pink to the class 1 and the color blue to the class 0. If the surrogate model145for a point outputs the class value 1 with a probability of 0.2 and the class value 0 with a probability of 0.8, then the heatmap generator150may color the point on the heatmap155blue since it is most likely associated with the class value of 0. The heatmap generator150may color the point with a high intensity (e.g., dark blue) because the probability of the class value is high. Depending on the embodiment, the lowest intensity color used in the heatmap155may correspond to the probability of 0.5. Any method for generating a heatmap155may be used.

The surrogate models145described herein may be used for the following applications. Other applications may be supported. One example application is for the combination of interpretations from multiple different classifiers. There may be two classifiers C1and C2trained on the same dataset102and representing two classes: blue and red. As an example, the datasets could be made up of textual reviews such as movie reviews, and the reviews in the dataset may be labeled based on whether the review was positive or negative. The model combiner140may generate a surrogate model145ξ1({right arrow over (x)}) for C1and a surrogate model ξ2({right arrow over (x)}) for C2for the observation of interest107({right arrow over (x)}). The following inferences may be drawn about the combined surrogate models145:1. All of the red points in the associated heatmap155(independent of intensity) may represent the regions of the feature space that favor classification into the red class. Similarly, the blue points represent regions of the feature space that favor classification into the blue class.2. The darker the point (i.e., higher the intensity) on the heatmap155, the greater the likelihood that ξ1({right arrow over (x)}) and ξ2({right arrow over (x)}) agree on that point and the higher the confidence in the classification, and vice versa.3. For points with low intensity, the two interpreters provide conflicting class outputs. Assuming at least two interpretations, points that are equidistant from the two models may have the lowest intensity.

Another application for the surrogate models145is to identify key features in a dataset102that are responsible for the classification. For example, the high intensity regions of the heatmap155are evidence of agreement among the combined models145. The particular feature vectors109from these regions may be used to identify the key features used for classification. For example, if all of the models105agree that certain conversations between customers and agents be escalated, then these conversations likely include key features that are causing the classification.

Another use for the surrogate models145is for purposes of data generation or for fixing erroneous labels in datasets102. For applications that require data generation, the regions of the heatmap155with high interpreter agreement may produce ample data points for this task with sufficient classifier confidence. In the chatbot setting, surrogate models145may allow for the generation of transcripts that are likely to escalate, even if they have never been seen in any of the training/testing examples. This may help in further identifying features which may have been missed while designing the original models105.

The ability to generate new datapoints for a dataset102with sufficient confidence about their classification has possible applications in fixing erroneous training labels (if the error rate is not too high). For example, if the training dataset102contains an example for which the label is different than the output of the surrogate model145, this may indicate that here is a problem in the dataset102.

As another example, the surrogate models described herein can be used to identify areas or applications where linear models105tend to disagree or agree and therefore may not be suitable for prediction. For example, if the surrogate model145(through the heatmap155) shows that the linear models105tend to agree (i.e., high intensity colors on the heatmap155) on whether or not certain calls should be escalated to a customer service agent, then this may indicate that call escalation is an area that is well suited to automation and/or classification. On the other hand, if the surrogate model145shows that the linear models105do not agree (i.e., low-intensity colors on the heatmap155) on whether an online review is positive or negative, then this may indicate that review classification is an area that is not well-suited for automation.

Continuing the above example, the combined surrogate model145may further indicate whether the particular set of features that are being used for classification by each underlying linear model105is sufficient for classification purposes. For example, if the surrogate model145models show that the linear models105tend to agree when classifying call transcripts for escalation, then it may be assumed that the particular feature vectors being used for classification are adequately capturing the characteristics of the call transcripts that are important for classification. Conversely, if the surrogate model145models show that the linear models105tend to disagree when classifying reviews as positive or negative, then it may be assumed that the particular feature vectors being used for review classification are not adequately capturing the characteristics of the reviews that are important for classification.

In some embodiments, the model combiner145may generate surrogate models145using the various models105used by a call center for different classification purposes. For example, the model combiner140may generate a surrogate model145using the various models105used for call escalation purposes, may generate a surrogate model145using the various models105that are used to classify the tone or emails or other written communications, and may generate a surrogate model145using the various models105that are used review the performance of agents. If the model combiner140determines that the generated surrogate model145for a particular group of linear models105do not agree by more than a threshold amount, the model combiner140may alert an administrator that the use of the linear models105may be reconsidered or reevaluated.

FIG.2is an operational flow of an implementation of a method200for determining a surrogate model. The method200may be implemented by the surrogate model engine110.

At210, a plurality of models is received. The plurality of models105may be received and/or selected by the model selector210. Each model105may be a linear model105. The models105may be classifiers and may output a class value in response to an input such as a feature vector109. The models105may have been trained using feature vectors109from a dataset102.

At220, an observation of interest is received. The observation of interest107may be received by the neighborhood selector130. The observation of interest107may be a feature vector109and a class value output for the feature vector109by each model105of the plurality of models105. That is, each model105may be concurrent with respect to the observation of interest107.

At230, a distance is received. The distance may be received by the neighborhood selector130. The distance may be set by a user or administrator.

At240, a neighborhood of feature vectors is determined. The neighborhood of feature vectors109may be determined by the neighborhood selector130by selecting or sampling feature vectors109from the dataset102that are within the received distance of the feature vector109of the observation of interest107in the dataset102. Any method for determining the distance of feature vectors109in the dataset102may be used.

At250, a surrogate model for the plurality of models is determined. The surrogate model145may be determined by the model combiner140. The surrogate model145may be one or more of a mean local linear surrogate model or a linearly weighted local surrogate model. Other types of surrogate models145may be supported. In some embodiments, the model combiner140may determine the surrogate model145using each model105of the plurality of models105and the feature vectors109of the neighborhood of feature vectors109according to one or more of the equations (1) and (3) described above.

FIG.3is an operational flow of an implementation of a method300for determining a surrogate model. The method300may be implemented by the surrogate model engine110.

At310, feature vectors within a distance of an observation of interest are selected. The feature vectors109may be selected by the neighborhood selector130. Depending on the embodiment, the feature vectors109may be selected or sampled from the dataset102. The feature vectors109may be selected according to a damping function that is selected according to the application that will use the surrogate model145or the types of linear models105that are being combined. The selected feature vectors109are the neighborhood of feature vectors109.

At320, classes are generated using each feature vector109for each model. The classes or class values may be generated by the model combiner140. Depending on the embodiment, each model105may be used to output a class for each of the feature vectors109of the neighborhood of feature vectors109.

At330, the surrogate model is determined using the generated classes and feature vectors. The surrogate model145may be generated by the model combiner140. Depending on the embodiment, the model combiner140may use the classes output by each model105to determine the surrogate model145as described above depending on whether the surrogate model145is a local linear surrogate model or a linearly weighted local surrogate model.

At340, the surrogate model is provided. The surrogate model145may be provided by the model combiner140. Depending on the embodiment, the surrogate model145may be provided to the heatmap generator150for use in creating on one more heatmaps155.

FIG.4shows an exemplary computing environment in which example embodiments and aspects may be implemented. The computing device environment is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality.

Numerous other general purpose or special purpose computing devices environments or configurations may be used. Examples of well-known computing devices, environments, and/or configurations that may be suitable for use include, but are not limited to, personal computers, server computers, handheld or laptop devices, multiprocessor systems, microprocessor-based systems, network personal computers (PCs), minicomputers, mainframe computers, embedded systems, distributed computing environments that include any of the above systems or devices, and the like.

Computer-executable instructions, such as program modules, being executed by a computer may be used. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Distributed computing environments may be used where tasks are performed by remote processing devices that are linked through a communications network or other data transmission medium. In a distributed computing environment, program modules and other data may be located in both local and remote computer storage media including memory storage devices.

With reference toFIG.4, an exemplary system for implementing aspects described herein includes a computing device, such as computing device400. In its most basic configuration, computing device400typically includes at least one processing unit402and memory404. Depending on the exact configuration and type of computing device, memory404may be volatile (such as random access memory (RAM)), non-volatile (such as read-only memory (ROM), flash memory, etc.), or some combination of the two. This most basic configuration is illustrated inFIG.4by dashed line406.

Computing device400may have additional features/functionality. For example, computing device400may include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Such additional storage is illustrated inFIG.4by removable storage408and non-removable storage410.

Computing device400typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by the device400and includes both volatile and non-volatile media, removable and non-removable media.

Computer storage media include volatile and non-volatile, and removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Memory404, removable storage408, and non-removable storage410are all examples of computer storage media. Computer storage media include, but are not limited to, RAM, ROM, electrically erasable program read-only memory (EEPROM), flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computing device500. Any such computer storage media may be part of computing device400.

Computing device400may contain communication connection(s)412that allow the device to communicate with other devices. Computing device400may also have input device(s)414such as a keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s)416such as a display, speakers, printer, etc. may also be included. All these devices are well known in the art and need not be discussed at length here.

It should be understood that the various techniques described herein may be implemented in connection with hardware components or software components or, where appropriate, with a combination of both. Illustrative types of hardware components that can be used include Field-programmable Gate Arrays (FPGAs), Application-specific Integrated Circuits (ASICs), Application-specific Standard Products (ASSPs), System-on-a-chip systems (SOCs), Complex Programmable Logic Devices (CPLDs), etc. The methods and apparatus of the presently disclosed subject matter, or certain aspects or portions thereof, may take the form of program code (i.e., instructions) embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium where, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the presently disclosed subject matter.

Although exemplary implementations may refer to utilizing aspects of the presently disclosed subject matter in the context of one or more stand-alone computer systems, the subject matter is not so limited, but rather may be implemented in connection with any computing environment, such as a network or distributed computing environment. Still further, aspects of the presently disclosed subject matter may be implemented in or across a plurality of processing chips or devices, and storage may similarly be effected across a plurality of devices. Such devices might include personal computers, network servers, and handheld devices, for example.

Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.