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 .
Drawings
The drawings are objected to as failing to comply with 37 CFR 1.84(p)(5) because they do not include the following reference sign(s) mentioned in the description: 272 (¶[0039], described as "vehicle sensors"). Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either "Replacement Sheet" or "New Sheet" pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Specification
The disclosure is objected to because of the following informalities: (a) in ¶[0043], the reference numeral "202" is inconsistently used to refer to "a first image sensor," whereas elsewhere in the specification (e.g., ¶[0038]) reference numeral 202 designates "the second image sensor" — correction of this inconsistent reference numeral usage is required; (b) in ¶[0072], "a absolute difference" should read --an absolute difference--; and (c) in ¶[0076], "In certain limitations" should read --In certain implementations--.
Appropriate correction is required.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 14, 15, 16, 17, and 18 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 14 depends from system claim 11, which recites a memory storing instructions that, when executed, "cause the at least one processor to" perform a series of recited actions. Claim 14 recites "further comprising determining normalized differences ..." without tying this limitation to the "cause the at least one processor to" instruction structure of claim 11, instead phrasing it as an active method step in the manner of a method claim (compare claim 4, which properly depends from method claim 1). It is therefore unclear whether claim 14 requires only a system possessing instructions capable of causing the processor to perform this determination, or requires that the determining step actually be performed. See IPXL Holdings, L.L.C. v. Amazon.com, Inc., 430 F.3d 1377, 1384 (Fed. Cir. 2005) (claim indefinite where it could not be determined whether infringement requires making the apparatus or performing the recited act). For purposes of examination, claim 14 is interpreted under BRI as though it recited that the instructions further cause the at least one processor to determine normalized differences based on the differences ..., wherein the attention weights are determined based on the normalized differences, consistent with specification at ¶[0085].
Claim 15 depends from and inherits the indefiniteness of claim 14 for the reasons set forth above. For purposes of examination, claim 15 is interpreted under BRI consistently with claim 14, as further specifying that the instructions cause the at least one processor to determine the normalized differences based on a size of a feature vector for the encoded input data.
Claim 16 depends from system claim 12 (which depends from claim 11) and recites "further comprising determining the attention weights ..." in the same unlinked active-step format identified for claim 14 above, raising the same IPXL Holdings ambiguity as to whether infringement requires making a capable system or actually performing the determination. For purposes of examination, claim 16 is interpreted under BRI as though it recited that the instructions further cause the at least one processor to determine the attention weights based on predetermined values within a lookup table that correspond to the differences ..., consistent with specification at ¶[0072]-[0076].
Claim 17 depends from and inherits the indefiniteness of claim 16 for the reasons set forth above. For purposes of examination, claim 17 is interpreted under BRI consistently with claim 16, as further specifying that the predetermined values within the lookup table are determined using a corresponding instruction within the machine learning processor.
Claim 18 depends from and inherits the indefiniteness of claim 16 for the reasons set forth above. For purposes of examination, claim 18 is interpreted under BRI consistently with claim 16, as further specifying that the encoded input data is quantized in one of a 4-bit integer format or an 8-bit integer format.
Appropriate correction is required. Applicant may amend claims 14-18 to recite that the instructions of the parent system claim further cause the at least one processor to perform the recited determination (e.g., 'wherein the instructions further cause the at least one processor to determine ...'), consistent with the format of parent claim 11.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1-5, 9 and 10 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Adder Attention for Vision Transformer to Shu et al. (hereinafter Shu).
Per claim 1, Shu discloses A method (Shu: p. 3, Section 3…Shu presents the Adder Transformer, a method that implements the multi-head attention and feed-forward modules of a transformer using adder operations in place of multiplications, which constitutes a method under BRI, "In this section, we present the Adder Transformer— which implement the multi-head attention module and FFN module using adder operations"), comprising:
receiving encoded input data for a machine learning model, wherein the encoded input data includes query values and key values (Shu: p. 3, Section 3.1, Eq. (4)…Shu's adder linear transformation projects the input embedding through the weight matrices WQ, WK and WV to produce the query, key and value matrices that the adder multi-head self-attention consumes, so the query and key values are an encoded form of the received input, which constitutes the receiving encoded input data for a machine learning model, wherein the encoded input data includes query values and key values under BRI, "we maximize the use of additions by taking ℓ1 distance to measure the distance between the weight matrices and input embedding as"; p. 3, Section 2…Shu confirms that the queries and the keys of a multi-head self-attention layer are produced by applying linear transformations to that layer's inputs, "For multi-head self-attention, the inputs X … are applied with three different linear transformations and output queries Q …, keys K … and values V …, where M is total number of heads, dq, dq, dv is the dimension of queries, keys and values for each head, respectively");
determining differences between corresponding elements of the query values and the key values (Shu: p. 2, Section 1…Shu replaces the scaled dot-product similarity of a conventional transformer with the ℓ1-distance between the query and the key, and the ℓ1-distance is by definition the sum of the absolute differences of correspondingly indexed elements of the two vectors, which constitutes the determining differences between corresponding elements of the query values and the key values under BRI, "Specifically, we utilize ℓ1-distance between query and key instead of scaled dot-product to measure the distance between them");
determining attention weights for use by the machine learning model based on the differences (Shu: p. 4, Section 3.2.1, Eq. (7)…Eq. (7) defines the adder attention map as the exponential of the negated, scaled ℓ1-distance between each query vector and each key vector, divided by the sum of those exponentials, so the resulting attention weights are computed from the element-wise differences and from nothing else, which constitutes the determining attention weights for use by the machine learning model based on the differences under BRI, "Hence, by calculating ℓ1-distance between each query and key vector, adder multi-head self-attention can be formulated as"); and
determining, by the machine learning model, output data based on the encoded input data and the attention weights (Shu: p. 4, Section 3.2.1, Eq. (9)…Eq. (9) forms each output value as the sum over the value matrix weighted by the corresponding entries of the adder attention map, so the transformer's output is determined from the encoded input data and from the attention weights, which constitutes the determining, by the machine learning model, output data based on the encoded input data and the attention weights under BRI, "For the process of yielding output values, the model jointly attend to information at different positions according to the attention map. Specifically, transformer model multiply the attention map with the value matrix directly to allocate each value with corresponding attention weights as in Eq. 9").
Per claim 2, Shu discloses claim 1, further disclosing wherein the attention weights are determined to identify an influence of corresponding portions of the encoded input data when determining the output data (Shu: p. 4, Section 3.2.1…Shu teaches that the magnitude of each attention score fixes how strongly the corresponding value contributes to the output, which is an identification of the influence of that corresponding portion of the encoded input data, which constitutes the attention weights are determined to identify an influence of corresponding portions of the encoded input data under BRI, "The output is usually positively correlated with the value and the correlation is determined by the magnitude of the attention score after normalization").
Per claim 3, Shu discloses claim 1, further disclosing wherein the attention weights are determined without performing multiplication between elements of the query values and the key values (Shu: p. 4, Section 3.2.1…Shu adopts the ℓ1-norm expressly because it is evaluated with additions and absolute differences rather than products, so no multiplication is performed between the elements of the query and the key, which constitutes the attention weights are determined without performing multiplication between elements of the query values and the key values under BRI, "We design the adder multi-head self-attention in strict compliance with the above principles which measure the similarity between vectors with the help of the ℓ1-norm, an effective measure to avoid multiplication operations"; p. 2, Section 1…Shu states the same objective for the architecture as a whole, "Thus, we are motivated to investigate the feasibility of replacing multiplications by additions in transformer architectures").
Per claim 4, Shu discloses claim 1, further disclosing determining normalized differences based on the differences between the corresponding elements of the query values and the key values, wherein the attention weights are determined based on the normalized differences (Shu: p. 4, Section 3.2.1, Eq. (7)…Shu divides the ℓ1-distance by a scaling factor before exponentiating it, so the attention weights are taken from the scaled, and therefore normalized, differences rather than from the raw differences, which constitutes the determining normalized differences based on the differences … wherein the attention weights are determined based on the normalized differences under BRI, "1/√dt and 1/√da represent the scaling factor of the dot-product attention function and adder attention function, respectively"; p. 4, Section 3.2.1…Shu adjusts that scaling factor from the dot-product form to the adder form so that it normalizes the ℓ1-difference specifically, "According to Theorem. 1, scaling factor 1/√dt in dot-product attention is to counteract the variance explosion, and we adjust the scaling factor to match the adder circumstances").
Per claim 5, Shu discloses claim 4, further disclosing wherein the normalized differences are determined based on a size of a feature vector for the encoded input data (Shu: p. 4, Section 3.2.1…Shu sets dt to the per-head embedding dimension, that is, to the length of the query and key feature vectors, which constitutes the normalized differences are determined based on a size of a feature vector for the encoded input data under BRI, "…generally we set N = Nq = Nkv as number of patches, dt = dh indicates embedding dimension for each head"; p. 4, Section 3.2.1, Theorem 1, Eq. (8)…Shu derives the adder scaling quantity da from that same dt by way of the variance of the ℓ1-distance, so the normalization applied to the differences is fixed by the feature-vector dimension itself, "Assuming that the components of Qm,j,: and Km,i,: are independent random variables following normal distribution, the variance of dot-product and ℓ1-distance between Qm,j,: and Km,i,: can be formulated respectively as follows").
Per claim 9, Shu discloses claim 1, further disclosing training the machine learning model based on the attention weights, the output data, or a combination thereof (Shu: p. 7, Section 3.2.3…Shu trains the adder transformer by back-propagating through the attention layer using the partial derivative of the output with respect to the value and to the normalized attention score, so the model's parameters are updated on the basis of the attention weights and the output data, which constitutes the training the machine learning model based on the attention weights, the output data, or a combination thereof under BRI, "Back-propagation of the attention layer needs to be done with two parts of gradients, namely the partial derivative of the output w.r.t value and normalized attention score and the partial derivative of attention w.r.t query and key, respectively"; p. 7, Section 4.2…Shu carries that training out on the CIFAR datasets, "We use NVIDIA Telsa-V100 GPUs and train baseline model and corresponding adder model for same epochs using PyTorch [22] library for fair comparison").
Per claim 10, Shu discloses claim 1, further disclosing wherein the differences are determined based on at least one of L1 differences between the corresponding elements of the query values and the key values…or a combination thereof (Shu: p. 4, Section 3.2.1, Theorem 1…Shu computes the ℓ1-distance between the query vector and the key vector, and the ℓ1-distance is the L1 difference between their corresponding elements; because the limitation is drafted in the alternative, Shu's disclosure of the L1 branch satisfies it under BRI, which constitutes the differences are determined based on at least one of L1 differences between the corresponding elements of the query values and the key values limitation under BRI, "Assuming that the components of Qm,j,: and Km,i,: are independent random variables following normal distribution, the variance of dot-product and ℓ1-distance between Qm,j,: and Km,i,: can be formulated respectively as follows").
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.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 6, 8, 11-17, 19 and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Shu, as applied in the rejection of claims 1-5, 9 and 10 above, in view of US Pat. Pub. No. 2021/0294784 A1 to Vasyltsov et al. (hereinafter Vasyltsov).
Per claim 6, Shu discloses claim 1.
Shu does not expressly disclose, but Vasyltsov does teach:
determining the attention weights based on predetermined values within a lookup table that correspond to the differences between the corresponding elements of the query values and the key values (Vasyltsov: ¶[0092]…Vasyltsov's lookup table holds precomputed values of the reciprocal of an exponential function over a preset index range, which constitutes the predetermined values within a lookup table under BRI, "The LUT may store information associated with a reciprocal of an exponential function corresponding to a preset range. For example, the LUT may include information associated with values from 1/exp(0) to 1/exp(n), in which n denotes a positive integer"; ¶[0031]…the neural processing unit scales the computed differences and maps them onto the table indexes, so the value retrieved for each element pair corresponds to the difference between that pair, "The NPU may be is further configured to scale differences between a maximum input data value of the input data values and each of the input data values, and map the scaled differences to indexes of the lookup table"; ¶[0096]…Vasyltsov maps the computed difference directly onto the index without intervening processing, "In an example, the hardware accelerator may directly map the difference between maximum input data value and each input data value to the index in the LUT").
Shu and Vasyltsov are analogous art because they are from the same field of endeavor, specifically the hardware-efficient evaluation of the attention and softmax operations of a neural network. They address the same problem of removing the multiplication and division operations from the attention normalization datapath so that the network can be executed with reduced arithmetic cost.
Before the effective filing date of the claimed invention, it would have been obvious to a person having ordinary skill in the art (PHOSITA) to determine the attention weights of Shu's adder multi-head self-attention from the predetermined lookup table values of Vasyltsov, indexed by the same ℓ1-differences between the corresponding query and key elements that Shu already computes.
The suggestion/motivation for doing so would have been provided by Vasyltsov itself, which teaches that evaluating the exponential from a one-dimensional lookup table removes the divider and the multiplier from the softmax datapath and allows the operation to be implemented on a neural processing unit without a large hardware budget, "According to an example embodiment, by calculating a softmax value using only a 1D LUT, it may be possible to reduce the size of the LUT, greatly reduce computational complexity without a need for a divider and/or a multiplier, and implement it in the hardware accelerator 230 such as an NPU without a requirement for a large hardware resource" (Vasyltsov: ¶[0089]). Shu supplies the very quantity by which Vasyltsov's table is indexed, teaching that the adder attention score is obtained by exponentiating a scaled ℓ1-distance between each query and key vector, "Hence, by calculating ℓ1-distance between each query and key vector, adder multi-head self-attention can be formulated as" (Shu: p. 4, Section 3.2.1, Eq. (7)), and Vasyltsov likewise addresses its table with a computed difference, so the two teachings meet at the same operand and a PHOSITA would have had a reasonable expectation of success in substituting the table lookup for Shu's explicit exponential. Furthermore, this is the use of a known technique to improve a similar device in the same way, the rationale of MPEP § 2143(C).
Per claim 8, Shu combined with Vasyltsov discloses claim 6. Vasyltsov further teaches wherein the predetermined values within the lookup table are determined using a corresponding instruction within a machine learning processor (Vasyltsov: ¶[0031]…the neural processing unit itself scales the differences and maps them onto the table indexes, so the retrieval of each predetermined value is an operation carried out inside the machine learning processor, "The NPU may be is further configured to scale differences between a maximum input data value of the input data values and each of the input data values, and map the scaled differences to indexes of the lookup table"; ¶[0026]…Vasyltsov's neural processing unit is configured to load the table and obtain the output values from it, so the predetermined values are determined by the machine learning processor's own operation rather than recomputed outside it, "a neural processing unit (NPU) configured to load the lookup table and obtain output data values corresponding to input data values"; ¶[0101]…Vasyltsov budgets a defined number of accelerator cycles for that load-and-obtain operation, showing the retrieval is a discrete instruction issued within the accelerator, "For example, n cycles may be needed to obtain the maximum input data value, and n cycles may be needed to load the LUT and obtain the output data"). The rationale to combine Vasyltsov with Shu is the same as the parent claim.
Per claim 11, Shu discloses:
…receive encoded input data for a machine learning model, wherein the encoded input data includes query values and key values (Shu: p. 3, Section 3.1, Eq. (4)…Shu's adder linear transformation projects the input embedding through the weight matrices WQ, WK and WV to produce the query, key and value matrices that the adder multi-head self-attention consumes, so the query and key values are an encoded form of the received input, which constitutes the receive encoded input data for a machine learning model, wherein the encoded input data includes query values and key values under BRI, "we maximize the use of additions by taking ℓ1 distance to measure the distance between the weight matrices and input embedding as"; p. 3, Section 2…Shu confirms that the queries and the keys of a multi-head self-attention layer are produced by applying linear transformations to that layer's inputs, "For multi-head self-attention, the inputs X … are applied with three different linear transformations and output queries Q …, keys K … and values V …, where M is total number of heads, dq, dq, dv is the dimension of queries, keys and values for each head, respectively");
determine, … differences between corresponding elements of the query values and the key values (Shu: p. 2, Section 1…Shu replaces the scaled dot-product similarity with the ℓ1-distance between the query and the key, which is the sum of the absolute differences of correspondingly indexed elements of the two vectors, which constitutes the determine … differences between corresponding elements of the query values and the key values under BRI, "Specifically, we utilize ℓ1-distance between query and key instead of scaled dot-product to measure the distance between them");
determine, … attention weights for use by the machine learning model based on the differences (Shu: p. 4, Section 3.2.1, Eq. (7)…Eq. (7) defines the adder attention map as the exponential of the negated, scaled ℓ1-distance between each query vector and each key vector, divided by the sum of those exponentials, so the attention weights are computed from the element-wise differences, which constitutes the determine … attention weights for use by the machine learning model based on the differences under BRI, "Hence, by calculating ℓ1-distance between each query and key vector, adder multi-head self-attention can be formulated as"); and
determine, by the machine learning model, output data based on the encoded input data and the attention weights (Shu: p. 4, Section 3.2.1, Eq. (9)…Eq. (9) forms each output value as the sum over the value matrix weighted by the corresponding entries of the adder attention map, which constitutes the determine, by the machine learning model, output data based on the encoded input data and the attention weights under BRI, "For the process of yielding output values, the model jointly attend to information at different positions according to the attention map. Specifically, transformer model multiply the attention map with the value matrix directly to allocate each value with corresponding attention weights as in Eq. 9").
Shu does not expressly disclose, but Vasyltsov does teach:
A system (Vasyltsov: ¶[0026]…Vasyltsov discloses a neural network device built from a central processing unit and a neural processing unit that together carry out a neural network layer, which constitutes the a system limitation under BRI, "In another general aspect, a neural network device includes a central processing unit (CPU) configured to generate a lookup table in which information associated with a reciprocal of an exponential function is stored, and a neural processing unit (NPU) configured to load the lookup table and obtain output data values corresponding to input data values") comprising:
at least one processor, including at least one machine learning processor (Vasyltsov: ¶[0067]…Vasyltsov's device includes a host processor embodied as a CPU, GPU or application processor, which constitutes the at least one processor under BRI, "The host 210 may be, or embodied by, for example, a central processing unit (CPU), a graphics processing unit (GPU), and an application processor (AP) that are included in the neural network device 200 , but examples are not limited thereto"; ¶[0070]…the same device further includes a hardware accelerator dedicated to operating the neural network and embodied as a neural processing unit or tensor processing unit, which is a processor tailored to machine learning workloads and therefore constitutes the at least one machine learning processor under BRI, "The hardware accelerator 230 may be a module dedicated to operating the neural network and include, for example, a neural processing unit (NPU), a tensor processing unit (TPU), and a neural engine, but examples are not limited thereto"); and
a memory storing instructions which, when executed by the at least one processor, cause the at least one processor to (Vasyltsov: ¶[0067]…Vasyltsov's device holds instructions in its memory and controls the device by executing them on the processor, which constitutes the a memory storing instructions which, when executed by the at least one processor, cause the at least one processor to limitation under BRI, "For example, the host 210 may control the neural network device 200 overall by executing instructions stored in the memory 220 of the neural network device 200"):
determine, by the at least one machine learning processor, … (Vasyltsov: ¶[0027]…Vasyltsov assigns the neural network layer's data-path operations to the NPU acting as the hardware accelerator, so the recited determining steps are performed by a machine learning processor, which constitutes the determine, by the at least one machine learning processor under BRI, "The NPU may be a hardware accelerator"; ¶[0026]…Vasyltsov expressly places the load-and-obtain operations of the layer in the NPU, "and a neural processing unit (NPU) configured to load the lookup table and obtain output data values corresponding to input data values").
Shu and Vasyltsov are analogous art because they are from the same field of endeavor, specifically the execution of neural network inference on dedicated machine learning hardware. They address the same problem of reducing the arithmetic cost of a neural network layer so that the layer can be executed by an embedded accelerator.
Before the effective filing date of the claimed invention, it would have been obvious to a PHOSITA to execute Shu's adder multi-head self-attention on the neural network device of Vasyltsov, in which a processor and a machine learning processor operate on instructions held in a memory.
The suggestion/motivation for doing so would have been provided by Shu itself, which states that the purpose of replacing the transformer's multiplications with additions is to permit the model to be deployed on power-constrained embedded hardware, "The high-power consumption of transformer-based models has blocked them from being deployed on mobile devices, e.g., smart phone, camera, and micro-robots. Therefore, it is necessary to study efficient transformers which can be embedded on mobile devices with affordable computation resources" (Shu: p. 1, Section 1). Vasyltsov supplies precisely such a deployment target, disclosing a neural network device whose accelerator is a dedicated neural processing unit sized so that the layer runs without a large hardware budget, "by calculating a softmax value using only a 1D LUT, it may be possible to reduce the size of the LUT, greatly reduce computational complexity without a need for a divider and/or a multiplier, and implement it in the hardware accelerator 230 such as an NPU without a requirement for a large hardware resource" (Vasyltsov: ¶[0089]), so a PHOSITA seeking the deployment target Shu identifies would have looked to Vasyltsov's device and would have had a reasonable expectation of success, the combination amounting to no more than the execution of a known algorithm on known machine learning hardware. Furthermore, this is the combination of prior art elements according to known methods to yield predictable results, the rationale of MPEP § 2143(A).
Per claim 12, Shu combined with Vasyltsov discloses claim 11. Shu further teaches wherein the attention weights are determined to identify an influence of corresponding portions of the encoded input data when determining the output data (Shu: p. 4, Section 3.2.1…Shu teaches that the magnitude of each attention score fixes how strongly the corresponding value contributes to the output, which is an identification of the influence of that corresponding portion of the encoded input data, which constitutes the attention weights are determined to identify an influence of corresponding portions of the encoded input data under BRI, "The output is usually positively correlated with the value and the correlation is determined by the magnitude of the attention score after normalization").
Per claim 13, Shu combined with Vasyltsov discloses claim 11. Shu further teaches wherein the attention weights are determined without performing multiplication between elements of the query values and the key values (Shu: p. 4, Section 3.2.1…Shu adopts the ℓ1-norm expressly because it is evaluated with additions and absolute differences rather than products, so no multiplication is performed between the elements of the query and the key, which constitutes the attention weights are determined without performing multiplication between elements of the query values and the key values under BRI, "We design the adder multi-head self-attention in strict compliance with the above principles which measure the similarity between vectors with the help of the ℓ1-norm, an effective measure to avoid multiplication operations").
Per claim 14, Shu combined with Vasyltsov discloses claim 11. Shu further teaches determining normalized differences based on the differences between the corresponding elements of the query values and the key values, wherein the attention weights are determined based on the normalized differences (Shu: p. 4, Section 3.2.1, Eq. (7)…Shu divides the ℓ1-distance by a scaling factor before exponentiating it and adjusts that factor from the dot-product form to the adder form, so the attention weights are taken from the scaled, and therefore normalized, differences rather than from the raw differences, which constitutes the determining normalized differences based on the differences … wherein the attention weights are determined based on the normalized differences under BRI, "1/√dt and 1/√da represent the scaling factor of the dot-product attention function and adder attention function, respectively…According to Theorem. 1, scaling factor 1/√dt in dot-product attention is to counteract the variance explosion, and we adjust the scaling factor to match the adder circumstances").
Per claim 15, Shu combined with Vasyltsov discloses claim 14. Shu further teaches wherein the normalized differences are determined based on a size of a feature vector for the encoded input data (Shu: p. 4, Section 3.2.1…Shu's adder scaling factor is 1/√da where da = 2dt(1 − 2/π) and dt is the per-head embedding dimension, so the normalization applied to the differences is fixed by the dimension of the query and key feature vectors themselves, which constitutes the normalized differences are determined based on a size of a feature vector for the encoded input data under BRI, "…generally we set N = Nq = Nkv as number of patches, dt = dh indicates embedding dimension for each head").
Per claim 16, Shu combined with Vasyltsov discloses claim 12. Vasyltsov further teaches determining the attention weights based on predetermined values within a lookup table that correspond to the differences between the corresponding elements of the query values and the key values (Vasyltsov: ¶[0092]…Vasyltsov's lookup table holds precomputed values of the reciprocal of an exponential function over a preset index range, which constitutes the predetermined values within a lookup table under BRI, "The LUT may store information associated with a reciprocal of an exponential function corresponding to a preset range. For example, the LUT may include information associated with values from 1/exp(0) to 1/exp(n), in which n denotes a positive integer"; ¶[0031]…the neural processing unit scales the computed differences and maps them onto the table indexes, so the value retrieved for each element pair corresponds to the difference between that pair, "The NPU may be is further configured to scale differences between a maximum input data value of the input data values and each of the input data values, and map the scaled differences to indexes of the lookup table"; ¶[0096]…Vasyltsov maps the computed difference directly onto the index without intervening processing, "In an example, the hardware accelerator may directly map the difference between maximum input data value and each input data value to the index in the LUT"). The rationale to combine Vasyltsov with Shu is the same as the parent claim.
Per claim 17, Shu combined with Vasyltsov discloses claim 16. Vasyltsov further teaches wherein the predetermined values within the lookup table are determined using a corresponding instruction within the machine learning processor (Vasyltsov: ¶[0031]…the neural processing unit itself scales the differences and maps them onto the table indexes, so the retrieval of each predetermined value is an operation carried out inside the machine learning processor, "The NPU may be is further configured to scale differences between a maximum input data value of the input data values and each of the input data values, and map the scaled differences to indexes of the lookup table"; ¶[0026]…Vasyltsov's neural processing unit is configured to load the table and obtain the output values from it, so the predetermined values are determined by the machine learning processor's own operation rather than recomputed outside it, "a neural processing unit (NPU) configured to load the lookup table and obtain output data values corresponding to input data values"; ¶[0101]…Vasyltsov budgets a defined number of accelerator cycles for that load-and-obtain operation, showing the retrieval is a discrete instruction issued within the accelerator, "For example, n cycles may be needed to obtain the maximum input data value, and n cycles may be needed to load the LUT and obtain the output data"). The rationale to combine Vasyltsov with Shu is the same as the parent claim.
Per claim 19, Shu combined with Vasyltsov discloses claim 11. Shu further teaches wherein the differences are determined based on at least one of L1 differences between the corresponding elements of the query values and the key values…or a combination thereof (Shu: p. 4, Section 3.2.1, Theorem 1…Shu computes the ℓ1-distance between the query vector and the key vector, and that distance is the L1 difference between their corresponding elements, which constitutes the differences are determined based on at least one of L1 differences between the corresponding elements of the query values and the key values under BRI, "Assuming that the components of Qm,j,: and Km,i,: are independent random variables following normal distribution, the variance of dot-product and ℓ1-distance between Qm,j,: and Km,i,: can be formulated respectively as follows").
Per claim 20, Shu discloses …receive encoded input data for a machine learning model, wherein the encoded input data includes query values and key values (Shu: p. 3, Section 3.1, Eq. (4)…Shu's adder linear transformation projects the input embedding through the weight matrices WQ, WK and WV to produce the query, key and value matrices that the adder multi-head self-attention consumes, so the query and key values are an encoded form of the received input, which constitutes the receive encoded input data for a machine learning model, wherein the encoded input data includes query values and key values under BRI, "we maximize the use of additions by taking ℓ1 distance to measure the distance between the weight matrices and input embedding as"; p. 3, Section 2…Shu confirms that the queries and the keys of a multi-head self-attention layer are produced by applying linear transformations to that layer's inputs, "For multi-head self-attention, the inputs X … are applied with three different linear transformations and output queries Q …, keys K … and values V …, where M is total number of heads, dq, dq, dv is the dimension of queries, keys and values for each head, respectively");
determine differences between corresponding elements of the query values and the key values (Shu: p. 2, Section 1…Shu replaces the scaled dot-product similarity with the ℓ1-distance between the query and the key, which is the sum of the absolute differences of correspondingly indexed elements of the two vectors, which constitutes the determine differences between corresponding elements of the query values and the key values under BRI, "Specifically, we utilize ℓ1-distance between query and key instead of scaled dot-product to measure the distance between them");
determine attention weights for use by the machine learning model based on the differences (Shu: p. 4, Section 3.2.1, Eq. (7)…Eq. (7) defines the adder attention map as the exponential of the negated, scaled ℓ1-distance between each query vector and each key vector, divided by the sum of those exponentials, so the attention weights are computed from the element-wise differences, which constitutes the determine attention weights for use by the machine learning model based on the differences limitation under BRI, "Hence, by calculating ℓ1-distance between each query and key vector, adder multi-head self-attention can be formulated as…"); and
determine, by the machine learning model, output data based on the encoded input data and the attention weights (Shu: p. 4, Section 3.2.1, Eq. (9)…Eq. (9) forms each output value as the sum over the value matrix weighted by the corresponding entries of the adder attention map, which constitutes the determine, by the machine learning model, output data based on the encoded input data and the attention weights under BRI, "For the process of yielding output values, the model jointly attend to information at different positions according to the attention map. Specifically, transformer model multiply the attention map with the value matrix directly to allocate each value with corresponding attention weights as in Eq. 9").
Shu does not expressly disclose, but Vasyltsov does teach:
A non-transitory, computer-readable medium storing instructions which, when executed by a processor, cause the processor to (Vasyltsov: ¶[0015]…Vasyltsov expressly provides the same method in the form of a non-transitory computer-readable storage medium whose stored instructions configure the executing processor to perform it, which constitutes the A non-transitory, computer-readable medium storing instructions which, when executed by a processor, cause the processor to limitation under BRI, "A non-transitory computer-readable storage medium may store instructions that, when executed by one or more processors, configure the one or more processors to perform the method"; ¶[0145]…Vasyltsov enumerates the tangible media on which those instructions are fixed, confirming the medium is non-transitory, "The instructions or software to control a processor or computer to implement the hardware components and perform the methods as described above, and any associated data, data files, and data structures, are recorded, stored, or fixed in or on one or more non-transitory computer-readable storage media"):
Shu and Vasyltsov are analogous art because they are from the same field of endeavor, specifically the execution of neural network inference on dedicated machine learning hardware. They address the same problem of reducing the arithmetic cost of a neural network layer so that the layer can be executed by an embedded accelerator.
Before the effective filing date of the claimed invention, it would have been obvious to a PHOSITA to embody Shu's adder multi-head self-attention as instructions stored on the non-transitory computer-readable medium of Vasyltsov, so that a processor executing them performs the recited operations.
The suggestion/motivation for doing so would have been provided by Vasyltsov itself, which teaches that the very method it discloses for the neural network layer is to be distributed and executed as instructions fixed on a non-transitory medium, "A non-transitory computer-readable storage medium may store instructions that, when executed by one or more processors, configure the one or more processors to perform the method" (Vasyltsov: ¶[0015]). Shu in turn is a software method trained and executed on general-purpose accelerator hardware through a software library, "We use NVIDIA Telsa-V100 GPUs and train baseline model and corresponding adder model for same epochs using PyTorch [22] library for fair comparison" (Shu: p. 7, Section 4.2), so a PHOSITA would have recognized that Shu's method is delivered to that hardware as stored instructions and would have had a reasonable expectation of success in fixing it on Vasyltsov's medium. Furthermore, this is the combination of prior art elements according to known methods to yield predictable results, the rationale of MPEP § 2143(A).
Claims 7 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Shu in view of Vasyltsov, as applied in the rejection of claims 6, 8, 11-17, 19 and 20 above, and further in view of ITA: An Energy-Efficient Attention and Softmax Accelerator for Quantized Transformers to Islamoglu et al. (hereinafter Islamoglu).
Per claim 7, Shu combined with Vasyltsov discloses claim 6.
Shu combined with Vasyltsov does not expressly disclose, but Islamoglu does teach:
wherein the encoded input data is quantized in one of a 4-bit integer format or an 8-bit integer format (Islamoglu: p. 3, Section III…Islamoglu's transformer accelerator holds the matrices on which it operates in 8-bit integer quantized form, which constitutes the encoded input data is quantized in one of a 4-bit integer format or an 8-bit integer format under BRI, "The architecture of our transformer accelerator is shown in Figure 2, targeting 8-bit integer quantized matrices"; p. 3, FIG. 2…the figure caption confirms that the accelerator's inputs, and not merely its outputs, are held in that 8-bit format, "Architecture of ITA with 8-bit inputs and weights"; p. 2, Section II.A…Islamoglu identifies those inputs as the query, key and value matrices generated by the attention layer's three linear transformations, so the query and key values are the data held in 8-bit integer format, "In attention, three linear transformations are applied to inputs of size S × E, where S is the sequence length and E is the embedding size, to generate Query (Q), Key (K), and Value (V ) matrices").
Shu, Vasyltsov and Islamoglu are analogous art because all three are from the same field of endeavor, specifically the hardware-efficient execution of transformer attention and softmax operations on embedded machine learning accelerators. They address the same problem of reducing the arithmetic and energy cost of an attention layer so that the layer can be executed on a resource-constrained device.
Before the effective filing date of the claimed invention, it would have been obvious to a PHOSITA to hold the query and key values of the Shu and Vasyltsov combination in the 8-bit integer format taught by Islamoglu, as claims 7 and 18 recite.
The suggestion/motivation for doing so would have been provided by Islamoglu itself, which teaches that 8-bit integer quantization is what makes transformer attention affordable on an embedded accelerator, "we propose ITA, a novel accelerator architecture for transformers and related models that targets efficient inference on embedded systems by exploiting 8-bit quantization and an innovative softmax implementation that operates exclusively on integer values" (Islamoglu: p. 1, Abstract). That is the same objective Shu states for replacing the transformer's multiplications with additions, "Therefore, it is necessary to study efficient transformers which can be embedded on mobile devices with affordable computation resources" (Shu: p. 1, Section 1), and Vasyltsov's lookup table is already sized to an integer word width, "For example, in a case of using an int8 hardware accelerator, w may be determined to be 7" (Vasyltsov: ¶[0128]), so a PHOSITA pursuing the embedded deployment all three references target would have quantized the query and key operands to 8-bit integers and would have had a reasonable expectation of success. Furthermore, this is the use of a known technique to improve a similar device in the same way, the rationale of MPEP § 2143(C).
Per claim 18, Shu combined with Vasyltsov discloses claim 16.
Shu combined with Vasyltsov does not expressly disclose, but Islamoglu does teach:
wherein the encoded input data is quantized in one of a 4-bit integer format or an 8-bit integer format (Islamoglu: p. 3, Section III…Islamoglu's transformer accelerator holds the matrices on which it operates in 8-bit integer quantized form, which constitutes the encoded input data is quantized in one of a 4-bit integer format or an 8-bit integer format under BRI, "The architecture of our transformer accelerator is shown in Figure 2, targeting 8-bit integer quantized matrices"; p. 3, FIG. 2…the figure caption confirms that the accelerator's inputs, and not merely its outputs, are held in that 8-bit format, "Architecture of ITA with 8-bit inputs and weights"; p. 2, Section II.A…Islamoglu identifies those inputs as the query, key and value matrices generated by the attention layer's three linear transformations, so the query and key values are the data held in 8-bit integer format, "In attention, three linear transformations are applied to inputs of size S × E, where S is the sequence length and E is the embedding size, to generate Query (Q), Key (K), and Value (V ) matrices"). The rationale to combine Islamoglu with Shu and Vasyltsov is the same as claim 7.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ALAN CHEN whose telephone number is (571)272-4143. The examiner can normally be reached M-F 10-7.
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, Kamran Afshar can be reached at (571) 272-7796. 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.
/ALAN CHEN/Primary Examiner, Art Unit 2125
Prosecution Insights