DETAILED ACTION
This office action is responsive to the Request for Reconsideration-After Non-Final filed 6/25/2026. The application contains claims 1-10, all examined and rejected.
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 .
Priority
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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-7, 9-10 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wang et al. [US 2021/0256384 A1, hereinafter Wang] in view of Biswas et al. [US 2023/0229892 A1, hereinafter Biswas] in view of Frumkin et al. [US 2020/0342632 A1, hereinafter Frumkin].
With regard to Claim 1,
Wand teach a computer-implemented method (700) for unstructured pruning of a neural network, the computer-implemented method (700) (¶12, “pattern-based DNN pruning approach is disclosed that achieves the benefits of both non-structured and structured pruning while avoiding their weaknesses”, ¶17) comprising:
accessing (702), by a processor (206), a trained neural network (112) to be pruned, the trained neural network (112) comprising one or more neural layers (¶71, “First, for the pre-trained DNN, we scan all the kernels, and for each kernel, we find the four weights with largest magnitudes (including the central weight)”, ¶78, “ADMM-based solution is an iterative process, starting from a pre-trained DNN model”, ¶40)
computing (704), by the processor (206), values of layer parameters of a filter associated with a neural layer of the one or more neural layers based, at least in part, on a pruning criteria (¶76-77, “In kernel pattern pruning, the constraint in the k-th CONV layer is Wk∈Sk:={X|each kernel in X needs to satisfy one specific pattern shape in the pattern set (and non-zero weight values can be arbitrary)}. In connectivity pruning, the constraint in the k-th CONV layer is Wk∈Sk′:={X|the number of nonzero kernels in X is less than or equal to αk} (αk is a predetermined hyperparameter with more discussions later). Both constraints need to be simultaneously satisfied.”, ¶78, “the ADMM-based solution is an iterative process, starting from a pre-trained DNN model. We assign an appropriate pattern for each kernel based on the L2-norm metric in each iteration”, iteratively optimize/train the kernel weights subject to pruning constraints and assign the appropriate pattern based on the L2 norm metric);
characterized in that, the computer-implemented method (700) comprising: determining, by the processor (206), an enumeration (specific kernel pattern selected) among a plurality of enumerations (pattern set) based, at least in part, on the values of the layer parameters of the filter (Fig. 23, Fig. 25, ¶59, “a fixed number of weights are pruned, and the remaining weights (white cells) form specific “kernel patterns”. … For each kernel, it possesses flexibility in choosing among a number of pre-defined patterns”, ¶60, “The selection of an appropriate pattern for each kernel can be naturally done by extending ADMM-based framework”, ¶71, “First, for the pre-trained DNN, we scan all the kernels, and for each kernel, we find the four weights with largest magnitudes (including the central weight) … there are a total of (8 3)=56 number of possible patterns. Suppose we aim at k different patterns in the candidate set. We count and select the Top-k most commonly appeared natural patterns across all kernels in the DNN, thereby forming the pattern candidate set”, ¶78, “it is flexible to select a pattern for each kernel from the pattern set“, “We assign an appropriate pattern for each kernel based on the L2-norm metric in each iteration, to achieve higher flexibility”, ¶70, “ we validate that 6-8 patterns in the set achieves as a desirable tradeoff for the most common 3×3 kernel”, ¶134, “Our evaluation selects 8 patterns that result in ideal performance with a negligible accuracy loss” selecting a pattern for each kernel from the pattern set),
wherein the enumeration is determined among the plurality of enumerations by performing a lookup of the plurality of enumerations in a table based on indices of non-zero layer parameters of the filter (¶71, “for the pre-trained DNN, we scan all the kernels, and for each kernel, we find the four weights with largest magnitudes (including the central weight). These four weights form a 4-entry pattern, called the natural pattern of the kernel. According to the definition of natural patterns, there are a total of (8 3)=56 number of possible patterns. Suppose we aim at k different patterns in the candidate set. We count and select the Top-k most commonly appeared natural patterns across all kernels in the DNN, thereby forming the pattern candidate set (to select from in the subsequent step)”, ¶70, “We need to determine the number of patterns, and design each specific candidate pattern in the pattern set” , ¶78, “it is flexible to select a pattern for each kernel from the pattern set“, “We assign an appropriate pattern for each kernel based on the L2-norm metric in each iteration”, candidate pattern set is a table based on indices of non-zero layer parameters because the natural patterns populating the set are defined by the position/indices of retained non-zero weights, selecting and assigning a pattern per kernel from the set is the lookup determining the enumeration among the plurality of enumerations, Fig. 9-10, DNN layer represented as a filters X kernels grid whose cells carry pattern values (1,2), ¶97, “a matrix represents a CONV layer of DNN and each cell is a kernel with pattern type denoted by the number on it. Empty kernels are the ones pruned by connectivity pruning. The kernels in the same row belong to the same filter”, ¶102, “FKW leverages the pattern information, and stores the kernels with the FKR information that will support later branch-less DNN execution”, ¶103, “ FKW uses five arrays to represent this DNN layer: offset array, reorder array, index array, stride array, and weight array … index array and stride array store kernel-level, and the weight array stores actual weights”, matrix cells are pattern types with each row a filter),
wherein the plurality of enumerations is defined based on a sparsity value of the filter (¶59, “For each kernel (in a CONV filter), a fixed number of weights are pruned, and the remaining weights (white cells) form specific “kernel patterns””, “ every kernel reserves 4 non-zero weights out of the original 3×3 kernel”, “For each kernel, it possesses flexibility in choosing among a number of pre-defined patterns”, ¶71, “when the number of patterns is determined and 4-entry patterns are utilized … These four weights form a 4-entry pattern, called the natural pattern of the kernel. According to the definition of natural patterns, there are a total of (8 3)=56 number of possible patterns …”);
computing (706), by the processor (206), a tag identifier (316) associated with the filter based, at least in part, on the enumeration, the tag identifier (316) having a single index indicating spatial locations of non-zero layer parameters in the filter (Fig. 3, ¶¶59-60, “the remaining weights (white cells) form specific “kernel patterns”. We define the example in FIG. 3 as 4-entry pattern pruning, since every kernel reserves 4 non-zero weights out of the original 3×3 kernel”, kernel pruning patterns are selected using an ADMM-based optimization framework that consider biological connections structure and accuracy, predefined patterns enable compiler level reordering and grouping of kernels with same pattern ID to maximize instruction level parallelism during inference, ¶71, “… we find the four weights with largest magnitudes (including the central weight). These four weights form a 4-entry pattern, called the natural pattern of the kernel. According to the definition of natural patterns, there are a total of (8 3)=56 number of possible patterns. …”, each kernel pattern shape is assigned a unique pattern ID that identified the spatial arrangement of non-zero weights (i.e. tag identifier), ¶99, “the filter similarity used in filter reorder is decided by two factors: first, the number of non-empty kernels in each filter (i.e., the length of each filter); and second, for filters with the same length, the number of kernels at identical positions with identical pattern IDs when the kernels in each filter are ordered according to these IDs”, ¶60, “the pre-defined pattern allows the compiler to reorder and generate codes at filter and kernel levels so that kernels with the same pattern can be grouped for consecutive executions to maximize instruction-level parallelism”, ¶97, “each cell is a kernel with pattern type denoted by the number on it. Empty kernels are the ones pruned by connectivity pruning. The kernels in the same row belong to the same filter”),
wherein computing the tag identifier associated with the filter comprises pruning the filter based, at least in part, on the pruning criteria (¶17, “performing an intra-convolution kernel pruning of the DNN model wherein a fixed number of weights are pruned in each convolution kernel of the DNN model to generate sparse convolution patterns …”, ¶99, “the filter similarity used in filter reorder is decided by two factors: first, the number of non-empty kernels in each filter (i.e., the length of each filter); and second, for filters with the same length, the number of kernels at identical positions with identical pattern IDs when the kernels in each filter are ordered according to these IDs”, ¶77, “each kernel in X needs to satisfy one specific pattern shape in the pattern set … Both constraints need to be simultaneously satisfied”, ¶¶10-13),
and storing (708), by the processor (206), the tag identifier (316) and the non-zero layer parameters for the filter of the trained neural network (112) in a database (204) for inference (¶100, ¶102, “FKW leverages the pattern information, and stores the kernels with the FKR information that will support later branch-less DNN execution”, ¶103, “ FKW uses five arrays to represent this DNN layer: offset array, reorder array, index array, stride array, and weight array … the weight array stores actual weights”, ¶104, “each kernel has four (non-zero) weights …”), and
computing, by the processor (206), an output of the neural network for an inference data by applying the filter to the inference data based on the spatial locations of the non-zero layer parameters identified by the tag identifier (¶107, “In DNN execution, such as a convolution operation, the data access pattern of the input and output is decided by the (none-zero elements) patterns of kernels that are already known after training. Therefore, it is possible to generate the optimized data access code with this information for each pattern of kernels and call them dynamically during the DNN execution. … the index of input data can be directly calculated from kernel pattern.”, ¶71, ¶96, “for a specific DNN layer, the patterns of all kernels are already known after model training, so the inference computation pattern is also known before model deployment”, ¶93, “high-level LR can generate compressed model and associated optimized model execution code by using the pattern-related information”, ¶94, “The inner-most iteration processes kernels in each filter in the order of their pattern types”, ¶59, “the remaining weights (white cells) form specific “kernel patterns” … every kernel reserves 4 non-zero weights out of the original 3×3 kernel …”, claim 2, “performing one or more compiler optimizations based on the sparse convolution patterns for compressed DNN execution”), the application of the filter corresponding to the tag identifier utilizing a reduced number of computations as compared to a conventional filter (¶122, “ the pattern-based pruning reduces the overall computation by 3× to 8×”, ¶130, “PatDNN also reduces the overall computation; thus, it significantly outperforms all other mobile frameworks”, ¶59, “For each kernel (in a CONV filter), a fixed number of weights are pruned, and the remaining weights (white cells) form specific “kernel patterns”. We define the example in FIG. 3 as 4-entry pattern pruning, since every kernel reserves 4 non-zero weights out of the original 3×3 kernel …”), thereby reducing memory usage relative to the conventional filter (¶¶45-46, “DNN model compression has been proposed for simultaneously reducing the storage/computation and accelerating inference”, ¶103, “ FKW uses five arrays to represent this DNN layer: offset array, reorder array, index array, stride array, and weight array … the weight array stores actual weights”, ¶132, “our pattern-based pruning leads to fewer computations and fewer memory accesses thus reducing the memory bandwidth pressure”).
Wang does not explicitly teach wherein pruning the filter based, at least in part, on the pruning criteria comprises comparing weight values of the filter with a threshold, and setting weight values that are less than the threshold to zero, and wherein the threshold is determined based on the sparsity value of the filter.
Biswas teach wherein computing the tag identifier associated with the filter comprises pruning the filter based, at least in part, on the pruning criteria (¶139, “Pruning may be performed in accordance with pruning control information. The pruning control information governs (determines) the sensitivity of the pruning, such as the number or ratio of the weight coefficients that are pruned (zeroed)”, ¶146, “In general, pruning may involve using an algorithm to decide which weights in a network (e.g., generative neural network) contribute the least to the accuracy of that model, and effectively set those weights to zero”, ¶49), wherein pruning the filter based, at least in part, on the pruning criteria comprises comparing weight values of the filter with a threshold, and setting weight values that are less than the threshold to zero (¶145, “the pruning includes zeroing one or more weights (weight coefficients) based on the set of sensitivity parameters. Weights, as stated above, correspond to or may be said to be the filter coefficients of the one or more filters in each layer of the encoder stage and the decoder stage of the generative neural network. In this context, a sensitivity parameter may be a scalar which indicates the percentage of the weights that are to be pruned (e.g., in terms/units) of standard deviations for the distribution of the weights), or may indicate thresholds below which the weights are to be set to zero (i.e., weights below the threshold may be set to zero)”, ¶¶51-52, “ zeroing (zeroing out, setting to zero) one or more weight coefficients based on the pruning control information”), and wherein the threshold is determined based on the sparsity value of the filter (¶139, “Each sensitivity parameter may set a ratio of weight coefficients that is to be pruned for the respective convolutional layer. Alternatively, each sensitivity parameter may set a respective threshold for pruning”, ¶147, “The set of sensitivity parameters may be chosen such that an increase in sparsity of the bottleneck layer is less than the increase in sparsity of either of the one or more pruned layers of the encoder stage and/or the decoder stage”, ¶148, “sensitivity parameter of the bottleneck layer may be selected in such a way that the bottleneck layer is made less sparse than the neighboring”, ¶156, “An example of a possible sparsity profile that indicates a sparsity as a function of layer number is indicated in FIG. 3B. This graph shows the percentage of zeroed-out (or zero valued) weights for each layer of the generative neural network … In general, the aforementioned percentage of zero valued weights (or sparsity) may be greater than a certain threshold value (sparsity threshold value)”, sparsity is the percentage of zero-valued weights and the set of sensitivity parameters are chosen based on a desired sparsity profile; the same sensitivity parameters also indicate threshold below which weights are set to zero, therefore the threshold is determined based on the sparsity value).
Wang and Biswas are analogous art to the claimed invention because they are from a similar field of endeavor of compressing Neural networks. Thus, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify Wang resulting in resolutions as disclosed by Biswas with a reasonable expectation of success.
One of ordinary skill in the art would be motivated to modify Wang as described above to reduce memory usage and computational complexity of deep learning processing without deteriorating performance (Biswas, ¶11).
Wang teach looking up a table by disclosing a pattern candidate set formed from the positions of the retained non-zero weights (¶¶70-71) from which a pattern is selected (¶78). Wang refers to this structure as a “pattern set” rather than a table, the terminology is different but the structure is the same. Therefore, in effort to expedite persecution, Frumkin explicitly disclose the limitation.
Frumkin teach performing a lookup of the plurality of enumerations in a table (¶86, “Another approach is to provide a look up table, which exploits the fact that there are a limited number of possible 2D structured-sparse patterns for a given block. For example, there are only 90 possible 2D 2:4 4×4 blocks, for which transposition information can be stored in a look up table”);
computing (706), by the processor (206), a tag identifier (316) associated with the filter based, at least in part, on the enumeration, the tag identifier (316) having a single index indicating spatial locations of non-zero layer parameters in the filter; and storing (708), by the processor (206), the tag identifier (316) and the non-zero layer parameters for the filter of the trained neural network (112) in a database (204) for inference (¶47, “compressor 10 receives a sparse matrix array 104 and generates a compressed data file 102 in a diagonal storage format. The diagonal storage format in one example embodiment includes a mask and a stream of non-zero values in diagonal order. The mask provides data for determining location of non-zero values in the decompressed data (e.g., original sparse matrix array or a transposed sparse matrix array). In one example, the mask may be a bitmask with ones (or zeros) indicating location of non-zero values in the sparse matrix array”, ¶71, “Once the DNN is trained, the DNN can be deployed and used to identify and classify objects or patterns in a process known as inference”, ¶75, claim 5, “wherein the mask includes a bitmask indicating location of each non-zero value in the sparse matrix”, Claim 6, ¶83, ¶124),
computing, by the processor (206), an output of the neural network for an inference data by applying the filter using the non-zero layer parameters identified by the tag identifier (¶47, “compressor 10 receives a sparse matrix array 104 and generates a compressed data file 102 in a diagonal storage format. The diagonal storage format in one example embodiment includes a mask and a stream of non-zero values in diagonal order. The mask provides data for determining location of non-zero values in the decompressed data (e.g., original sparse matrix array or a transposed sparse matrix array). In one example, the mask may be a bitmask with ones (or zeros) indicating location of non-zero values in the sparse matrix array”, ¶71, “Once the DNN is trained, the DNN can be deployed and used to identify and classify objects or patterns in a process known as inference”, ¶75, claim 5, “wherein the mask includes a bitmask indicating location of each non-zero value in the sparse matrix”, Claim 6, ¶83, ¶124¶11, “indices of nonzero elements may be provided in a map such as a bitmap indicating location of nonzero elements”, ¶13, “mask indicating sparse matrix locations of the non-zero values”, “ The mask provides data for determining location of non-zero values”), the application of the filter corresponding to the tag identifier utilizing a reduced number of computations as compared to a conventional filter (¶63, “matrix data is compressed and decompressed at various stages to reduce system storage and/or communication resources, and increase computation speeds”, ¶76, “when storing and performing operations using sparse matrices, specialized data representations can be used to exploit the sparsity of the matrices to reduce storage requirements and memory latency”, ¶78, “diagonal storage needs only one copy of non-zeroes and of the mask”, ¶80, ¶136, “may be configured to perform the operations by directly using the array and indexing data, without decompressing the data to generate the original matrix, compacted matrix, transposed matrix, and/or transposed and compacted matrix”).
Wang-Biswas and Frumkin are analogous art to the claimed invention because they are from a similar field of endeavor of compressing Neural networks. Thus, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify Wang-Biswas resulting in resolutions as disclosed by Frumkin with a reasonable expectation of success.
One of ordinary skill in the art would be motivated to modify Wang-Biswas as described above for efficient on demand data decompression and save resources by facilitating looking up data and saving memory (Frumkin ¶3, “ reduce memory and transmission latency” ¶10, “it may take much longer to unpack a highly compressed sparse matrix data file as compared with one that is not as compressed. With increases in data sizes and analytical demands, solutions are needed for efficient on demand data decompression”).
With regard to Claim 2,
Wang-Biswas-Frumkin teach the computer-implemented method (700) as claimed in claim 1, wherein the layer parameters are weights of the filter (Wang, ¶59, “Kernel Pattern Pruning is illustrated in FIG. 3. For each kernel (in a CONV filter), a fixed number of weights are pruned, and the remaining weights (white cells) form specific “kernel patterns”. We define the example in FIG. 3 as 4-entry pattern pruning, since every kernel reserves 4 non-zero weights out of the original 3×3 kernel (the most commonly used kernel). The same approach is also applicable to other kernel sizes and the FC layer. For each kernel, it possesses flexibility in choosing among a number of pre-defined patterns” ¶45, “Two important categories of DNN model compression techniques are weight pruning [8, 12, 15, 19, 42, 54] and weight quantization”, ¶46, “Weight pruning … two main approaches of weight pruning are (1) the general and non-structured pruning; and (2) structured pruning, which produces irregular and regular compressed DNN models”, Frumkin ¶47, “compressor 10 receives a sparse matrix array 104 and generates a compressed data file 102 in a diagonal storage format. The diagonal storage format in one example embodiment includes a mask and a stream of non-zero values in diagonal order. The mask provides data for determining location of non-zero values in the decompressed data (e.g., original sparse matrix array or a transposed sparse matrix array). In one example, the mask may be a bitmask with ones (or zeros) indicating location of non-zero values in the sparse matrix array”).
The same motivation to combine for claim 1 equally applies for current claim.
With regard to Claim 3,
Wang-Biswas-Frumkin teach the computer-implemented method (700) as claimed in claim 1, wherein the trained neural network (112) is a convolutional neural network, and wherein the filter is a convolutional filter (Wang, ¶59, “Kernel Pattern Pruning is illustrated in FIG. 3. For each kernel (in a CONV filter), a fixed number of weights are pruned, and the remaining weights (white cells) form specific “kernel patterns”. We define the example in FIG. 3 as 4-entry pattern pruning, since every kernel reserves 4 non-zero weights out of the original 3×3 kernel (the most commonly used kernel). The same approach is also applicable to other kernel sizes and the FC layer. For each kernel, it possesses flexibility in choosing among a number of pre-defined patterns”, ¶86).
The same motivation to combine for claim 1 equally applies for current claim.
With regard to Claim 4,
Wang-Biswas-Frumkin teach the computer-implemented method (700) as claimed in claim 1, wherein the filter is pruned to obtain a sparse weight matrix comprising zero and non-zero elements (Wang, ¶59, “Kernel Pattern Pruning is illustrated in FIG. 3. For each kernel (in a CONV filter), a fixed number of weights are pruned, and the remaining weights (white cells) form specific “kernel patterns”. We define the example in FIG. 3 as 4-entry pattern pruning, since every kernel reserves 4 non-zero weights out of the original 3×3 kernel”, ¶¶77-80, “each kernel in X needs to satisfy one specific pattern shape in the pattern set (and non-zero weight values can be arbitrary)”, ¶81, “for connectivity pruning, the projection is: keeping αk kernels with largest L2 norms and setting the rest of kernels to zero”, ¶¶46-47), and wherein computing the tag identifier (316) associated with the filter further comprises:
determining, by the processor (206), the tag identifier (316) associated with the filter based on the sparse weight matrix, the tag identifier (316) indicating spatial locations of the non-zero elements of the sparse weight matrix (Wang, ¶59, “For each kernel (in a CONV filter), a fixed number of weights are pruned, and the remaining weights (white cells) form specific “kernel patterns”. We define the example in FIG. 3 as 4-entry pattern pruning, since every kernel reserves 4 non-zero weights out of the original 3×3 kernel …”, ¶77, “each kernel in X needs to satisfy one specific pattern shape in the pattern set (and non-zero weight values can be arbitrary)”, ¶¶78-79, “… We assign an appropriate pattern for each kernel based on the L2-norm metric in each iteration, to achieve higher flexibility”, ¶92, “pattern types presented in this layer, the pattern order in each filter, the connection between kernels and input/output channels”, Frumkin ¶47, “compressor 10 receives a sparse matrix array 104 and generates a compressed data file 102 in a diagonal storage format. The diagonal storage format in one example embodiment includes a mask and a stream of non-zero values in diagonal order. The mask provides data for determining location of non-zero values in the decompressed data (e.g., original sparse matrix array or a transposed sparse matrix array). In one example, the mask may be a bitmask with ones (or zeros) indicating location of non-zero values in the sparse matrix array”, ¶71, “Once the DNN is trained, the DNN can be deployed and used to identify and classify objects or patterns in a process known as inference”, ¶83, ¶75, claim 5, “wherein the mask includes a bitmask indicating location of each non-zero value in the sparse matrix”, Claim 6, ¶¶130-131, “The indexing data provides information needed to specify and/or determine, for each nonzero value, where the nonzero value is positioned in the (1) matrix, (2) compacted matrix, (3) the transformed matrix, and/or (4) the transposed compacted matrix”, ¶228, “Bit-mask nnz_mask is generated with ones representing locations of the non-zero elements and zeros representing zero valued elements in the matrix”).
The same motivation to combine for claim 1 equally applies for current claim.
With regard to Claim 5,
Wang-Biswas-Frumkin teach the computer-implemented method (700) as claimed in claim 4, wherein computing the values of the layer parameters for the filter comprises:
receiving, by the processor (206), the sparsity value for the filter, wherein the sparsity value indicates a number of zero values of the layer parameters in the filter (Wang, ¶92, “A key feature of PatDNN is its sparsity- and pruning-aware design. To support it, PatDNN provides a high-level fine-grained Layerwise Representation (LR) to capture the sparsity information. This LR includes intensive DNN layer specific information to enable aggressive layerwise optimizations”, ¶46, “Weight pruning reduces the redundancy in the number of weights. As shown in FIG. 2, two main approaches of weight pruning are (1) the general and non-structured pruning; and (2) structured pruning, which produces irregular and regular compressed DNN models”, ¶60, Frumkin, ¶47, “compressor 10 receives a sparse matrix array 104 and generates a compressed data file 102 in a diagonal storage format. The diagonal storage format in one example embodiment includes a mask and a stream of non-zero values in diagonal order. The mask provides data for determining location of non-zero values in the decompressed data (e.g., original sparse matrix array or a transposed sparse matrix array). In one example, the mask may be a bitmask with ones (or zeros) indicating location of non-zero values in the sparse matrix array”); and
adapting, by the processor (206), one or more values of the layer parameters of the filter based, at least in part on, a corresponding sparsity value and the pruning criteria to generate the sparse weight matrix (Wang, ¶77, “In kernel pattern pruning, the constraint in the k-th CONV layer is Wk∈Sk:={X|each kernel in X needs to satisfy one specific pattern shape in the pattern set (and non-zero weight values can be arbitrary)”, ¶78, “ADMM-based solution is an iterative process, starting from a pre-trained DNN model. We assign an appropriate pattern for each kernel based on the L2-norm metric in each iteration, to achieve higher flexibility”, ¶46, “Weight pruning reduces the redundancy in the number of weights. As shown in FIG. 2, two main approaches of weight pruning are (1) the general and non-structured pruning; and (2) structured pruning, which produces irregular and regular compressed DNN models”, ¶47, “Kernel Pattern Pruning is illustrated in FIG. 3. For each kernel (in a CONV filter), a fixed number of weights are pruned, and the remaining weights (white cells) form specific “kernel patterns”. We define the example in FIG. 3 as 4-entry pattern pruning, since every kernel reserves 4 non-zero weights out of the original 3×3 kernel (the most commonly used kernel). The same approach is also applicable to other kernel sizes and the FC layer. For each kernel, it possesses flexibility in choosing among a number of pre-defined patterns”, Frumkin, ¶124, “approaches disclosed in this application are not limited to structured sparsity or any particular block size. The approaches can work with 2:8 sparsity, 4:16 sparsity, 8:16 sparsity, or even general 25% or 50% density without a structure. In some embodiments, interaction with sparse Matrix Multiply Accumulate may require a compliant sparsity pattern”).
The same motivation to combine for claim 1 equally applies for current claim.
With regard to Claim 6,
Wang-Biswas-Frumkin teach the computer-implemented method (700) as claimed in claim 4, wherein computing the tag identifier (316) further comprises: identifying, by the processor (206), a structure associated with the sparse weight matrix after pruning (Wang, ¶46, “Weight pruning reduces the redundancy in the number of weights. As shown in FIG. 2, two main approaches of weight pruning are (1) the general and non-structured pruning; and (2) structured pruning, which produces irregular and regular compressed DNN models”, structure exist after pruning, ¶59, “Kernel Pattern Pruning is illustrated in FIG. 3. For each kernel (in a CONV filter), a fixed number of weights are pruned, and the remaining weights (white cells) form specific “kernel patterns”. We define the example in FIG. 3 as 4-entry pattern pruning, since every kernel reserves 4 non-zero weights out of the original 3×3 kernel (the most commonly used kernel). The same approach is also applicable to other kernel sizes and the FC layer. For each kernel, it possesses flexibility in choosing among a number of pre-defined patterns”, Frumkin ¶47, “compressor 10 receives a sparse matrix array 104 and generates a compressed data file 102 in a diagonal storage format. The diagonal storage format in one example embodiment includes a mask and a stream of non-zero values in diagonal order. The mask provides data for determining location of non-zero values in the decompressed data (e.g., original sparse matrix array or a transposed sparse matrix array). In one example, the mask may be a bitmask with ones (or zeros) indicating location of non-zero values in the sparse matrix array”);
determining, by the processor (206), the enumeration, based at least in part, on the identified structure (Wang, ¶59, “Kernel Pattern Pruning is illustrated in FIG. 3. For each kernel (in a CONV filter), a fixed number of weights are pruned, and the remaining weights (white cells) form specific “kernel patterns”. We define the example in FIG. 3 as 4-entry pattern pruning, since every kernel reserves 4 non-zero weights out of the original 3×3 kernel (the most commonly used kernel). The same approach is also applicable to other kernel sizes and the FC layer. For each kernel, it possesses flexibility in choosing among a number of pre-defined patterns”, ¶71, “Suppose we aim at k different patterns in the candidate set. We count and select the Top-k most commonly appeared natural patterns across all kernels in the DNN, thereby forming the pattern candidate set (to select from in the subsequent step)”, Frumkin, ¶124, “approaches disclosed in this application are not limited to structured sparsity or any particular block size. The approaches can work with 2:8 sparsity, 4:16 sparsity, 8:16 sparsity, or even general 25% or 50% density without a structure. In some embodiments, interaction with sparse Matrix Multiply Accumulate may require a compliant sparsity pattern”, ¶83, “For an 2D N:M structured sparse matrix (where each column and row of M elements has only N nonzero values), it is desirable to store a single version of the compacted matrix using M*N storage space (plus metadata), but to be able to generate simply from this storage both the compacted+transposed and compacted+non-transposed version of the matrix. Along with appropriate metadata (either generated or stored), these versions of the matrix can be fed directly to sparse matrix multiply-accumulate (MMA) instructions”, sparsity must be selected , this show enumeration among allowable format for sparse MMA); and
assigning, by the processor (206), the tag identifier (316) for the filter, based at least in part, on the enumeration, wherein the tag identifier (316) is indicative of weight values of the filter that are to be multiplied with an input data of the filter (Wang, ¶59, “Kernel Pattern Pruning is illustrated in FIG. 3. For each kernel (in a CONV filter), a fixed number of weights are pruned, and the remaining weights (white cells) form specific “kernel patterns”. We define the example in FIG. 3 as 4-entry pattern pruning, since every kernel reserves 4 non-zero weights out of the original 3×3 kernel (the most commonly used kernel). The same approach is also applicable to other kernel sizes and the FC layer. For each kernel, it possesses flexibility in choosing among a number of pre-defined patterns”, Frumkin, ¶124, “approaches disclosed in this application are not limited to structured sparsity or any particular block size. The approaches can work with 2:8 sparsity, 4:16 sparsity, 8:16 sparsity, or even general 25% or 50% density without a structure. In some embodiments, interaction with sparse Matrix Multiply Accumulate may require a compliant sparsity pattern”, ¶83, “For an 2D N:M structured sparse matrix (where each column and row of M elements has only N nonzero values), it is desirable to store a single version of the compacted matrix using M*N storage space (plus metadata), but to be able to generate simply from this storage both the compacted+transposed and compacted+non-transposed version of the matrix. Along with appropriate metadata (either generated or stored), these versions of the matrix can be fed directly to sparse matrix multiply-accumulate (MMA) instructions”, ¶¶190-192, “matrix multiply and accumulate (MMA) operation can be defined by C+=A*B”, ¶193, “ result matrix C may be added to matrices multiplied in the next MMA operation”).
The same motivation to combine for claim 1 equally applies for current claim.
With regard to Claim 7,
Wang-Biswas-Frumkin teach the computer-implemented method (700) as claimed in claim 4, wherein computing the tag identifier (316) further comprises:
receiving, by the processor (206), an enumeration preference for the filter (Wand, ¶¶59-60, Wand, ¶¶59-60, ADMM-based optimization framework is used to select kernel pruning patterns aligned with biological connections structure and optimized for accuracy. The selected patterns, each is associated with pattern ID, and used by the compiler to reorder and group kernels to maximize instruction-level parallelism during inference, ¶46); and
determining, by the processor (206), a subset of enumerations among a plurality of enumerations based, at least in part, on the enumeration preference and the pruning criteria for the filter (Wand, ¶71, “the number of patterns is determined and 4-entry patterns are utilized, the compiler optimization and hard-ware efficiency are oblivious to the specific pattern shapes. However, the specific patterns to use need to be carefully optimized to maintain high accuracy after kernel pattern pruning. The key insights of pattern design are: (1) both theory and empirical studies [58, 59] show that the central weight in a 3×3 kernel is critical and shall not be pruned; and (2) it is desirable that the distortion is small for each kernel before and after kernel pattern pruning. Hence, we propose the following heuristic. First, for the pre-trained DNN, we scan all the kernels, and for each kernel, we find the four weights with largest magnitudes (including the central weight). These four weights form a 4-entry pattern, called the natural pattern of the kernel. According to the definition of natural patterns, there are a total of (8 3)=56 number of possible patterns. Suppose we aim at k different patterns in the candidate set. We count and select the Top-k most commonly appeared natural patterns across all kernels in the DNN, thereby forming the pattern candidate set (to select from in the subsequent step)”, ¶¶59-60, ¶46, ¶¶77-78, “ADMM-NN [49], in that it is flexible to select a pattern for each kernel from the pattern set. As long as a pattern is assigned for each kernel, constraints in problem (1) become clustering-like and ADMM compatible. Similar to ADMM-NN [49], the ADMM-based solution is an iterative process, starting from a pre-trained DNN model. We assign an appropriate pattern for each kernel based on the L2-norm metric in each iteration, to achieve higher flexibility”).
The same motivation to combine for claim 1 equally applies for current claim.
With regard to Claim 9,
Wang-Biswas-Frumkin teach the computer-implemented method (700) as claimed in claim 1, further comprising: generating, by the processor (206), a filter function for the filter associated with the neural layer of the trained neural network (112) to be used in an inference phase, wherein the filter function is based, at least in part, on the tag identifier (316),the values of the layer parameters of the filter and an input variable; and storing, by the processor (206), the filter function for the filter in the database (204) (¶¶59-60, kernel pruning patterns are selected using an ADMM-based optimization framework that consider biological connections structure and accuracy, predefined patterns enable compiler-level reordering and grouping of kernels with same pattern ID to maximize instruction-level parallelism during inference, ¶94, “code optimization does not require any loop control-flows. This is guaranteed by our filter kernel reorder”, TAG ID control access and usage of sparse weights, ¶71, “When the number of patterns is determined and 4-entry patterns are utilized, the compiler optimization (filter function is generated) and hard-ware efficiency are oblivious to the specific pattern shapes. However, the specific patterns to use need to be carefully optimized to maintain high accuracy after kernel pattern pruning …”, ¶72, “our approach focuses on system-level design and compiler optimization (filter function stored and reused)of the pattern-based acceleration framework (pattern code generated and used in inference)”, each kernel pattern shape is assigned a unique pattern ID that identified the spatial arrangement of non-zero weights (i.e. tag identifier)).
The same motivation to combine for claim 1 equally applies for current claim.
With regard to Claim 10,
Wang-Biswas-Frumkin teach the computer-implemented method (700) as claimed in claim 9, wherein the tag identifier (316), the values of the layer parameters and the filter function associated with the filter of the neural layer are used to perform the inference on an inference data (¶¶59-60, kernel pruning patterns are selected using an ADMM-based optimization framework that consider biological connections structure and accuracy, predefined patterns enable compiler-level reordering and grouping of kernels with same pattern ID to maximize instruction-level parallelism during inference, ¶71, “When the number of patterns is determined and 4-entry patterns are utilized, the compiler optimization (filter function is generated) and hard-ware efficiency are oblivious to the specific pattern shapes. However, the specific patterns to use need to be carefully optimized to maintain high accuracy after kernel pattern pruning …”, ¶72, “our approach focuses on system-level design and compiler optimization (filter function stored and reused) of the pattern-based acceleration framework (pattern code generated and used in inference)”, each kernel pattern shape is assigned a unique pattern ID that identified the spatial arrangement of non-zero weights (i.e. tag identifier)). In other words, during inference the tag ID (i.e. pattern ID assigned to each kernel pattern shape), the values of the layer parameters (i.e. non-zero weights remaining after kernel pruning), and the compiler generated filter function (optimized for specific pattern) are jointly used to execute the filter on inference data).
The same motivation to combine for claim 1 equally applies for current claim.
Claim 8 is rejected under 35 U.S.C. 103 as being unpatentable over Wang et al. [US 2021/0256384 A1, hereinafter Wang] in view of Biswas et al. [US 2023/0229892 A1, hereinafter Biswas] in view of Frumkin et al. [US 2020/0342632 A1, hereinafter Frumkin] in view of “Compression of Deep Neural Networks by Combining Pruning and Low Rank Decomposition” published on 29/7/2019 [hereinafter D1].
With regard to Claim 8,
Wang-Biswas-Frumkin teach the computer-implemented method (700) as claimed in claim 1. The same motivation to combine for claim 1 equally applies for current claim.
Wang-Biswas-Frumkin does not explicitly teach wherein computing values of the layer parameters for the filter further comprises using one or more filter decomposition techniques on the filter with higher order filter dimensions to prune the trained neural network (112).
D1 teach wherein computing values of the layer parameters for the filter further comprises using one or more filter decomposition techniques on the filter with higher order filter dimensions to prune the trained neural network (112) (Abstract, “Large number of weights in deep neural networks make the models difficult to be deployed in low memory environments such as, mobile phones, IOT edge devices as well as “inferencing as a service" environments on the cloud … In this paper, we demonstrate the use of multiple techniques to achieve not only higher model compression but also reduce the compute resources required during inferencing. We do filter pruning followed by low-rank decomposition using Tucker decomposition for model compression”, P. 953, Col. 1, ¶¶2-3, “Thus, in our work we combine two compression mechanisms where one is dependent on the data being trained (filter pruning), while the other (low rank decomposition) is independent of the data once the model is transfer learnt“, P. 953, Col. 2, ¶1, “For CNNs, the convolution layer is a 4D Tensor of size F D h w (the first 2 dimensions are the output and input of that layer and the remaining 2 dimensions are the spatial dimensions) and maps an input (source) tensor of size X Y D into output (target) tensor of size X0Y 0F. For the simpler case where padding is ‘same’, and stride is one, X0 = X and Y 0 = Y . The rank-(R1;R2;R3;R4) Tucker decomposition of this 4D tensor (along all of its modes) results in a set of 2D-matrices U along each of the dimensions of the tensor (also called modes) and a core tensor G”, P. 953-954, B. Filter Pruning, “Pruning filters from convolution layers is a standard method of compressing the CNNs [26]. The parameters of a convolution layer can be pruned in a finer manner by removing individual connections as in Weight Pruning [14] or a coarser manner by removing the entire node of that layer as in Filter Pruning . In this paper, we have used filter pruning for model compression. There are several methods of removing filter from CNNs based on their importance. As discussed in [26], these heuristics include the combined `2-norm of the kernel weights, the mean, standard deviation or percentage of the feature map’s activation, and mutual information between activations and predictions. In our work, we remove the filters by minimizing the Taylor series expansion of the error introduced by removing a filter as it yields better results. A threshold parameter provides a tradeoff between space and accuracy by controlling the number of filters to be pruned. Note that for two successive convolution operations, the removal of a filter for the first convolution leads to removal of the corresponding kernel in the next convolution).
Wang-Biswas-Frumkin and D1 are analogous art to the claimed invention because they are from a similar field of endeavor of compressing Neural networks. Thus, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify Wang-Biswas-Frumkin resulting in resolutions as disclosed by D1 with a reasonable expectation of success.
One of ordinary skill in the art would be motivated to modify Wang-Biswas-Frumkin as described above to achieve not only higher model compression but also reduce the compute resources required during inferencing which allow the deployment of models in low memory environments such as, mobile phones, IOT edge devices as well as “inferencing as a service" environments on the cloud (D1, Abstract).
Response to Arguments
Applicant’s argue that Wang does not disclose determining an enumeration by performing a lookup of enumerations in a table based on the indices of non-zero values of the layer parameters of a filter. More particularly, in Wang, the top-k pattern selection is used to form a limited candidate set of kernel pruning patterns. Wang first identifies possible/natural kernel patterns and then selects a small number of frequently occurring patterns as a pre-defined pattern set. However, Wang's Top-k pattern selection is not based on performing a lookup of enumerations in a table using indices of non-zero layer parameters of a particular filter. Rather, Wang selects frequently occurring pruning patterns to define a reduced pattern candidate set, and then uses that candidate set during pruning. Therefore, Wang fails to teach or suggest the above-mentioned features as recited in amended independent claim 1. Biswas and Frumkin are neither contended to nor do they cure the deficiencies of Wang in the rejection of amended independent claim 1.
Examiner respectfully disagrees, applicant asserts that Wang Top-K pattern selection is not based on performing a lookup of an enumeration in a table using indices of non-zero layer parameters. The claim does not recite using it recites “performing a lookup of the plurality of enumerations in a table based on indices of non-zero layer parameters of the filter”. The claim identifies what is looked up (of the plurality of enumerations) and where the lookup occurs (“in a table”) before the disputed phrase. The claim language require looking up “of an enumeration” within a table that is generated based on indices of non-zero layer parameters of the filter. In other words applicant claim does not recite any lookup key, or recite a lookup key, or that indices are stored in the table, and does not recite that the indices address the table. Wang expressly drives its pattern set from the positions of the non-zero weights. At ¶71, the pretrained DNN, Wang scans all kernels and for each kernel finds the four weights with the largest magnitudes including the central weight. Wang states that “the four weights from a 4 entry patterns, called the natural pattern of the kernel.” A natural pattern is constituted by nothing other than which four of the nine positions of the 3X3 kernel hold the retained weights, which is why Wang computes 56 of possible patterns. Wang counts the natural patterns and select the top-k, ¶71 “thereby forming the pattern candidate set “, “design each specific candidate pattern in the pattern set”, ¶70. The derivation is unbroken: positions of the non-zero weights - > natural patterns - > candidate set. The arguments does not address ¶78 where Wang states, “it is flexible to select a pattern for each kernel from the pattern set”, “ We assign an appropriate pattern for each kernel based on the L2-norm metric in each iteration”. Applicant acknowledge and disclose that Wang disclose “selecting from a predefined pattern set” . The claim recite that the table is “based on” the indices, not that it is based on those of one filter. Wang derives its natural pattern from the retained weight positions of every kernel, and each CONV filter comprises a plurality of kernels (¶97, “The kernels in the same row belong to the same filter”) and discloses a per filter structure holding the enumerations “a matrix represents a CONV layer of DNN and each cell is a kernel with pattern type denoted by the number on it”, with pattern order in each filter carried in the Layerwise Representation (¶92). In response to applicant's argument that the references fail to show certain features of the invention, it is noted that the features upon which applicant relies (i.e., an enumeration in a table using indices of non-zero layer parameters) are not recited in the rejected claim(s). Although the claims are interpreted in light of the specification, limitations from the specification are not read into the claims. See In re Van Geuns, 988 F.2d 1181, 26 USPQ2d 1057 (Fed. Cir. 1993). Further, examiner notes that Frumkin teach performing a lookup of the plurality of enumerations in a table (¶86, “Another approach is to provide a look up table, which exploits the fact that there are a limited number of possible 2D structured-sparse patterns for a given block. For example, there are only 90 possible 2D 2:4 4×4 blocks, for which transposition information can be stored in a look up table”).
Applicant’s argue that Wang fails to teach or suggest utilizing the pattern ID as the claimed tag identifier that identifies spatial locations of non-zero layer parameters for a particular filter and causes the processor to apply only those non-zero layer parameters to corresponding spatial locations of inference data. Biswas also does not teach the claimed feature. Accordingly, Wang, Biswas, and Frumkin, alone or in combination, fail to teach or suggest the above-mentioned features of amended independent claim 1.
Examiner respectfully disagrees, applicant’s argument rely on limitations that are not part of the claim. The claim does not require applying “only” non-zero layer parameters, a “particular” filter, and does not require mapping those parameters to spatial location of inference data. The claim require applying the filter to inference data based on the spatial location of non-zero layer parameter and Wang disclose these requirements explicitly See at least ¶71, “we scan all the kernels, and for each kernel, we find the four weights with largest magnitudes (including the central weight). These four weights form a 4-entry pattern, called the natural pattern of the kernel. According to the definition of natural patterns, there are a total of (8 3)=56 number of possible patterns”, ¶107, “In DNN execution, such as a convolution operation, the data access pattern of the input and output is decided by the (none-zero elements) patterns of kernels that are already known after training. Therefore, it is possible to generate the optimized data access code with this information for each pattern of kernels and call them dynamically during the DNN execution. … the index of input data can be directly calculated from kernel pattern.”. In response to applicant's argument that the references fail to show certain features of the invention, it is noted that the features upon which applicant relies (i.e., applying “only” non-zero layer parameters, a “particular” filter, and mapping those parameters to spatial location of inference data) are not recited in the rejected claim(s). Although the claims are interpreted in light of the specification, limitations from the specification are not read into the claims. See In re Van Geuns, 988 F.2d 1181, 26 USPQ2d 1057 (Fed. Cir. 1993).
As to the remaining dependent claims, applicant argue that they are allowable due to their respective direct and indirect dependencies upon one of the aforementioned Independent claims. The examiner respectfully disagrees, Independent claims were not allowable as stated in the paragraph above in this “Response to Arguments” section in this office action.
Conclusion
The prior art made of record and not relied upon is considered pertinent to the applicant’s disclosure.
US Patent Application Publication No. 20220076095 filed by Qin et al. that disclose providing a single, multi-level sparse neural network that can provide multiple sparse neural networks with multiple sparsity levels. The multi-level sparse neural network can use a hierarchical structure to store parameters (e.g., matrix weights) for the multiple sparse neural networks with multiple sparsity levels such that parameters (e.g., locations and values of non-zero matrix elements) of a more-sparse model (e.g., a “tiny” model) are a subset of parameters (e.g., locations and values of non-zero matrix elements) a less-sparse model (e.g., a “small” model). In accordance with the hierarchical structure, parameters (e.g., non-zero matrix weights) and hyper parameters (e.g., biases, weights related to batch normalization, running means, or running variances) of the multiple sparse neural networks can be decoded from the single, multi-level sparse neural network. By doing so, the storage cost can be capped by the least sparse (or the most dense) model. See at least ¶25
Examiner has pointed out particular references contained in the prior arts of record in the body of this action for the convenience of the applicant. Although the specified citations are representative of the teachings in the art and are applied to the specific limitations within the individual claim, other passages and Figures may apply as well. It is respectfully requested from the applicant, in preparing the response, to consider fully the entire references as potentially teaching all or part of the claimed invention, as well as the context of the passage as taught by the prior arts or disclosed by the examiner. It is noted that any citation to specific pages, columns, figures, or lines in the prior art references any interpretation of the references should not be considered to be limiting in any way. A reference is relevant for all it contains and may be relied upon for all that it would have reasonably suggested to one having ordinary skill in the art. In re Heck, 699 F.2d 1331-33, 216 USPQ 1038-39 (Fed. Cir. 1983) (quoting In re Lemelson, 397 F.2d 1006, 1009, 158 USPQ 275, 277 (CCPA 1968)).
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MOHAMED ABOU EL SEOUD whose telephone number is (303)297-4285. The examiner can normally be reached Monday-Thursday 9:00am-6:00pm MT.
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, Michelle Bechtold can be reached at (571) 431-0762. 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.
/MOHAMED ABOU EL SEOUD/Primary Examiner, Art Unit 2148
Prosecution Insights