# US 10,482,353 B2 · Bandwidth selection in support vector data description for classification or outlier detection

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,482,353 B2
- Document ID: US10482353B2
- Status: Granted
- Kind: B2
- Application number: 16/055,336
- Filed: 2018-08-06
- Published: 2019-02-07
- Granted: 2019-11-19
- Earliest claimed: 2017-08-07
- Assignees: SAS Institute Inc.
- Applicants: SAS Institute Inc.
- Inventors: Yuwei Liao; Deovrat Vijay Kakde; Arin Chaudhuri; Hansi Jiang; Carol Wagih Sadek; Seung Hyun Kong
- Web page: https://patentgrep.com/patent/US10482353B2

## CPC

- G06N 20/10: using kernel methods, e.g. support vector machines [SVM]
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06F 18/22: Matching criteria, e.g. proximity measures
- G06F 18/2411: based on the proximity to a decision surface, e.g. support vector machines
- G06N 7/00: Computing arrangements based on specific mathematical models
- G06N 20/00: Machine learning
- G06V 30/19173: {Classification techniques}
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

A computing device determines a bandwidth parameter value for outlier detection or data classification. A mean pairwise distance value is computed between observation vectors. A tolerance value is computed based on a number of observation vectors. A scaling factor value is computed based on a number of observation vectors and the tolerance value. A Gaussian bandwidth parameter value is computed using the mean pairwise distance value and the scaling factor value. An optimal value of an objective function is computed that includes a Gaussian kernel function that uses the computed Gaussian bandwidth parameter value. The objective function defines a support vector data description model using the observation vectors to define a set of support vectors. The Gaussian bandwidth parameter value and the set of support vectors are output for determining if a new observation vector is an outlier or for classifying the new observation vector.

## Claims

### Claim 1

A non-transitory computer-readable medium having stored thereon computer-readable instructions that when executed by a computing device cause the computing device to:
(a) compute a mean pairwise distance value between a plurality of observation vectors, wherein each observation vector of the plurality of observation vectors includes a variable value for each variable of a plurality of variables;
(b) compute a tolerance value based on a number of the plurality of observation vectors;
(c) compute a scaling factor value based on the number of the plurality of observation vectors and the computed tolerance value;
(d) compute a Gaussian bandwidth parameter value by multiplying the computed mean pairwise distance value and the computed scaling factor value;
(e) train a support vector data description (SVDD) model using the plurality of observation vectors by computing an optimal value of an objective function that includes a Gaussian kernel function that uses the computed Gaussian bandwidth parameter value, wherein the objective function associated with the optimal value defines a set of support vectors selected from the plurality of observation vectors to define a boundary around the plurality of observation vectors; and
(f) output the computed Gaussian bandwidth parameter value and the trained SVDD model for determining if a new observation vector is an outlier or for classifying the new observation vector.

### Claim 2 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the mean pairwise distance value is computed using
D
_
2
=
2
⁢
N
(
N
-
1
)
⁢
∑
j
=
1
p
⁢
⁢
σ
j
2
,
where D is the mean pairwise distance value, N is the number of the plurality of observation vectors, p is a number of the plurality of variables, and σj2 is a variance of each variable of the plurality of variables.

### Claim 3 (depends on 2)

The non-transitory computer-readable medium of claim 2, wherein the variance for a first variable of the plurality of variables is computed using
σ
1
2
=
∑
i
=
1
N
⁢
⁢
(
x
i
⁢
⁢
1
-
μ
1
)
2
N
,
where xi1 is a value for the first variable of the ith observation vector of the plurality of observation vectors and
μ
1
=
∑
i
=
1
N
⁢
⁢
x
i
⁢
⁢
1
N
.

### Claim 4 (depends on 2)

The non-transitory computer-readable medium of claim 2, wherein the Gaussian bandwidth parameter value is computed using s=DF, where s is the Gaussian bandwidth parameter value and F is the scaling factor value.

### Claim 5 (depends on 4)

The non-transitory computer-readable medium of claim 4, wherein the scaling factor value is computed using F=1/√{square root over (ln[(N−1)/δ2])}, where δ is the computed tolerance value.

### Claim 6 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the scaling factor value is computed using F=1/√{square root over (ln[(N−1)/δ2])}, where F is the scaling factor value, N is the number of the plurality of observation vectors, and δ is the computed tolerance value.

### Claim 7 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the tolerance value is computed by iteratively solving δ=[ln(N−1)−2 ln(δ)]−1.5 for δ, where N is the number of the plurality of observation vectors, and δ is the computed tolerance value.

### Claim 8 (depends on 7)

The non-transitory computer-readable medium of claim 7, wherein the computer-readable instructions further cause the computing device to iteratively solve for δ by:
initializing a current tolerance value δ0;
initializing a counter n=0;
(g) computing a next tolerance value using δn+1=[ln(N−1)−2 ln(δn)]−1.5, where δn+1 is the next tolerance value and δn is the current tolerance value;
(h) computing an absolute value of a difference between the next tolerance value δn+1 and the current tolerance value δn;
incrementing the counter n to replace the current tolerance value δn with the next tolerance value δn+1 and repeating (g) and (h) until the computed absolute value satisfies a convergence test; and
when the computed absolute value satisfies the convergence test, defining the computed tolerance value as the next tolerance value δn+1.

