# US 10,872,277 B1 · Distributed classification system > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,872,277 B1 - Document ID: US10872277B1 - Status: Granted - Kind: B1 - Application number: 16/935,586 - Filed: 2020-07-22 - Granted: 2020-12-22 - Earliest claimed: 2020-01-20 - Assignees: SAS Institute Inc. - Applicants: SAS Institute Inc. - Inventors: Yingjian Wang - Web page: https://patentgrep.com/patent/US10872277B1 ## 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/2415: based on parametric or probabilistic models, e.g. based on likelihood ratio or false acceptance rate versus a false rejection rate - G06F 18/2431: Multiple classes - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A computing system classifies distributed data. A first computation request is sent to worker computing devices. A first response is received from each worker computing device. Each first response includes a first matrix computed as a second order derivative of a logarithm of a predefined likelihood function on a subset of training data distributed to each respective worker computing device. A global first matrix is defined by concatenating the first matrix from each worker computing device. A kernel matrix is computed using the training data and a predefined kernel function. A second computation request is sent to the worker computing devices. The second computation request indicates that each worker computing device compute a classification probability for each observation vector distributed to a respective worker computing device using the defined global first matrix and the computed kernel matrix. The determined classification probability is output for each 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: send a first computation request to a plurality of worker computing devices; receive a first response to the first computation request from each worker computing device of the plurality of worker computing devices, wherein each first response includes a first matrix computed as a second order derivative of a logarithm of a predefined likelihood function on a subset of training data distributed to each respective worker computing device, wherein the training data includes a plurality of observation vectors, wherein each observation vector of the plurality of observation vectors includes a value for each variable of a plurality of variables; define a global first matrix by concatenating the first matrix from each worker computing device of the plurality of worker computing devices; compute a kernel matrix using an entirety of the training data and a predefined kernel function; send a second computation request to the plurality of worker computing devices, wherein the second computation request indicates that each worker computing device compute a classification probability for each observation vector of the plurality of observation vectors distributed to a respective worker computing device using the defined global first matrix and the computed kernel matrix; and output the determined classification probability for each observation vector of the plurality of classified observation vectors. ### Claim 2 (depends on 1) The non-transitory computer-readable medium of claim 1, wherein the predefined likelihood function is a sigmoid function. ### Claim 3 (depends on 2) The non-transitory computer-readable medium of claim 2, wherein the predefined likelihood function is 1 1 + e - x , where x is an observation vector of the plurality of observation vectors. ### Claim 4 (depends on 2) The non-transitory computer-readable medium of claim 2, wherein the predefined likelihood function is ∫ - ∞ x ⁢ 𝒩 ⁡ ( τ ❘ 0 , 1 ) ⁢ d ⁢ τ , where x is an observation vector of the plurality of observation vectors, N(τ|0,1) is a standard normal distribution, and the predefined likelihood function computes a probability that the observation vector x is less than or equal to a τth quantile of the standard normal distribution. ### Claim 5 (depends on 1) The non-transitory computer-readable medium of claim 1, wherein the first matrix is computed using Ww=−∇∇ log l(xi), i=1, 2, . . . , Now, where ∇∇ indicates the second order derivative of the logarithm of the predefined likelihood function, l(xi) is the predefined likelihood function value computed for an ith observation vector xi included in the subset of training data distributed to each respective worker computing device, and Now is a number of observation vectors included in the subset of training data distributed to each respective worker computing device. ### Claim 6 (depends on 1) The non-transitory computer-readable medium of claim 1, wherein the predefined kernel function is a Gaussian kernel function, and the kernel matrix is computed using K ⁡ ( x i , x j ) = exp ⁢ -  x i - x j  2 2 ⁢ s 2 ⁢ i = 1 , … ⁢ , N , j = 1 , … ⁢ ⁢ N , where xi is an ith observation vector of the training data, xj is a jth observation vector of the training data, N is a number of observation vectors included in the training data, and s is a Gaussian bandwidth parameter value. ### Claim 7 (depends on 1) The non-transitory computer-readable medium of claim 1, wherein computing the classification probability comprises: computing a decomposition matrix of the subset of training data distributed to each respective worker computing device based on the defined global first matrix and the computed kernel matrix; (A) receiving an observation vector; (B) computing a posterior latent function value for the received observation vector based on a first order derivative of the logarithm of the predefined likelihood function; (C) computing a first vector for the received observation vector based on the defined global first matrix and the computed decomposition matrix; and (D) computing a deviation value for the received observation vector based on the computed first vector, wherein the classification probability is computed based on the computed deviation value and the computed posterior latent function value for the received observation vector. ### Claim 8 (depends on 7) The non-transitory computer-readable medium of claim 7, wherein the observation vector is received by reading the observation vector from an input data subset stored at each worker computing device of the plurality of worker computing devices. ### Claim 9 (depends on 8) The non-transitory computer-readable medium of claim 8, wherein (A) through (D) are repeated with each remaining observation vector included in the input data subset stored at each worker computing device of the plurality of worker computing devices as the observation vector. ### Claim 10 (depends on 7) The non-transitory computer-readable medium of claim 7, wherein the decomposition matrix is computed using L=cholesky(I+Wg0.5KWg0.5), where L is the decomposition matrix, cholesky indicates a Cholesky decomposition, I is an N×N diagonal identity matrix, Wg is the defined global first matrix, K is the computed kernel matrix, and N is a number of observation vectors included in the training data. ### Claim 11 (depends on 10) The non-transitory computer-readable medium of claim 10, wherein the posterior latent function value is computed using ƒ=kT(xi)∇ log l(xi), where ƒ is the posterior latent function value, k(xi) is a vector having length N that is a projection of xi using a kernel bivariate function selected based on the predefined kernel function, xi is the received observation vector, T indicates a transpose, ∇ indicates the first order derivative of the logarithm of the predefined likelihood function, and l(xi) is the predefined likelihood function value computed for xi. ### Claim 12 (depends on 11) The non-transitory computer-readable medium of claim 11, wherein the first vector is computed using v=L\(Wg0.5k(xi)), where v is the first vector. ### Claim 13 The non-transitory computer-readable medium of 12, wherein the deviation value is computed using V=k(xi,xi)−vTv, where ∇ is the deviation value, and k(xi,xi) is an ith value of k(xi). ### Claim 14 (depends on 1) The non-transitory computer-readable medium of claim 1, wherein the determined classification probability is output by each worker computing device of the plurality of worker computing devices for each observation vector included in the subset of input data distributed to each respective worker computing device. ### Claim 15 (depends on 1) The non-transitory computer-readable medium of claim 1, wherein the classification probability is defined for each class of a plurality of classes. ### Claim 16 (depends on 15) The non-transitory computer-readable medium of claim 15, further comprising computer-readable instructions that cause the computing device to: determine the class of the plurality of classes for each observation vector of the plurality of observation vectors based on a maximum value of the determined classification probability for a respective observation vector and a respective class, and output the determined class for each observation vector of the plurality of observation vectors, wherein the determined class is defined to represent a label for the respective observation vector. ### Claim 17 (depends on 1) The non-transitory computer-readable medium of claim 1, wherein the predefined likelihood function is defined by training using the training data before sending the second computation request. ### Claim 18 (depends on 17) The non-transitory computer-readable medium of claim 17, wherein the training data is stored on each worker computing device of the plurality of worker computing devices, and wherein a unique subset of the training data is stored on each worker computing device of the plurality of worker computing devices, wherein in combination, the unique subset stored on each worker computing device of the plurality of worker computing devices includes all of the plurality of observation vectors. ### Claim 19 (depends on 18) The non-transitory computer-readable medium of claim 18, wherein training using the training data comprises: (A) computing a second matrix using the defined global first matrix and the computed kernel matrix; (B) sending a third computation request to the plurality of worker computing devices; (C) receiving a second response to the third computation request from each worker computing device of the plurality of worker computing devices, wherein each second response includes a first vector computed from a first order derivative of the logarithm of the predefined likelihood function on the subset of training data distributed to each respective worker computing device; (D) define a global first vector by concatenating the first vector from each worker computing device of the plurality of worker computing devices; (E) sending a fourth computation request to the plurality of worker computing devices; (F) receiving a third response to the fourth computation request from each worker computing device of the plurality of worker computing devices, wherein each second response includes a second vector computed from the defined global first vector; (G) define a global second vector by concatenating the second vector from each worker computing device of the plurality of worker computing devices; (H) sending a fifth computation request to the plurality of worker computing devices; (I) receiving a fourth response to the fifth computation request from each worker computing device of the plurality of worker computing devices, wherein each second response includes a latent function vector computed from the defined global second vector; and (J) define a global latent function vector by concatenating the latent function vector from each worker computing device of the plurality of worker computing devices. ### Claim 20 (depends on 19) The non-transitory computer-readable medium of claim 19, wherein the second matrix is computed using B=Wg0.5KWg0.5, where Wg is the defined global first matrix and K is the computed kernel matrix. ### Claim 21 (depends on 20) The non-transitory computer-readable medium of claim 20, wherein the first vector is computed using bw=Wgƒg+∇ log l(xi), i=1, 2, . . . , Now, where ƒg is the defined global latent function, V indicates the first order derivative of the logarithm of the predefined likelihood function, l(xi) is the predefined likelihood function value computed for xi, xi is an ith observation vector included in the subset of training data, and Now is a number of observation vectors included in the subset of training data. ### Claim 22 (depends on 21) The non-transitory computer-readable medium of claim 21, wherein the second vector is computed using a=bg−Wg0.5LT\(L\(Wg0.5KWg0.5)), where bg is the defined global first vector, and L is a decomposition matrix of the subset of training data distributed to each respective worker computing device based on the defined global first matrix and the computed kernel matrix, and T indicates a transpose. ### Claim 23 (depends on 22) The non-transitory computer-readable medium of claim 22, wherein the decomposition matrix is computed using L=cholesky(I+Wg0.5KWg0.5), where L is the decomposition matrix, cholesky indicates a Cholesky decomposition, I is an N×N diagonal identity matrix, Wg is the defined global first matrix, K is the computed kernel matrix, and N is a number of observation vectors included in the training data. ### Claim 24 (depends on 22) The non-transitory computer-readable medium of claim 22, wherein the latent function vector is computed using ƒ=Kag, where ƒ is the latent function vector, and ag is the defined global second vector. ### Claim 25 (depends on 24) The non-transitory computer-readable medium of claim 24, wherein training using the training data further comprises: (K) computing an objective function value; (L) comparing the computed objective function value to the objective function value computed on a prior iteration of (K); and repeating (A) through (L) until convergence is determined based on the comparison in (L). ### Claim 26 (depends on 25) The non-transitory computer-readable medium of claim 25, wherein the objective function value is computed using C=−0.5agTƒg+log l(xi), i=1, 2, . . . , N, where C is the objective function value. ### Claim 27 (depends on 26) The non-transitory computer-readable medium of claim 26, wherein a difference value ΔC is computed using ΔC=|C−Cp|, where Cp is the objective function value computed on the prior iteration of (K). ### Claim 28 (depends on 27) The non-transitory computer-readable medium of claim 27, wherein convergence is determined when ΔC