Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Arguments
Regarding objections to claims 3 and 15 in the previous office action, Applicant’s amendments have overcome the objections, which are withdrawn.
Regarding the rejection of claims 6 and 18 under 35 U.S.C. 112, Applicant’s amendments have overcome the rejections, which are withdrawn.
Applicant further argues regarding the rejection of claims under 35 U.S.C. 102 or 35 U.S.C. 103.
Regarding claim 1:
Examiner has reconsidered the interpretation of “centroid” as used in the claims as a term of art, and has accordingly rejected claim 1 under new grounds. As claim 1 is unamended, this action is non-final.
Applicant’s arguments which rely upon the assertion that Ran does not teach “centroid” are therefore moot, as Liu, as described below, is relied upon in the rejection for the defining characteristics of centroids. Examiner finds that the prototypes of Ran are analogous to centroids and therefore the application of centroids, as described in Liu, to the teachings of prototypes in Ran would be obvious to a person having ordinary skill in the art. In the method of Ran, in particular,
“approximating subvectors with the closest prototypes” (Ran, Fig. 2 caption)
“In short, PECAN is mapping (quantizing) the original input features onto prototype patterns in compact codebooks, then multiplication between weights (F) and features (X) can be approximated by lookup table operation during inference” (Ran, section III, paragraph 2),
the patterns in input sub-vectors used to determine prototypes shows that the prototypes are analogous to a centroid that is “representing a cluster of sub-vectors with matched feature information.” Examiner further notes that present disclosure suggests that the PQ method (which is employed in Ran) can be used to produce centroids (specification, paragraph 0030, “Product quantization (PQ) is an effective vector quantization technique used for dataset compression. It compresses the dataset by clustering the vectors in the dataset first, and then learning the centroids to represent vectors in each cluster, which can reduce the cardinality of the dataset. The set of centroids is called a codebook”).
Regarding claim 2 and analogous claim 14:
The rejection of claim 2 in the previous office action referenced the PECAN-D embodiment of Ran. Although this reference only served as explicit evidence that the PECAN method used backpropagation, Ran does not make this explicit for the PECAN-A embodiment referenced in claim 1, upon which claim 2 depends. Examiner has therefore provided new grounds of rejection under 35 U.S.C. 103, as given below.
Regarding claim 3:
Applicant submits that Ran does not teach all of the further limitations of claim 3 because:
“PECAN-A's softmax attention scores are not probabilities indicating which centroid is closest. Rather, they are learned attention weights used to construct a weighted linear combination of all prototypes simultaneously. In PECAN-A, no centroid is ever identified as ‘closest’ and the mechanism is explicitly a soft blending operation over the entire codebook, not an approximation of nearest-neighbor selection.”
Examiner respectfully disagrees. The relevant claim language is:
wherein the loss function is determined based at least in part on respective probabilities for the respective centroids in the first plurality of codebooks, a probability for a centroid in a codebook indicating a probability that the centroid is closest to a sample input sub-vector associated with the codebook relative to other centroids in the codebook
The language does not require that a particular centroid be identified as closest. Rather, it requires that the model loss function is “based at least” on centroid probabilities, where the probability indicates “a probability that the centroid is closest to a sample input sub-vector.” As shown in Ran, Fig. 2, the model loss function depends at least in part on the outputs of the PECAN-A method (in the PECAN-A embodiment). The PECAN-A method computes a softmax weighting of prototypes to approximate the input features vectors; these weights meet the broadest reasonable interpretation of “indicating a probability that the centroid is closest to a sample input sub-vector.”
The argument is therefore found unpersuasive.
Regarding claim 4:
Applicant, against the rejection of claim 4, states that PECAN-A in Ran does not use a distance metric. Both PECAN variants employ a distance metric. Under the broadest reasonable interpretation of the term, “distance” could encompass any similarity measure, such as that given in the rejection.
The argument is therefore found unpersuasive.
Regarding claims 5–13 and 15–20:
Applicant’s arguments regarding these claims rely on arguments made for one or more of claims 1–4 above, and are therefore not rebutted separately.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1, 8, 12–13, and 19–20 rejected under 35 U.S.C. 103 over Ran et al., “PECAN: A Product-Quantized Content Addressable Memory Network,” April 2023, 2023 Design, Automation & Test in Europe Conference & Exhibition (hereafter Ran) in view of Liu et al., US Pre-Grant Publication No. 2022/0036184 (hereafter Liu).
Regarding claim 1 and analogous claims 13 and 20:
Ran teaches:
“A computer-implemented method, comprising”: Ran, Abstract, “A novel deep neural network (DNN) architecture [computer-implemented method] is proposed wherein the filtering and linear transform are realized solely with product quantization (PQ)”; Ran, section IV, paragraph2, “All experiments are run on a machine equipped with four NVIDIA Tesla V100 GPU with 24GB frame buffer, and all codes are implemented by PyTorch.”
“dividing a first input for a first layer of a neural network into a first plurality of input sub-vectors”: Ran, section III, paragraph 1, “It is natural to set each prototype in PQ to be a k2 x 1 subvector (viz. same size as a vectorized kernel), with p prototypes in each of the cin input channels according to the patterns of flattened matrices. With this setting, there are two main components in a trained PECAN that require memory storage in each layer, namely, i) pcin prototypes for ‘quantizing’ the input subvectors [dividing a first input for a first layer of a neural network into a first plurality of input sub-vectors]; ii) coutcinp inner product values between the (sub)rows in F and each prototype.”
“and the respective centroids in the first plurality of codebooks being determined along with a first weight matrix for the first layer through a training procedure of the neural network”: Ran, section III. A, paragraph 1, “For PECAN-A, we compute the approximated matrix ˜X by splitting its rows into D = cin groups, each with subvectors of dimension d = k2, and get the attention scores Ki(j) to formulate the combination of prototypes Cm(j). […] Since the dot product distance function with softmax is differentiable, mapping features to prototypes can be learned end-to-end. It is worth noting that all intermediate features are replaced with the combination of learned prototypes after training [the respective centroids in the first plurality of codebooks being determined along with a first weight matrix for the first layer through a training procedure of the neural network].”
“selecting, from a lookup table, respective target computation results of the respective target centroids with the first weight matrix, the lookup table comprising respective computation results of the respective centroids in the first plurality of codebooks with the first weight matrix”; Ran, section III. C, paragraph 1, “For the original convolution, the computation im2col complexity is O(cinHoutWoutk2cout). During inference, our method includes two stages, the first is to get the indices by computing the distance between the flattened features and prototypes, while the second is to retrieve the product between weights and prototypes computed in advance, i.e., a simple table lookup [selecting, from a lookup table, respective target computation results of the respective target centroids with the first weight matrix, the lookup table comprising respective computation results of the respective centroids in the first plurality of codebooks with the first weight matrix].”
“determining a first output corresponding to the first input for the first layer based on aggregation of the respective target computation results”: Ran, section III. C, paragraph 1, “For the original convolution, the computation im2col complexity is O(cinHoutWoutk2cout). During inference, our method includes two stages, the first is to get the indices by computing the distance between the flattened features and prototypes, while the second is to retrieve the product between weights and prototypes computed in advance, i.e., a simple table lookup”; Ran, “Algorithm 1 Inference Algorithm of PECAN,” “Input: Codebook C ∈ ℝcink2×p, 4-D learned kernel tensor K ∈ ℝcout×cin×k×k, unfolded features X ∈ ℝcink2×HoutWout. Output: The approximated convolution output ˜Y ∈ ℝcout×HoutWout [determining a first output corresponding to the first input for the first layer based on aggregation of the respective target computation results].”
Ran does not explicitly teach ““determining respective target centroids for the first plurality of input sub-vectors based on respective distances between the first plurality of input sub-vectors and respective centroids in a first plurality of codebooks for the first layer, a centroid representing a cluster of sub- vectors with matched feature information.”
Liu teaches “determining respective target centroids for the first plurality of input sub-vectors based on respective distances between the first plurality of input sub-vectors and respective centroids in a first plurality of codebooks for the first layer, a centroid representing a cluster of sub- vectors with matched feature information”: Liu, paragraph 0005, “In some implementations, the plurality of parameters includes a plurality of weights of at least one layer of the machine-learned model, the plurality of weights including a weight matrix of the at least one layer. In some implementations, the weight matrix includes a plurality of subvectors, each subvector of the plurality of subvectors [the first plurality of input sub-vectors ] including a block of contiguous scalars in a column of the weight matrix, and the plurality of codes are respective to the plurality of subvectors”; Liu, paragraph 0007, “In some implementations, determining the code book including the plurality of centroids includes learning the plurality of centroids simultaneously with the plurality of codes to optimize a reconstruction error between the plurality of parameters and an approximated plurality of parameters that is reconstructed from the encoded data. In some implementations, the reconstruction error is optimized by minimizing a covariance of the plurality of parameters. In some implementations, the closest centroid to the respective parameter is closest to the respective parameter in Euclidean distance [determining respective target centroids for the first plurality of input sub-vectors based on respective distances between the first plurality of input sub-vectors and respective centroids ]”; Liu, paragraph 063, “Additionally and/or alternatively, at 304, the method 300 can include determining a codebook including a plurality of centroids [in a first plurality of codebooks for the first layer]. The plurality of centroids can have a respective index of a plurality of indices indicative of an ordering of the codebook. For instance, the codebook can include an ordered set of centroids, where each centroid is denoted in the ordered set by the respective index. For instance, the centroid(s) can have values that are learned to quantize the parameters of the machine-learned model. The codebook ( e.g., the set of centroids) can be a smaller set than that of the model parameters [a centroid representing a cluster of sub- vectors with matched feature information].”
Liu and Ran are analogous arts as they are both related to model quantization and compression. It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to have combined the centroids of Liu with the teachings of Ran to arrive at the present invention, in order to aid in the compression of a model, as stated in Liu, paragraph 0020, “These models, especially overparameterized models, can be compressed to reduce computing resource requirements for deploying, storing, or otherwise using the models while providing accuracy that is near or equal to uncompressed models. Reduced-size models having sufficient accuracy can be useful in providing applications that rely on mobile and/or low-power computational platforms for large-scale deployment.”
Regarding claim 8 and analogous claim 19:
Ran as modified by Liu teaches “The method of claim 1.”
Ran further teaches “wherein the lookup table is a quantized lookup table comprising respective quantized computation results of the respective centroids in the first plurality of codebooks with the first weight matrix”: Ran, section III, paragraph 2, “In short, PECAN is mapping (quantizing) the original input features onto prototype patterns in compact codebooks, then multiplication between weights (F) and features (X) can be approximated by lookup table operation during inference [wherein the lookup table is a quantized lookup table comprising respective quantized computation results of the respective centroids in the first plurality of codebooks with the first weight matrix].”
Regarding claim 12:
Ran as modified by Liu teaches “The method of claim 1.”
Ran further teaches “wherein a second plurality of codebooks are determined for a second layer of the neural network, respective centroids in the second plurality of codebooks being determined along with a second weight matrix for the second layer through the training procedure of the neural network”: Ran, Fig. 3 caption, “Fig. 3. The flattened features and codebooks for five different layers in VGG-Small [including a second layer of the neural network], (a)-(e) for conv1-conv5. For each subfigure, the upper image is the input feature after im2col operation, the second image shows the approximation matrix [a second weight matrix ] after substitution with PECAN-D which is composed of the corresponding codebook shown in the third row [respective centroids in the second plurality of codebooks].”
Claims 2–7, 9, and 14–18 rejected under 35 U.S.C. 103 over Ran as modified by Liu in view of Ichino et al., US Pre-Grant Publication No. 2023/0360440 (hereafter Ichino).
Regarding claim 2 and analogous claim 14:
Ran as modified by Liu teaches “The method of claim 1.”
Ran further teaches (bold only) “wherein the respective centroids in the first plurality of codebooks are updated by decreasing a loss function for training the neural network during a backpropagation of the training procedure”: Ran, section IV, paragraph 2, “To implement the PECAN framework for the CIFAR-10 and CIFAR-100 tasks, we use the co-optimization strategy that update the prototypes and weights together. We set the training epochs for PECAN-A and PECAN-D as 150 and 300, respectively. The learning rate for PECAN-A is set to 0.01 initially, decaying every 50 epoch, while that of PECAN-D is initialized as 0.001, decaying at epoch 200. For both datasets, we employ softmax function and set the temperature τ at 1 and 0.5 for PECAN-A and PECAN-D, respectively. We set the batch size to 64, and use cross-entropy as the loss function [the respective centroids in the first plurality of codebooks are updated by decreasing a loss function for training the neural network ], which is optimized by Adam.”
Ran as modified by Liu does not explicitly teach (bold only) “wherein the respective centroids in the first plurality of codebooks are updated by decreasing a loss function for training the neural network during a backpropagation of the training procedure.”
Ichino teaches (bold only) “wherein the respective centroids in the first plurality of codebooks are updated by decreasing a loss function for training the neural network during a backpropagation of the training procedure”: Ichino, paragraph 0128, “After the process of FIG. 5 is completed, the learning control unit 208 calculates a gradient of a parameter of the neural network of the feature conversion unit 105 using an error backpropagation method (backpropagation) [a backpropagation of the training procedure] (step S243).”
Ichino and Ran are analogous arts as they are both related to neural network training using softmax. It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to have combined the backpropagation softmax temperature training of Ichino with the teachings of Ran to arrive at the present invention, in order to improve training, as stated in Ichino, paragraph 0184, “Thereby, the authentication device 100 is expected to perform authentication with relatively high accuracy using a feature in which a part having many features for personal identification is emphasized.”
Regarding claim 3 and analogous claim 15:
Ran as modified by Liu and Ichino teaches “The method of claim 2.”
Ran further teaches:
“wherein a sample input for the first layer corresponding to a training sample is divided into a first plurality of sample input sub-vectors, a sample input sub-vector for the first layer is associated with one of the first plurality of codebooks”: Ran, section III, paragraph 2, “In short, PECAN is mapping (quantizing) the original input features onto prototype patterns in compact codebooks, then multiplication between weights (F) and features (X) can be approximated by lookup table operation during inference”; Ran, Fig. 2 caption, “When approximating subvectors with the closest prototypes [a sample input sub-vector for the first layer is associated with one of the first plurality of codebooks], PECAN-A and PECAN-D adopt different assignment schemes”; Ran, section III, paragraph 1, “It is natural to set each prototype in PQ to be a k2 x 1 subvector (viz. same size as a vectorized kernel), with p prototypes in each of the cin input channels according to the patterns of flattened matrices. With this setting, there are two main components in a trained PECAN that require memory storage in each layer, namely, i) pcin prototypes for ‘quantizing’ the input subvectors [a sample input for the first layer corresponding to a training sample is divided into a first plurality of sample input sub-vectors]; ii) coutcinp inner product values between the (sub)rows in F and each prototype.”
“and wherein the loss function is determined based at least in part on respective probabilities for the respective centroids in the first plurality of codebooks, a probability for a centroid in a codebook indicating a probability that the centroid is closest to a sample input sub-vector associated with the codebook relative to other centroids in the codebook” (underlined text as interpreted by Examiner; see claim objections, above): Ran, section III. A, paragraph 1, “For PECAN-A, we compute the approximated matrix ˜X by splitting its rows into D = cin groups, each with subvectors of dimension d = k2, and get the attention scores Ki(j) to formulate the combination of prototypes Cm(j):
PNG
media_image1.png
35
448
media_image1.png
Greyscale
where i = 1, 2, . . . ,HoutWout. Since the dot product distance function with softmax is differentiable, mapping features to prototypes can be learned end-to-end [softmax transforms results to probabilities that a particular result is most correct, used here as part of the training, hence, the loss function is determined based at least in part on respective probabilities for the respective centroids in the first plurality of codebooks, a probability for a centroid in a codebook indicating a probability that the centroid is closest to a sample input sub-vector associated with the codebook relative to other centroids in the codebook]. It is worth noting that all intermediate features are replaced with the combination of learned prototypes after training.”
Regarding claim 4 and analogous claim 16:
Ran as modified by Liu and Ichino teaches “The method of claim 3.”
Ran further teaches (bold only) “wherein the probability for the centroid in the codebook is determined through a differentiable function, the differentiable function being determined based at least in part on a distance between the centroid and the sample input sub-vector, and wherein the respective centroids in the first plurality of codebooks are updated through a backpropagation based on gradient information generated via the differentiable function”: Ran, section III. A, paragraph 1, “For PECAN-A, we compute the approximated matrix ˜X by splitting its rows into D = cin groups, each with subvectors of dimension d = k2, and get the attention scores Ki(j) to formulate the combination of prototypes Cm(j):
PNG
media_image1.png
35
448
media_image1.png
Greyscale
where i = 1, 2, . . . ,HoutWout. Since the dot product distance function [the differentiable function being determined based at least in part on a distance between the centroid and the sample input sub-vector] with softmax is differentiable [the probability for the centroid in the codebook is determined through a differentiable function], mapping features to prototypes can be learned end-to-end [the respective centroids in the first plurality of codebooks are updated … via the differentiable function]. It is worth noting that all intermediate features are replaced with the combination of learned prototypes after training.”
Ichino further teaches (bold only) “wherein the respective centroids in the first plurality of codebooks are updated through a backpropagation based on gradient information generated via the differentiable function”: Ichino, paragraph 0128, “After the process of FIG. 5 is completed, the learning
control unit 208 calculates a gradient of a parameter of the neural network of the feature conversion unit 105 using an error backpropagation method (backpropagation) [through a backpropagation based on gradient information generated] (step S243).”
Ichino and Ran are combinable for the rationale given under claim 2.
Regarding claim 5 and analogous claim 17:
Ran as modified by Liu and Ichino teaches “The method of claim 4.”
Ran further teaches (bold only) “wherein the differentiable function is determined further based on a learning coefficient for the first layer, the learning coefficient is configured to control a distribution of probabilities for centroids in a codebook, and is determined along with the respective centroids in the first plurality of codebooks through the training procedure of the neural network”: Ran, section III. B, paragraph 1, “To enable optimization for prototypes with the non-differentiable function argmax, we approximate it with a differentiable softmax function:
PNG
media_image2.png
60
408
media_image2.png
Greyscale
where τ is the temperature to relax the softmax function [the learning coefficient is configured to control a distribution of probabilities for centroids in a codebook]”; Ran, section IV, paragraph 2, “To implement the PECAN framework for the CIFAR-10 and CIFAR-100 tasks, we use the co-optimization
strategy that update the prototypes and weights together. We set the training epochs for PECAN-A and PECAN-D as 150 and 300, respectively. The learning rate for PECAN-A is set to 0.01 initially, decaying every 50 epoch, while that of PECAN-D is initialized as 0.001, decaying at epoch 200. For both datasets, we employ softmax function and set the temperature τ at 1 and 0.5 for PECAN-A and PECAN-D,
respectively [and is determined along with the respective centroids in the first plurality of codebooks].”
Ichino further teaches (bold only) “wherein the differentiable function is determined further based on a learning coefficient for the first layer, the learning coefficient is configured to control a distribution of probabilities for centroids in a codebook, and is determined along with the respective centroids in the first plurality of codebooks through the training procedure of the neural network”: Ichino, paragraph 0182, “For example, the attention processing unit 304 may be configured to multiply the attention map input from training data by a temperature coefficient S and input a multiplication result to the Softmax function and the multiplication unit 313 may be configured to multiply a result of the convolution calculation unit 311 by an obtained function value. In this case, the temperature coefficient S may be a parameter adjusted through learning [through the training procedure of the neural network].”
Ichino and Ran are combinable for the rationale given under claim 2.
Regarding claim 6 and analogous claim 18:
Ran as modified by Liu and Ichino teaches “The method of claim -4.”
Ran further teaches “wherein the differentiable function is a softmax function”: Ran, section III. A, paragraph 1, “For PECAN-A, we compute the approximated matrix ˜X by splitting its rows into D = cin groups, each with subvectors of dimension d = k2, and get the attention scores Ki(j) to formulate the combination of prototypes Cm(j):
PNG
media_image1.png
35
448
media_image1.png
Greyscale
where i = 1, 2, . . . ,HoutWout. Since the dot product distance function with softmax is differentiable [wherein the differentiable function is a softmax function], mapping features to prototypes can be learned end-to-end. It is worth noting that all intermediate features are replaced with the combination of learned prototypes after training.”
Regarding claim 7:
Ran as modified by Liu and Ichino “The method of claim 3.”
Ran further teaches “wherein the respective centroids in the first plurality of codebooks are initialized in the training procedure by clustering a set of sample inputs for the first layer corresponding to a set of training samples in a training dataset for the neural network”: Ran, section III, paragraph 1, “The convolution operation in a CNN is conceptually illustrated as a window sliding across the cin-channel input feature (cf. Fig. 1(a)) [clustering a set of sample inputs for the first layer corresponding to a set of training samples in a training dataset for the neural network, interpreted as including operations that divide training data into groups]. Actual implementations often unfold the convolution into a matrix-matrix product (cf. Fig. 1(b)). Specifically, the im2col command stretches the input entries covered in each filter stride into a column and concatenates the columns into a matrix X, whereas the kernel tensors are reshaped into a filter matrix F, such that PQ can be used to approximate FX. For an intermediate CNN layer, consider the flattened feature matrix X ∈ ℝcink2×HoutWout, where cin and k are the number of input channels and the kernel size, Hout and Wout are height and width of the output feature, codebooks C ∈ ℝcink2 x p are assigned with parameters to construct an embedding table for the features [initialized in the training procedure], where p is the number of choices for each codebook C(j), j = 1, 2, …, D. C(j)m ∈ ℝd are called prototypes, m = 1, 2, . . . , p (cf. Fig. 1(c))”; Ran, section III, paragraph 2, “In short, PECAN is mapping (quantizing) the original input features onto prototype patterns in compact codebooks, then multiplication between weights (F) and features (X) can be approximated by lookup table operation during inference.”
Regarding claim 9:
Ran as modified by Liu teaches “The method of claim 1.”
Ran further teaches:
(bold only) “wherein an intermediate lookup table is used during a backpropagation of the training procedure, the intermediate lookup table comprising respective intermediate real-value computation results of respective intermediate centroids in the first plurality of codebooks with an intermediate weight matrix for the first layer”: Ran, section III, paragraph 1, “For an intermediate CNN layer, consider the flattened feature matrix X ∈ ℝcink2×HoutWout, where cin and k are the number of input channels and the kernel size, Hout and Wout are height and width of the output feature, codebooks C ∈ ℝcink2 x p are assigned with parameters to construct an embedding table for the features, where p is the number of choices for each codebook C(j), j = 1, 2, …, D. C(j)m ∈ ℝd are called prototypes, m = 1, 2, . . . , p (cf. Fig. 1(c))”; Ran, section III, paragraph 2, “In short, PECAN is mapping (quantizing) the original input features onto prototype patterns in compact codebooks, then multiplication between weights (F) and features (X) can be approximated by lookup table operation during inference “; Ran, section III. A., “For PECAN-A, we compute the approximated matrix ˜X by splitting its rows into D = cin groups, each with subvectors of dimension d = k2, and get the attention scores K(j)i to formulate the combination of prototypes C(j) m :
PNG
media_image3.png
34
450
media_image3.png
Greyscale
where i = 1, 2, . . . ,HoutWout [where C is the set of codebooks used for lookups of computations between weights and features, hence, an intermediate lookup table … comprising respective intermediate real-value computation results of respective intermediate centroids in the first plurality of codebooks with an intermediate weight matrix for the first layer, intermediate interpreted applying to values used and/or updated during an ongoing process]. Since the dot product distance function with softmax is differentiable, mapping features to prototypes can be learned end-to-end. It is worth noting that all intermediate features are replaced with the combination of learned prototypes after training.”
“and wherein an intermediate quantized lookup table is used during a forward propagation of the training procedure, the intermediate quantized lookup table comprising respective intermediate quantized computation results of the respective intermediate centroids in the first plurality of codebooks with the intermediate weight matrix for the first layer”: Ran, section III, paragraph 2, “In short, PECAN is mapping (quantizing) the original input features onto prototype patterns in compact codebooks, then multiplication between weights (F) and features (X) can be approximated by lookup table operation during inference [hence the prototypes are a quantized lookup table accessible during forward propagation]”; Ran, section III. A., “For PECAN-A, we compute the approximated matrix ˜X by splitting its rows into D = cin groups, each with subvectors of dimension d = k2, and get the attention scores K(j)i to formulate the combination of prototypes C(j) m :
PNG
media_image3.png
34
450
media_image3.png
Greyscale
where i = 1, 2, . . . ,HoutWout [where C is the set of codebooks used for lookups of computations between weights and features, containing quantized prototypes, hence, an intermediate lookup table … intermediate quantized lookup table comprising respective intermediate quantized computation results of the respective intermediate centroids in the first plurality of codebooks with the intermediate weight matrix for the first layer, intermediate interpreted applying to values used and/or updated during an ongoing process]. Since the dot product distance function with softmax is differentiable, mapping features to prototypes can be learned end-to-end. It is worth noting that all intermediate features are replaced with the combination of learned prototypes after training.”
Ran as modified by Liu does not explicitly teach (bold only) “wherein an intermediate lookup table is used during a backpropagation of the training procedure.”
Ichino teaches (bold only) “wherein an intermediate lookup table is used during a backpropagation of the training procedure”: Ichino, paragraph 0128, “After the process of FIG. 5 is completed, the learning control unit 208 calculates a gradient of a parameter of the neural network of the feature conversion unit 105 using an error backpropagation method (backpropagation) [a backpropagation of the training procedure] (step S243).”
Ichino and Ran are analogous arts as they are both related to neural network training using softmax. It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to have combined the backpropagation softmax temperature training of Ichino with the teachings of Ran to arrive at the present invention, in order to improve training, as stated in Ichino, paragraph 0184, “Thereby, the authentication device 100 is expected to perform authentication with relatively high accuracy using a feature in which a part having many features for personal identification is emphasized.”
Claim 10 rejected under 35 U.S.C. 103 over Ran as modified by Liu in view of Chen, US Pre-Grant Publication No. 2020/0074318 (hereafter Chen).
Ran as modified by Liu teaches “The method of claim 1.”
Ran as modified by Liu does not explicitly teach “in accordance with a determination that an inference service for the neural network is activated, storing the first plurality of codebooks in a cache.”
Chen teaches “accordance with a determination that an inference service for the neural network is activated, storing the first plurality of codebooks in a cache”: Chen, paragraph 0273, “Example 7 includes the subject matter of Examples 1 -6, wherein the one or more processors are further to: assign one or more caches to one or more layers of the plurality of layers of the neural network to expedite inference acceleration for the neural network [in accordance with a determination that an inference service for the neural network is activated, storing the first plurality of codebooks in a cache].”
Chen and Ran are analogous arts as they are both related to neural network efficiency improvements. It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to have combined the caching of neural network data of Chen with the teachings of Ran to arrive at the present invention, in order to improve inference processing speed, as stated in Chen, paragraph 0273, “Example 7 includes the subject matter of Examples 1 -6, wherein the one or more processors are further to: assign one or more caches to one or more layers of the plurality of layers of the neural network to expedite inference acceleration for the neural network.”
Claim 11 rejected under 35 U.S.C. 103 over Ran as modified by Liu in view of Wikipedia, “Divide-and-conquer algorithm,” version of May 2023 (hereafter Wikipedia).
Ran as modified by Liu teaches “The method of claim 1.”
Ran further teaches (bold only) “wherein a first codebook of the first plurality of codebooks is divided into a plurality of sub-codebooks, a sub-codebook comprising two or more centroids, the first codebook being associated with a first input sub-vector of the first plurality of input sub-vectors, and wherein determining the respective target centroids comprises selecting a plurality of candidate target centroids from the plurality of sub-codebooks based on parallel distance comparison for the plurality of sub-codebooks, the parallel distance comparison is configured to compare distances between the first input sub-vector and respective centroids in the plurality of sub-codebooks; and determining a target centroid for the first input sub-vector from the plurality of candidate target centroids by comparing distances between the first input sub-vector and the plurality of candidate target centroids”: Ran, section III, paragraph 1, “For an intermediate CNN layer, consider the flattened feature matrix X ∈ ℝcink2×HoutWout, where cin and k are the number of input channels and the kernel size, Hout and Wout are height and width of the output feature, codebooks C ∈ ℝcink2 x p are assigned with parameters to construct an embedding table for the features [the first codebook being associated with a first input sub-vector of the first plurality of input sub-vectors], where p is the number of choices for each codebook C(j), j = 1, 2, …, D. C(j)m ∈ ℝd are called prototypes [determining the respective target centroids comprises selecting a plurality of candidate target centroids], m = 1, 2, . . . , p (cf. Fig. 1(c))”; Ran, section III, paragraph 2, “In short, PECAN is mapping (quantizing) the original input features onto prototype patterns in compact codebooks, then multiplication between weights (F) and features (X) can be approximated by lookup table operation during inference”; Ran, Fig. 2 caption, “When approximating subvectors with the closest prototypes [based on … distance comparison; the … distance comparison is configured to compare distances between the first input sub-vector and respective centroids … ; and determining a target centroid for the first input sub-vector], PECAN-A and PECAN-D adopt different assignment schemes.”
Ran as modified by Liu does not explicitly teach (bold only) “wherein a first codebook of the first plurality of codebooks is divided into a plurality of sub-codebooks, a sub-codebook comprising two or more centroids, the first codebook being associated with a first input sub-vector of the first plurality of input sub-vectors, and wherein determining the respective target centroids comprises selecting a plurality of candidate target centroids from the plurality of sub-codebooks based on parallel distance comparison for the plurality of sub-codebooks, the parallel distance comparison is configured to compare distances between the first input sub-vector and respective centroids in the plurality of sub-codebooks; and determining a target centroid for the first input sub-vector from the plurality of candidate target centroids by comparing distances between the first input sub-vector and the plurality of candidate target centroids.”
Wikipedia teaches (bold only) “wherein a first codebook of the first plurality of codebooks is divided into a plurality of sub-codebooks, a sub-codebook comprising two or more centroids, the first codebook being associated with a first input sub-vector of the first plurality of input sub-vectors, and wherein determining the respective target centroids comprises selecting a plurality of candidate target centroids from the plurality of sub-codebooks based on parallel distance comparison for the plurality of sub-codebooks, the parallel distance comparison is configured to compare distances between the first input sub-vector and respective centroids in the plurality of sub-codebooks; and determining a target centroid for the first input sub-vector from the plurality of candidate target centroids by comparing distances between the first input sub-vector and the plurality of candidate target centroids”: Wikipedia, paragraph 4, “The divide-and-conquer paradigm is often used to find an optimal solution of a problem. Its basic idea is to decompose a given problem into two or more similar, but simpler, subproblems [is divided into a plurality of sub-codebooks, a sub-codebook comprising two or more centroids], to solve them in turn [from the plurality of sub-codebooks based on parallel distance comparison for the plurality of sub-codebooks], and to compose their solutions to solve the given problem [from the plurality of candidate target centroids by comparing distances between the first input sub-vector and the plurality of candidate target centroids]. Problems of sufficient simplicity are solved directly. For example, to sort a given list of n natural numbers, split it into two lists of about n/2 numbers each, sort each of them in turn, and interleave both results appropriately to obtain the sorted version of the given list (see the picture). This approach is known as the merge sort algorithm.”
Wikipedia and Ran are analogous arts as they are both related to algorithmic efficiency. It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to have combined the divide and conquer algorithm from Wikipedia with the closest-value search of Ran to arrive at the present invention’s finding of a closest value through dividing the list of candidates and comparing the closest result in each sub-list, in order to take advantage of parallelism for performance improvements, as stated in Wikipedia, “Parallelism,” “Divide-and-conquer algorithms are naturally adapted for execution in multi-processor machines, especially shared-memory systems where the communication of data between processors does not need to be planned in advance because distinct sub-problems can be executed on different processors.”
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Moshovos, US Pre-Grant Publication No. 2022/0092382, discloses a method for neural network inference using a lookup table populated by centroids of clusters of values.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to VINCENT SPRAUL whose telephone number is (703) 756-1511. The examiner can normally be reached M-F 9:00 am - 5:00 pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, MICHAEL HUNTLEY can be reached at (303) 297-4307. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/VAS/ Examiner, Art Unit 2129
/MICHAEL J HUNTLEY/Supervisory Patent Examiner, Art Unit 2129
Prosecution Insights