### Claim 9 (depends on 8)

The non-transitory computer-readable medium of claim 8, wherein the computed absolute value satisfies the convergence test when the computed absolute value is less than or equal to a predefined convergence value.

### Claim 10 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the tolerance value is computed by fitting a polynomial function to δ that has a degree greater than one as a function of 1/ln(N−1), where N is the number of the plurality of observation vectors, and δ is the computed tolerance value.

### Claim 11 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the tolerance value is computed using a polynomial function δ=−0.14818008ϕ4+0.284623624ϕ3−0.252853808ϕ2+0.159059498ϕ−0.001381145, where ϕ=1/ln(N−1), where N is the number of the plurality of observation vectors, and δ is the computed tolerance value.

### Claim 12 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the scaling factor value is computed using F=W/√{square root over (Q×ln[2Q/(δ2M)])}, where F is the scaling factor value, W=Σi=1Nwi, M=Σi=1Nwi2, Q=(W2−M)/2, N is a number of distinct observation vectors included in the plurality of observation vectors, δ is the computed tolerance value, and wi is a repetition vector that indicates a number of times each observation vector of the distinct observation vectors is repeated.

### Claim 13 (depends on 12)

The non-transitory computer-readable medium of claim 12, wherein the mean pairwise distance value is computed using σ2=Σi=1pσi2, where σ is the mean pairwise distance value, p is a number of the plurality of variables, and σi2 is a weighted variance of each variable of the plurality of variables.

### Claim 14 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein the weighted variance for a first variable of the plurality of variables is computed using
σ
1
2
=
∑
i
=
1
N
⁢
⁢
w
i
⁡
(
x
i
⁢
⁢
1
-
μ
1
)
2
W
,
where xi1 is a value for the first variable of the ith observation vector of the distinct observation vectors and
μ
1
=
∑
i
=
1
N
⁢
⁢
w
i
⁢
x
i
⁢
⁢
1
W
.

### Claim 15 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein the Gaussian bandwidth parameter value is computed using s=σF, where s is the Gaussian bandwidth parameter value.

### Claim 16 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the objective function defined for the SVDD model is max(Σi=1NαiK(xi, xi)−Σi=1NΣj=1NαiαjK(xi,xj)), subject to Σi=1Nαi=1 and 0≤αi≤C, ∀i=1, . . . , N, where
K
⁡
(
x
i
,
x
j
)
=
exp
⁢
-

x
i
-
x
j

2
2
⁢
s
2
is the Gaussian kernel function, s is the Gaussian bandwidth parameter value, N is the number of the plurality of observation vectors, C=1/Nf, where f is an expected outlier fraction, xi and xj are the plurality of observation vectors, and αi and αj are Lagrange constants.

### Claim 17 (depends on 16)

The non-transitory computer-readable medium of claim 16, wherein the xi that have 0≤αi<C are the defined set of support vectors.

### Claim 18 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein, after (f), the computer-readable instructions further cause the computing device to:
receive the new observation vector;
compute a distance value using the trained SVDD model and the received new observation vector; and
when the computed distance value is greater than a computed threshold, identify the received new observation vector as an outlier.

### Claim 19 (depends on 18)

The non-transitory computer-readable medium of claim 18, wherein the defined set of support vectors are included in the trained SVDD model, wherein the threshold is computed using R2=1−2Σi=1NSVαiK(xi, xk)+Σi=1NSVΣj=1NSVαiαjK(xi, xj), where R2 is the computed threshold, xk is any support vector of the defined set of support vectors,
K
⁡
(
x
i
,
x
j
)
=
exp
⁢
-

x
i
-
x
j

2
2
⁢
s
2
is the Gaussian kernel function, s is the computed Gaussian bandwidth parameter value, NSV is a number of support vectors included in the defined set of support vectors, xi and xj are each support vectors of the defined set of support vectors, and αi and αj are Lagrange constants of an associated support vector of the defined set of support vectors.

### Claim 20 (depends on 19)

The non-transitory computer-readable medium of claim 19, wherein the Lagrange constant for each support vector included in the defined set of support vectors and the computed threshold are included in the trained SVDD model.

### Claim 21 (depends on 19)

The non-transitory computer-readable medium of claim 19, wherein the distance value is computed using dist2=1−2Σi=1NSVαiK(xi,z)+Σi=1NSVΣj=1NSVαiαjK(xi,xj), where dist is the computed distance value, and z is the received new observation vector.

### Claim 22 (depends on 18)

The non-transitory computer-readable medium of claim 18, wherein when the computed distance value is not greater than the computed threshold, the received new observation vector is not identified as an outlier.

### Claim 23 (depends on 18)

The non-transitory computer-readable medium of claim 18, wherein each variable of the plurality of variables describes a characteristic of a physical object, and identifying the new observation vector as an outlier indicates the physical object is performing in an anomalous manner.

