DETAILED ACTION
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 .
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Regarding Claim 1,
(Step 1): Claim 1 recites A system for processing input data for a first transform network, comprising, thus a machine, one of the four statutory categories of patentable subject matter,
(Step 2A Prong 1): However, Claim 1 further recites providing a mapping of N input nodes for the first transform network to the n input nodes of the second transform network, wherein N is greater than n; which constitutes the evaluation of input nodes of the first transform network to determine mapping relationships to input nodes of the second network, thus corresponding to a mental process which can be done mentally or by pen and paper;
using the mapping to map the N input nodes to n input nodes; which constitutes the evaluation of the mapping to determine which input nodes map to select input nodes, thus corresponding to a mental process which can be done mentally or by pen and paper;
Thus, Claim 1 recites an abstract idea.
(Step 2A Prong 2): The claim does not recite any additional elements which integrate the abstract idea into a practical application because the additional elements consist of:
a plurality of processing units, which are interconnected, to receive input data for
n input nodes for a second transform network to process at interlinked stages of nodes in the processing units, which is implementing an abstract idea on generic computer components (MPEP 2106.05(f)) as well as merely reciting insignificant extra-solution activity of data gathering (MPEP 2106.05(g))
and wherein a plurality of the N input nodes of the first transform network map to one of the n input nodes of the second transform network, which merely recites the particular technological environment or field of use in which the abstract idea is to be performed (MPEP 2106.05(h))
and a transform manager to perform operations, the operations comprising, which is implementing an abstract idea on generic computer components (MPEP 2106.05(f))
receiving input data from the N input nodes, which is merely reciting insignificant extra-solution activity of data gathering (MPEP 2106.05(g))
and loading the received input data for the n input nodes into the processing units to perform computations operations with respect to the input data at the interlinked stages of nodes in the processing units, which merely recites the particular technological environment or field of use in which the abstract idea is to be performed (MPEP 2106.05(h))
and thus, the claim is directed to the abstract idea of evaluating input nodes of neural networks to determine mappings between a first and second set of input nodes.
(Step 2B) The additional elements, taken alone or in combination, cannot provide significantly
more than the abstract idea itself because elements a), c) (via MPEP 2106.05(f), “apply it on a computer”) cannot provide an inventive concept, elements b), e) (via MPEP 2106.05(h)) cannot integrate the abstract idea into a practical application or provide significantly more than the abstract idea itself, and elements a), d) constitutes further well-understood, routine, and conventional activity of “storing and retrieving information in memory” by MPEP 2106.05(d), which cannot provide significantly more than the abstract idea itself. Thus, Claim 1 is subject-matter ineligible.
Claims 2, 3, 10 recite additional steps of the abstract idea (mental processes) but merely recite insignificant extra-solution activity of data gathering and data outputting (MPEP 2106.05(g)) and therefore constitutes further well-understood, routine, and conventional activity of “storing and retrieving information in memory” by MPEP 2106.05(d), which cannot provide significantly more than the abstract idea itself. Thus, Claims 2, 3, 10 are subject-matter ineligible.
Claims 4, 6 recite additional steps of the abstract idea (mental processes) but merely recite instances of implementing an abstract idea on generic computer components and thus (via MPEP 2106.05(f), “apply it on a computer”) cannot provide an inventive concept. Thus, Claims 4, 6 are subject-matter ineligible.
Claims 5, 7, 8, 9 recite additional steps of the abstract idea (mental processes) but merely recite the particular technological environment or field of use in which the abstract idea is to be performed and thus (via MPEP 2106.05(h)) cannot integrate the abstract idea into a practical application or provide significantly more than the abstract idea itself. Thus, Claims 5, 7, 8, 9 are subject-matter ineligible.
Claims 11, 12, 13, 14 and 15 recite a computer program product comprising a computer readable storage medium with code to perform the method executed by the system of Claims 1, 2, 5, 8 and 10 respectively. As the implementation of an abstract idea on generic computer components cannot integrate an abstract idea into a practical application nor provide an inventive concept (see MPEP 2106.05(f)(2)), Claims 11, 12, 13, 14 and 15 are rejected for reasons set forth in the rejection of Claims 1, 2, 5, 8 and 10 respectively.
Claims 16, 17, 18, 19 and 20 recite the method performed by the system of Claims 1, 2, 5, 8 and 10 respectively. As the implementation of an abstract idea on generic computer components cannot integrate an abstract idea into a practical application nor provide an inventive concept (see MPEP 2106.05(f)(2)), Claims 16, 17, 18, 19 and 20 are rejected for reasons set forth in the rejection of Claims 1, 2, 5, 8 and 10 respectively.
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-7, 10; 11-13, 15; 16-18, 20 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Alizadeh vahid et al. (“Butterfly Transform: An Efficient FFT Based Neural Architecture Design” [2020], hereinafter “Alizadeh vahid”).
Regarding Claim 1,
Alizadeh vahid discloses A system for processing input data for a first transform network, comprising:
a plurality of processing units, which are interconnected, to receive input data for
n input nodes for a second transform network to process at interlinked stages of nodes in the processing units; (Alizadeh vahid [Abstract];
PNG
media_image1.png
355
341
media_image1.png
Greyscale
Alizadeh vahid [Figure 2];
PNG
media_image2.png
273
694
media_image2.png
Greyscale
Alizadeh vahid [Section I Paragraph 3]; “We propose a set of principles to design a replacement for pointwise convolutions motivated by both efficiency and accuracy. The proposed principles are as follows: (1) full connectivity from every input to all outputs: to allow outputs to use all available information, (2) large information bot tleneck: to increase representational power throughout the network, (3) low operation count: to reduce the computa tional cost, (4) operation symmetry: to allow operations to be stacked into dense matrix multiplications. In Section 3, we formally define these principles, and mathematically prove a lower-bound of O(nlogn) operations to satisfy these princi ples. We propose a novel, lightweight convolutional building block based on the Butterfly Transform (BFT). We prove that BFT yields an asymptotically optimal FLOP count under these principles. We show that BFT can be used as a drop-in replacement for pointwise convolutions in several state-of-the-art effi cient CNNs. This significantly reduces the computational bottleneck for these networks. For example, replacing point wise convolutions with BFT decreases the computational bottleneck of MobileNetV1 from 95% to 60%, as shown in Figure 3. We empirically demonstrate that using BFT leads to significant increases in accuracy in constrained settings, in cluding up to a 6.75% absolute Top-1 gain for MobileNetV1, 4.4% for ShuffleNet V2 and 5.4% for MobileNetV3 on the ImageNet[7] dataset. There have been several efforts on using butterfly operations in neural networks [20, 6, 33] but, to the best of our knowledge, our method outperforms all other structured matrix methods (Table 2b) for replacing pointwise convolutions as well as state-of-the-art Neural Architecture Search (Table 2a) by a large margin at low FLOP ranges” wherein drop-in replacement for pointwise convolutions in state-of-the-art CNNs with Butterfly Transformation based operations thus reads on a plurality of processing units which are interconnected (CNNs comprising such processing units) to receive input data for n input nodes for a second transform network to process (BFT-replaced CNN and its associated input tensor displayed in Figure 2))
providing a mapping of N input nodes for the first transform network to the n input nodes of the second transform network, wherein N is greater than n, and wherein a plurality of the N input nodes of the first transform network map to one of the n input nodes of the second transform network (Alizadeh vahid [Figure 2];
PNG
media_image3.png
262
688
media_image3.png
Greyscale
Wherein the BFT procedure of remapping the inputted tensor nodes of the transform network to n remapped input nodes being done in recursive fashion thus reads on a provided mapping of N input nodes for a first transform network to the n input nodes of the second transform network; wherein the recursive procedure involving 2 of the N input nodes (visualized by blue and red unilateral vectors) being mapped to a single n input node reads on N being greater than n)
and a transform manager to perform operations, the operations comprising: receiving input data from the N input nodes; using the mapping to map the N input nodes to n input nodes; and loading the received input data for the n input nodes into the processing units to perform computations operations with respect to the input data at the interlinked stages of nodes in the processing units (Alizadeh vahid [Figure 2];
PNG
media_image4.png
268
693
media_image4.png
Greyscale
Wherein the BFT(n, 2) transform structure enforcing butterfly transformations upon received N input nodes to remap recursively onto n input nodes is performed; wherein such a structure performing butterfly transforms with respect to the input data at the interlinked stages of nodes (mid-recursion) in the processing units thus reads on loading the received input data for the n input nodes to perform computations operations)
Regarding Claim 2,
Alizadeh vahid teaches the method of Claim 1 (and thus the rejection of Claim 1 is incorporated). Alizadeh vahid further discloses wherein the operations further comprise:
a near memory device, associated with the processing units, to store data at the n
input nodes that map to the processing units, wherein processing the received input data
comprises sequentially performing operations on the received input data (Alizadeh vahid [Algorithm 1];
PNG
media_image5.png
365
347
media_image5.png
Greyscale
Wherein the function containing variable definitions storing associated data variables recursively through iterative remapping thus reads on a near memory device associated with the processing units to store data at the n input nodes that map to the processing units; wherein performing such BFT operations upon the sequentially split sequences thus reads on sequentially performing operations on the received input data)
Regarding Claim 3,
Alizadeh vahid teaches the method of Claim 2 (and thus the rejection of Claim 2 is incorporated). Alizadeh vahid further discloses wherein the N input data is stored in the near memory device according to the mapping that maps the N input nodes to the n input nodes (Alizadeh vahid [Algorithm 1];
PNG
media_image5.png
365
347
media_image5.png
Greyscale
Wherein the recursive function comprising inputted Data X representing the first N input data thus reads on the storage of such N input data; wherein the storage of X recursively as it is split sequentially thus reads on the storage of N input data according in some way to the mapping that maps the N input nodes to the n input nodes as such storage of X ends when the mapping is completed recursively and an end condition is met)
Regarding Claim 4,
Alizadeh vahid teaches the method of Claim 2 (and thus the rejection of Claim 2 is incorporated). Alizadeh vahid further discloses wherein the near memory device comprise a first set of memory devices, further comprising: a second set of memory devices coupled to the processing units to provide additional inputs to apply to the processed input data in the first set of memory devices (Alizadeh vahid [Section 5]; “A weakness of our model is that there is an increase in working memory when using BFT since we must add substantially more channels to maintain the same number of FLOPs as the original network. For example, a MobileNetV1-2.0+BFT has the same number of FLOPS as a MobileNetV1-0.5, which means it will use about four times as much working memory. Please note that the intermediate BFLayers can be computed in-place so they do not increase the amount of working memory needed. Due to using wider channels, GPU training time is also increased. In our implementation, at the forward pass, we calculate B(n,k) from the current weights of the BFLayers, which is a bottleneck in training. Introducing a GPU implementation of butterfly operations would greatly reduce training time.” wherein the memory device specified to contain the same number of Floating point operations per second across its MobileNET version comprising several sets of memory devices in its working memory thus reads on the inputs of Algorithm 1 being associated with at least a first and second set of memory devices coupled to the processing units to store such processed input data throughout recursion)
Regarding Claim 5,
Alizadeh vahid teaches the method of Claim 1 (and thus the rejection of Claim 1 is incorporated). Alizadeh vahid further discloses wherein the interlinked stages of nodes in each of the processing units implement a radix-k butterfly operation on input data at the n input nodes associated with the processing units, wherein there are M butterfly units per processing units, wherein M*k data elements are consumed in parallel within each of the processing units (Alizadeh vahid [Section 3.2];
PNG
media_image6.png
480
338
media_image6.png
Greyscale
)
Regarding Claim 6,
Alizadeh vahid teaches the method of Claim 1 (and thus the rejection of Claim 1 is incorporated). Alizadeh vahid further discloses wherein the interlinked stages of nodes in the processing units link with stages of nodes in other of the processing units, wherein the processing units process input data from the n input nodes associated with other of the processing units (Alizadeh vahid [Section 3.2];
PNG
media_image6.png
480
338
media_image6.png
Greyscale
PNG
media_image7.png
279
343
media_image7.png
Greyscale
Wherein product of butterfly matrices, each associated with their own respective input sequence vector, thus read on some interlinking of stages of the nodes in the plurality of processing units)
Regarding Claim 7,
Alizadeh vahid teaches the method of Claim 1 (and thus the rejection of Claim 1 is incorporated). Alizadeh vahid further discloses wherein the processing units comprise processing tiles, wherein n comprises a number of the processing tiles times a number of data elements that can be consumed in parallel within a processing tile (Alizadeh vahid [Section 3.2];
PNG
media_image8.png
145
332
media_image8.png
Greyscale
Wherein the partitioning of channels to k parts thus reads on some n number of processing tiles of size n/k, wherein k represents the number of data elements that can be consumed in parallel within a processing tile)
Regarding Claim 10,
Alizadeh vahid teaches the method of Claim 1 (and thus the rejection of Claim 1 is incorporated). Alizadeh vahid further discloses a near memory device coupled to the processing units with memory devices to store and buffer the input data from the N input nodes before loading into butterfly units of the processing units (Alizadeh vahid [Algorithm 1];
PNG
media_image5.png
365
347
media_image5.png
Greyscale
Wherein the recursive function comprising the storage of inputted data tensor X and continued buffered storage of X1 and X2 across iterative recursions of input node mappings through the butterfly transform units thus reads on such process units storing and buffering input data from the N input nodes before loading into butterfly units of the processing units (i.e. retaining split input data across recursion iterations until recursion ends and all butterfly recursive operations are executed)
Claims 11, 12, 13 and 15 recite a computer program product comprising a computer readable storage medium with code to perform the method executed by the system of Claims 1, 2, 5 and 10 respectively. Thus, Claims 11, 12, 13 and 15 are rejected for reasons set forth in the rejection of Claims 1, 2, 5 and 10 respectively.
Claims 16, 17, 18 and 20 recite the method performed by the system of Claims 1, 2, 5 and 10 respectively. Thus, Claims 16, 17, 18 and 20 are rejected for reasons set forth in the rejection of Claims 1, 2, 5 and 10 respectively.
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.
Claims 8-9; 14; 19 are rejected under 35 U.S.C. 103 as being unpatentable over Alizadeh vahid et al. (“Butterfly Transform: An Efficient FFT Based Neural Architecture Design” [2020], hereinafter “Alizadeh vahid”) in view of Reid (US PGPub #20240289416 published 8/29/24 having priority to provisional application #63486935 filed 2/24/2023)
Regarding Claim 8,
Alizadeh vahid teaches the method of Claim 1 (and thus the rejection of Claim 1 is incorporated). Alizadeh vahid fails to explicitly disclose but Reid discloses wherein the mapping of the N input nodes to the n input nodes is performed by performing at least one folding of the N input nodes (Reid [0020]; “In mathematics, a “transform” maps a function from its original domain space into another domain space, where some of the properties of the original function might be more easily characterized and manipulated than in the original domain space. The transformed function can generally be mapped back to the original domain space using the inverse transform. As but one example, the Discrete Fourier Transform (DFT) maps a time-domain signal to a frequency-domain signal; the Inverse Discrete Fourier Transform (IDFT) maps a frequency-domain signal to a time-domain counterpart. The DFT has an optimized variant referred to as the Fast Fourier Transform (FFT). As another example, the Discrete Cosine Transform (DCT) is a variant commonly used in image and video processing because it does not include imaginary sine components. Still other transforms include wavelet transforms which are often used for signals which have similarity across different time scales. While the present discussion is presented in the context of a DFT computation, artisans of ordinary skill in the related arts will readily appreciate that many other transforms (e.g., multi-dimensional FFT/IFFT, real FFT (RFFT)/IRFFT, DCT/IDCT, non-radix-2 decimation, wavelet transforms, and/or any other low-displacement-rank transforms, etc.) have similar computational steps.”
Reid [0036]; “FIG. 4 summarizes the exemplary single stage decomposition and the two-stage decomposition with the modulo-k subvector nomenclature. As shown, a single-stage decomposition may be rewritten as EQN. 26 using the sparse permutation matrix P1. Similarly, a 2nd stage decomposition may be rewritten as EQN. 27 using the sparse permutation matrix P2. While the modulo-k subvector nomenclature provides a concise notation, the underlying computation is a multi-matrix operation. For reference, FIG. 5 depicts a two-stage decomposition of an 8-point DFT as a multi-matrix operation. Here, the 8-point DFT may be initially expressed as EQN. 28, which is then factorized to EQN. 29. As shown, the first matrix corresponds to the 1st order Twiddle Stage (T(N)), the second matrix corresponds to two parallel 2nd order
PNG
media_image9.png
33
160
media_image9.png
Greyscale
and the third matrix corresponds to four parallel 2-point
PNG
media_image10.png
38
125
media_image10.png
Greyscale
More generally, higher-order decompositions can be performed by adding more even/odd permutation stages prior to the DFT process (e.g., a 3rd order decomposition would use 3 permutation stages to decompose to
PNG
media_image11.png
41
67
media_image11.png
Greyscale
a 4th order decomposition would use 4 permutation stages to decompose to
PNG
media_image12.png
35
71
media_image12.png
Greyscale
”
wherein the decomposition of the model comprising modifications to the DFT process comprising the addition of even/odd permutation stages is thus interpreted as performing foldings of N input nodes in the Fourier transform; wherein such a decomposition indirectly reads on mapping of the N input nodes to the n input nodes since decomposition inherently changes the structure of the network and thus involves changed mappings between the original N input nodes and secondary post-decomposition n input nodes)
It would have been obvious to modify Alizadeh vahid’s butterfly-transform variant of the fast Fourier transform to perform Reid’s multiple stage decompositions comprising folding N input nodes prior to Alizadeh vahid ’s BFT process. One would have been motivated to do so because “With a single stage of decomposition, it [Fourier Transform] is reduced to two smaller DFTs, each of [smaller] complexity O(N^2/4)” (Reid [0032]) wherein the decomposition comprising folding of the N input nodes contributes to reduction of the mapping complexity of the N input nodes during Alizadeh’s Butterfly Fourier Transformations.
Provisional support for above sections disclosed: (Reid [0031];
PNG
media_image13.png
255
648
media_image13.png
Greyscale
Reid [0013]; “ In mathematics, a “transform” maps a function from its original domain space into another domain space, where some of the properties of the original function might be more easily characterized and manipulated than in the original domain space. The transformed function can generally be mapped back to the original domain space using the inverse transform. As but one example, the Discrete Fourier Transform (DFT) maps a time-domain signal to a frequency-domain signal; the Inverse Discrete Fourier Transform (IDFT) maps a frequency-domain signal to a time-domain counterpart. The DFT has an optimized variant referred to as the Fast Fourier Transform (FFT). As another example, the Discrete Cosine Transform (DCT) is a variant commonly used in image and video processing because it does not include imaginary sine components. Still other transforms include wavelet transforms which are often used for signals which have similarity across different time scales. While the present discussion is presented in the context of a DFT computation, artisans of ordinary skill in the related arts will readily appreciate that many other transforms (e.g., multi-dimensional FFT/IFFT, real FFT (RFFT)/IRFFT, DCT/IDCT, non-radix-2 decimation, wavelet transforms, and/or any other low-displacement-rank transforms, etc.) have similar computational steps”
Regarding Claim 9,
The combination of Alizadeh vahid/Reid teaches the method of Claim 8 (and thus the rejection of Claim 8 is incorporated). The combination already discloses wherein F comprises a number of foldings,
wherein F is at least one, and wherein n comprises N divided by 2F (Reid [0036]; “FIG. 4 summarizes the exemplary single stage decomposition and the two-stage decomposition with the modulo-k subvector nomenclature. As shown, a single-stage decomposition may be rewritten as EQN. 26 using the sparse permutation matrix P1. Similarly, a 2nd stage decomposition may be rewritten as EQN. 27 using the sparse permutation matrix P2. While the modulo-k subvector nomenclature provides a concise notation, the underlying computation is a multi-matrix operation. For reference, FIG. 5 depicts a two-stage decomposition of an 8-point DFT as a multi-matrix operation. Here, the 8-point DFT may be initially expressed as EQN. 28, which is then factorized to EQN. 29. As shown, the first matrix corresponds to the 1st order Twiddle Stage (T(N)), the second matrix corresponds to two parallel 2nd order
PNG
media_image9.png
33
160
media_image9.png
Greyscale
and the third matrix corresponds to four parallel 2-point
PNG
media_image10.png
38
125
media_image10.png
Greyscale
More generally, higher-order decompositions can be performed by adding more even/odd permutation stages prior to the DFT process (e.g., a 3rd order decomposition would use 3 permutation stages to decompose to
PNG
media_image11.png
41
67
media_image11.png
Greyscale
a 4th order decomposition would use 4 permutation stages to decompose to
PNG
media_image12.png
35
71
media_image12.png
Greyscale
”)
Claim 14 recites a computer program product comprising a computer readable storage medium with code to perform the method executed by the system of Claim 8. Thus, Claim 14 is rejected for reasons set forth in the rejection of Claim 8.
Claim 19 recites the method performed by the system of Claim 8. Thus, Claim 19 is rejected for reasons set forth in the rejection of Claim 8.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant’s disclosure:
“DETERMINE VALID DROP TARGETS FOR NODES FROM MAPPING” (US 20200403859 A1) which discloses mapping of a first neural network’s input nodes to a smaller neural network’s input nodes for complexity reduction in model computation.
“RESTRUCTURING DEEP NEURAL NETWORKS TO REDUCE THE NUMBER OF PARAMETERS” (US 20200160144 A1) which discloses a plurality of processors for restructuring of a neural network comprising re-mappings of the original input nodes
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JONATHAN J KIM whose telephone number is (571)272-0523. The examiner can normally be reached 9-6.
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, Matt Ell can be reached on (571) 270-3264. 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
/JONATHAN J KIM/Examiner, Art Unit 2141 /MATTHEW ELL/Supervisory Patent Examiner, Art Unit 2141
Prosecution Insights