### Claim 24 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein each observation vector of the plurality of observation vectors includes a class indicator variable, wherein (a) to (f) are performed on a subset of the plurality of observation vectors associated with a unique class indicator of the class indicator variable to train the SVDD model for the unique class indicator.

### Claim 25 (depends on 24)

The non-transitory computer-readable medium of claim 24, wherein (a) to (f) are performed for a plurality of unique class indicators of the class indicator variable to define a plurality of classes and to train the SVDD model for each class of the plurality of classes.

### Claim 26 (depends on 25)

The non-transitory computer-readable medium of claim 25, wherein, after (f) is performed for each class of the defined plurality of classes, the computer-readable instructions further cause the computing device to:
receive the new observation vector;
select a class from the defined plurality of classes;
(g) select the trained SVDD model for the unique class indicator associated with the selected class;
(h) compute a distance value using the selected, trained SVDD model and the received new observation vector;
(i) determine if the received new observation vector is within a radius of the selected, trained SVDD model using the computed distance value; and
(j) store an indicator of the determination and the computed distance value; and
repeat (g) to (j) with each remaining class of the defined plurality of classes as the selected class;
when the received new observation vector is determined to be in a single class of the defined plurality of classes based on the stored indicator, assign the received new observation vector to the single class; and
when the received new observation vector is determined to not be in a single class of the defined plurality of classes based on the stored indicator, assign the received new observation vector to a class using
arg
⁢
{
min
m
=
1
,
2
,
…
,
M
⁢
(
dist
m
⁡
(
z
)
/
R
m
)
}
,
where z is the received new observation vector, M is a number of the plurality of classes, distm(z) is the stored, computed distance value for class m, and Rm is the radius of the selected, trained SVDD model for class m.

### Claim 27 (depends on 26)

The non-transitory computer-readable medium of claim 26, wherein the distance value is computed using distm2(z)=1−2Σi=1NSVαimK(xi,z)+Σi=1NSVΣj=1NSVαimαjmK(xi,xj), where
K
⁡
(
x
i
,
x
j
)
=
exp
⁢
-

x
i
-
x
j

2
2
⁢
s
m
2
is the Gaussian kernel function, sm is the computed Gaussian bandwidth parameter value for class m, NSV is a number of support vectors included in the defined set of support vectors for class m, xi and xj are each support vectors of the defined set of support vectors for class m, and αi and αj are Lagrange constants of an associated support vector of the defined set of support vectors for class m.

### Claim 28

A computing device comprising:
a processor; and
a non-transitory computer-readable medium operably coupled to the processor, the computer-readable medium having computer-readable instructions stored thereon that, when executed by the processor, cause the computing device to
compute a mean pairwise distance value between a plurality of observation vectors, wherein each observation vector of the plurality of observation vectors includes a variable value for each variable of a plurality of variables;
compute a tolerance value based on a number of the plurality of observation vectors;
compute a scaling factor value based on the number of the plurality of observation vectors and the computed tolerance value;
compute a Gaussian bandwidth parameter by multiplying using the computed mean pairwise distance value and the computed scaling factor value;
train a support vector data description (SVDD) model using the plurality of observation vectors by computing an optimal value of an objective function that includes a Gaussian kernel function that uses the computed Gaussian bandwidth parameter value, wherein the objective function associated with the optimal value defines a set of support vectors selected from the plurality of observation vectors to define a boundary around the plurality of observation vectors; and
output the computed Gaussian bandwidth parameter value and the defined a set of support vectors for determining if a new observation vector is an outlier or for classifying the new observation vector.

### Claim 29

A method of determining a bandwidth parameter value for a support vector data description for outlier identification, the method comprising:
computing, by a computing device, a mean pairwise distance value between a plurality of observation vectors, wherein each observation vector of the plurality of observation vectors includes a variable value for each variable of a plurality of variables;
computing, by the computing device, a tolerance value based on a number of the plurality of observation vectors;
computing, by the computing device, a scaling factor value based on the number of the plurality of observation vectors and the computed tolerance value;
computing, by the computing device, a Gaussian bandwidth parameter value by multiplying the computed mean pairwise distance value and the computed scaling factor value;
training, by the computing device, a support vector data description (SVDD) model using the plurality of observation vectors by computing an optimal value of an objective function that includes a Gaussian kernel function that uses the computed Gaussian bandwidth parameter value, wherein the objective function associated with the optimal value defines a set of support vectors selected from the plurality of observation vectors to define a boundary around the plurality of observation vectors; and
outputting, by the computing device, the computed Gaussian bandwidth parameter value and the defined a set of support vectors for determining if a new observation vector is an outlier or for classifying the new observation vector.

### Claim 30 (depends on 29)

The method of claim 29, wherein the mean pairwise distance value is computed using
D
_
2
=
2
⁢
N
(
N
-
1
)
⁢
∑
j
=
1
p
⁢
⁢
σ
j
2
,
where D is the mean pairwise distance value, N is the number of the plurality of observation vectors, p is a number of the plurality of variables, and σj2 is a variance of each variable of the plurality of variables.