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 .
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 2026/08/28, 2025/04/07, 2024/11/22 & 2024/05/07. The submission is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
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–14 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (an abstract idea) without reciting significantly more.
Regarding independent claims 1, 13, and 14
Step 1 -- whether the claim falls within any statutory category. See MPEP 2106.03.
Independent claim 1 is drawn to an information processing device comprising a processor and a memory. Independent claim 13 is drawn to a non-transitory computer-readable storage medium. Independent claim 14 is drawn to an information processing method. Therefore, claims 1, 13, and 14 each fall under at least one of the four categories of statutory subject matter: claim 1 as a machine, claim 13 as a manufacture, and claim 14 as a process.
Step 2A Prong 1 – whether the claim recites a judicial exception. See MPEP 2106.04, subsection II.
Regarding independent claim 1, the claim is directed to an information processing device that calculates a forward probability of a unit series of a time series being classified into a class, by arranging, shifting, and adding log-likelihoods in matrices.
The limitation of "a log-likelihood matrix in which log-likelihoods are arranged as components in ascending order of lengths of unit series predetermined to divide a time series of a predetermined event and timesteps for combinations of predicted values predicting the event for each length up to a maximum length and variances of the predicted values, the log-likelihoods being obtained by converting likelihoods into logarithms, the likelihoods being probabilities of observation values obtained from the event at the respective timesteps being generated" recites an abstract idea. It describes computing probabilities of observation values from predicted values and variances, converting the probabilities into logarithms, and organizing the resulting values by length and timestep. This limitation falls within the mathematical concepts grouping of abstract ideas, i.e., mathematical relationships and mathematical calculations. See MPEP § 2106.04(a)(2), subsection I.
The limitation of "generating a shifted log-likelihood matrix by performing a shifting process of shifting the log-likelihoods other than log-likelihoods at the top of each line in the log-likelihood matrix in such a manner that the log-likelihoods are aligned along each line in ascending order of the lengths when the lengths and the timesteps are each increased by one unit" recites an abstract idea. It describes re-indexing matrix components by offsets that depend on length and timestep, which is a mathematical operation on a matrix. It falls within the mathematical concepts grouping. See MPEP § 2106.04(a)(2), subsection I.
The limitation of "generating a successive-generation probability matrix by adding the log-likelihoods from the top of each of the lines to the respective components in the shifted log-likelihood matrix, to calculate successive generation probabilities of the respective components" recites an abstract idea. It describes calculating cumulative sums of log-likelihoods to obtain probabilities, which is a mathematical calculation. It falls within the mathematical concepts grouping. See MPEP § 2106.04(a)(2), subsection I.
The limitation of "generating a shifted successive-generation probability matrix by shifting the successive generation probabilities in the successive-generation-probability matrix in such a manner that shift destinations and shift sources of components whose values have been shifted through the shifting process are reversed" recites an abstract idea. It describes the inverse re-indexing of matrix components, a mathematical operation on a matrix. It falls within the mathematical concepts grouping. See MPEP § 2106.04(a)(2), subsection I.
The limitation of "calculating a forward probability of a unit series having a certain length to be classified into a certain class with a certain timestep being an endpoint by using a value obtained by adding the successive generation probabilities up to the respective components in ascending order of the lengths at the respective timesteps in the shifted successive-generation probability matrix" recites an abstract idea. It describes calculating a probability by adding values, which is a mathematical calculation. It falls within the mathematical concepts grouping. See MPEP § 2106.04(a)(2), subsection I.
These limitations recite mathematical calculations in words rather than in formulas. A claim does not need to recite a formula or the word "calculating" to recite a mathematical calculation. See MPEP § 2106.04(a)(2), subsection I, C. The specification confirms that each recited step is a mathematical operation (Spec., p. 19, Eq. (10); p. 21, Eq. (11); p. 23, Eqs. (12)–(13); FIG. 4, steps S11–S15).
Accordingly, independent claim 1 recites an abstract idea under Step 2A Prong 1 because the claim includes limitations falling within the mathematical concepts grouping of abstract ideas. Therefore, the analysis proceeds to Step 2A Prong 2.
Independent claim 13 is a non-transitory computer-readable storage medium claim reciting the same log-likelihood matrix, shifting, adding, reverse-shifting, and forward-probability-calculating limitations as independent claim 1. For the reasons discussed above with respect to independent claim 1, independent claim 13 recites an abstract idea within the mathematical concepts grouping. See MPEP § 2106.04(a)(2), subsection I.
Independent claim 14 is an information processing method claim reciting "using a log-likelihood matrix" and the same shifting, adding, reverse-shifting, and forward-probability-calculating limitations as independent claim 1. The step of "using a log-likelihood matrix" merely recites using the mathematical construct described above in the recited calculations. For the reasons discussed above with respect to independent claim 1, independent claim 14 recites an abstract idea within the mathematical concepts grouping. See MPEP § 2106.04(a)(2), subsection I.
Accordingly, independent claims 1, 13, and 14 recite a judicial exception under Step 2A Prong 1. Therefore, the analysis proceeds to Step 2A Prong 2.
Step 2A Prong 2 -- whether the claim as a whole integrates the recited judicial exception into a practical application of the exception or whether the claim is "directed to" the judicial exception. This evaluation is performed by (1) identifying whether there are any additional elements recited in the claim beyond the judicial exception, and (2) evaluating those additional elements individually and in combination to determine whether the claim as a whole integrates the exception into a practical application. See MPEP 2106.04(d).
Regarding independent claim 1, this claim recites additional elements of:
"a processor to execute a program,"
"a memory to store the program which, when executed by the processor, performs processes of," and
"storing a log-likelihood matrix."
The recited processor and memory are claimed at a high level of generality and merely serve as tools to perform the recited calculations. They amount to no more than mere instructions to apply the judicial exception using generic computer components. See MPEP § 2106.05(f). They also amount to no more than generally linking the use of the judicial exception to a particular technological environment, namely implementation on a computer. See MPEP § 2106.05(h).
The limitation of "storing a log-likelihood matrix" merely retains the data used in the calculations. It is incidental to the recited mathematical operations and is insignificant extra-solution activity. See MPEP § 2106.05(g).
The claim does not reflect an improvement to the functioning of a computer or to another technology or technical field. See MPEP §§ 2106.04(d)(1) and 2106.05(a):
The specification states that the object of the disclosure is "to enable efficient calculation of forward probabilities" (Spec., p. 2). Any efficiency gained comes from rearranging the order of the mathematical operations, which is an improvement to the abstract idea itself, not an improvement to technology. See MPEP § 2106.05(a), subsection II.
Claim 1 does not recite parallel computation or any specific manner of operating the processor or memory.
The specification states that the shifting may be accomplished "by reading reference addresses of a matrix by shifting the reference addresses by a column number without rearrangement in the memory" (Spec., p. 24). The recited shifting is therefore not tied to any particular memory structure or data-storage technique; it is a mathematical re-indexing that may be carried out in any manner.
The claim does not apply the calculated forward probability in any technological process, and it does not recite a particular machine, a transformation of an article, or any other meaningful limitation. See MPEP §§ 2106.05(b), 2106.05(c), and 2106.05(e).
Accordingly, the additional elements, individually and in combination, do not integrate the recited judicial exception into a practical application. Therefore, independent claim 1 is directed to the abstract idea under Step 2A Prong 2.
Regarding independent claim 13, to the extent claim 13 recites limitations overlapping with independent claim 1, those limitations are rejected under 35 U.S.C. § 101 for the same reasons discussed above with respect to claim 1. Claim 13 recites additional elements of:
"a non-transitory computer-readable storage medium storing a program that causes a computer to execute processes," and
"storing a log-likelihood matrix."
The storage medium, program, and computer are recited at a high level of generality and merely provide a generic storage medium and generic computer on which the recited calculations are performed. They amount to no more than mere instructions to apply the judicial exception on a computer. See MPEP § 2106.05(f). They also amount to no more than generally linking the judicial exception to the technological environment of a computer. See MPEP § 2106.05(h). The storing limitation is insignificant extra-solution activity for the reasons discussed above with respect to claim 1. See MPEP § 2106.05(g).
Accordingly, the additional elements, individually and in combination, do not integrate the judicial exception into a practical application. Therefore, independent claim 13 is directed to the abstract idea under Step 2A Prong 2.
Regarding independent claim 14, to the extent claim 14 recites limitations overlapping with independent claim 1, those limitations are rejected under 35 U.S.C. § 101 for the same reasons discussed above with respect to claim 1. Claim 14 recites no additional elements beyond the judicial exception. Each recited step, including "using a log-likelihood matrix," is part of the mathematical concepts identified in Step 2A Prong 1. A claim that recites no additional elements cannot integrate the judicial exception into a practical application. See MPEP § 2106.04(d). Therefore, independent claim 14 is directed to the abstract idea under Step 2A Prong 2.
Step 2B -- whether the claim amounts to significantly more than the judicial exception. See MPEP 2106.05.
Regarding independent claim 1, the additional elements beyond the judicial exception are "a processor to execute a program," "a memory to store the program which, when executed by the processor, performs processes of," and "storing a log-likelihood matrix."
As explained in the Step 2A Prong 2 analysis, the processor and memory are recited at a high level of generality and amount to no more than mere instructions to apply the exception using generic computer components, which cannot provide an inventive concept. See MPEP § 2106.05(f). Using a computer to perform mathematical calculations faster or more efficiently does not provide significantly more. See MPEP § 2106.05(f), subsection II.
The storing limitation was found to be insignificant extra-solution activity in Step 2A Prong 2. Upon reevaluation in Step 2B, it is also well-understood, routine, and conventional activity: storing and retrieving information in memory is recognized as a well-understood, routine, and conventional computer function. See MPEP § 2106.05(d), subsection II (citing Versata Dev. Group, Inc. v. SAP Am., Inc., 793 F.3d 1306, 1334 (Fed. Cir. 2015); OIP Techs., Inc. v. Amazon.com, Inc., 788 F.3d 1359, 1363 (Fed. Cir. 2015)).
Considered individually and in combination, these additional elements do not provide an inventive concept.
Regarding independent claim 13, to the extent claim 13 recites limitations overlapping with claim 1, those limitations do not amount to significantly more than the judicial exception for the same reasons discussed above with respect to claim 1. The additional elements of "a non-transitory computer-readable storage medium storing a program that causes a computer to execute processes" merely recite a generic storage medium and generic computer implementation of the same calculations. They amount to no more than mere instructions to apply the exception on a computer. See MPEP § 2106.05(f). The storing limitation is well-understood, routine, and conventional activity for the reasons discussed above with respect to claim 1. See MPEP § 2106.05(d), subsection II. Considered individually and in combination, the additional elements of claim 13 do not provide an inventive concept.
Regarding independent claim 14, claim 14 recites no additional elements beyond the judicial exception and therefore recites nothing that could amount to significantly more than the judicial exception. See MPEP § 2106.05.
Accordingly, claims 1, 13, and 14 do not recite additional elements, individually or in combination, that amount to significantly more than the recited judicial exception, and are therefore ineligible under 35 U.S.C. § 101.
Regarding dependent claims 2–12
Claims 2–12 merely narrow the previously identified abstract idea limitations of independent claim 1. For the reasons discussed above with respect to independent claims 1, 13, and 14, these judicial exceptions are not meaningfully integrated into a practical application and do not amount to significantly more than the abstract idea. The dependent claims recite additional mathematical relationships and mathematical calculations, and, to the extent they recite additional elements, those elements amount to no more than mere instructions to apply the exception on a generic computer or generally linking the exception to a particular technological environment. Therefore, claims 2–12 also recite abstract ideas that do not integrate into a practical application or amount to significantly more than the judicial exception, and are rejected under 35 U.S.C. § 101.
Step 1 -- whether the claim falls within any statutory category. See MPEP 2106.03.
Claims 2–12 are drawn to an information processing device. Therefore, each of these claims falls under one of the four categories of statutory subject matter (process/method, machine/product/apparatus, manufacture, or composition of matter).
Step 2A Prong 1 – whether the claim recites a judicial exception. See MPEP 2106.04, subsection II.
Regarding claim 2, this claim recites the limitations of "when the lengths are arranged in a row direction and the timesteps are arranged in a column direction in the log-likelihood matrix, the processor shifts the log-likelihoods in each row in a direction in which the timesteps decrease by a column number corresponding to a value obtained by subtracting one from a row number" and "the processor shifts the successive generation probabilities in each row in a direction in which the timesteps increase by the column number corresponding to a value obtained by subtracting one from the row number."
These limitations specify the direction and amount of the re-indexing of matrix components, computed by subtracting one from a row number. They are directed towards the abstract idea of mathematical relationships and mathematical calculations. See MPEP § 2106.04(a)(2), subsection I.
Regarding claim 3, as best understood in view of the rejection under 35 U.S.C. 112(b), this claim recites the limitations of "when the lengths are arranged in a column direction and the timesteps are arranged in a row direction in the log-likelihood matrix, the processor shifts the log-likelihoods in each column in a direction in which the timesteps decrease by a row number corresponding to a value obtained by subtracting one from a column number" and "the processor shifts the successive generation probabilities in each row in a direction in which the timesteps increase by the row number corresponding to a value obtained by subtracting one from the column number."
These limitations specify the direction and amount of the re-indexing of the transposed matrix components. They are directed towards the abstract idea of mathematical relationships and mathematical calculations. See MPEP § 2106.04(a)(2), subsection I.
Regarding claim 4, this claim recites the limitation of "the predicted values are values determined through calculation of Gaussian distribution likelihood."
This limitation is directed towards the abstract idea of a mathematical calculation, namely calculating a likelihood of a Gaussian (normal) probability distribution. See MPEP § 2106.04(a)(2), subsection I.
Regarding claim 5, this claim recites the limitation of "the predicted values are expected values calculated with a blocked Gibbs sampler."
This limitation is directed towards the abstract idea of a mathematical calculation, namely calculating expected values with a statistical sampling algorithm. See MPEP § 2106.04(a)(2), subsection I.
Regarding claim 6, this claim recites the limitation of "the predicted values are predicted with a recurrent neural network with dropouts added to introduce uncertainty."
To the extent this limitation recites predicting values and introducing uncertainty by dropouts, it is directed towards the abstract idea of mathematical calculations. The recited recurrent neural network is evaluated as an additional element in Step 2A Prong 2.
Regarding claims 7–12, these claims recite the limitations of "the processor stores the log-likelihood matrix for each of a plurality of dimensions corresponding to a plurality of classes of the unit series" and "the processor executes processing in parallel in each of the dimensions other than the timesteps."
To the extent these limitations organize the log-likelihood values by class and perform the recited calculations for each class and length, they are directed towards the abstract idea of mathematical relationships and mathematical calculations. See MPEP § 2106.04(a)(2), subsection I. The storing and the parallel execution by the processor are evaluated as additional elements in Step 2A Prong 2. Claims 8–12 further recite the limitations of claims 2–6, respectively, which are directed towards the abstract idea for the reasons stated above for claims 2–6.
Step 2A Prong 2 -- whether the claim as a whole integrates the recited judicial exception into a practical application of the exception or whether the claim is "directed to" the judicial exception. This evaluation is performed by (1) identifying whether there are any additional elements recited in the claim beyond the judicial exception, and (2) evaluating those additional elements individually and in combination to determine whether the claim as a whole integrates the exception into a practical application. See MPEP 2106.04(d).
Regarding claims 2–5, these claims recite the additional element of "the processor."
This limitation amounts to no more than mere instructions to apply the judicial exception using a generic computer component. See MPEP § 2106.05(f). It also amounts to no more than generally linking the use of the judicial exception to a particular technological environment. See MPEP § 2106.05(h). It fails to integrate the exception into a practical application.
Regarding claim 6, this claim recites the additional element of "a recurrent neural network with dropouts added to introduce uncertainty."
The recurrent neural network is recited at a high level of generality and is used to generally apply the abstract idea. The claim places no limits on how the recurrent neural network functions and recites only the outcome of predicting values. It therefore amounts to no more than mere instructions to implement the abstract idea on a generic computer. See MPEP § 2106.05(f); 2024 AI SME Update, Example 47, claim 2, Step 2A Prong 2 ("using the trained ANN"). The recitation also merely confines the abstract idea to a particular technological environment, namely neural networks. See MPEP § 2106.05(h). It fails to integrate the exception into a practical application.
Regarding claims 7–12, these claims recite the additional elements of "the processor stores the log-likelihood matrix for each of a plurality of dimensions corresponding to a plurality of classes of the unit series" and "the processor executes processing in parallel in each of the dimensions other than the timesteps."
The storing limitation merely retains the data used in the calculations and is insignificant extra-solution activity. See MPEP § 2106.05(g).
The parallel-execution limitation is recited at a high level of generality. It requires only that the processor perform the recited calculations simultaneously. It recites no particular processor architecture, memory arrangement, or other details of how the parallel processing is achieved. Using a computer's processing capability to perform calculations simultaneously, and therefore faster, amounts to no more than mere instructions to apply the exception on a generic computer. See MPEP § 2106.05(f), subsection II. It also merely links the exception to a particular technological environment, namely parallel computing. See MPEP § 2106.05(h).
The claims do not reflect an improvement to the functioning of the computer itself, because any efficiency results from the rearrangement of the mathematical operations, which is an improvement to the abstract idea. See MPEP § 2106.05(a), subsection II.
Considered individually and in combination, these additional elements fail to integrate the exception into a practical application. Claims 8–12 recite the additional elements of claims 2–6, respectively, which fail to integrate the exception for the reasons stated above.
Step 2B -- whether the claim amounts to significantly more than the judicial exception. See MPEP 2106.05.
Regarding claims 2–5, the additional element of "the processor" amounts to no more than mere instructions to apply the exception using a generic computer component and cannot provide an inventive concept. See MPEP § 2106.05(f).
Regarding claim 6, the additional element of "a recurrent neural network with dropouts added to introduce uncertainty" is at best mere instructions to apply the abstract idea using a generic neural network, which cannot provide an inventive concept. See MPEP § 2106.05(f); 2024 AI SME Update, Example 47, claim 2, Step 2B. Confining the abstract idea to neural networks also fails to add an inventive concept. See MPEP § 2106.05(h).
Regarding claims 7–12:
The storing limitation is well-understood, routine, and conventional activity. See MPEP § 2106.05(d), subsection II (storing and retrieving information in memory).
The parallel-execution limitation amounts to no more than mere instructions to apply the exception on a generic computer, which cannot provide an inventive concept. See MPEP § 2106.05(f).
Considered individually and in combination, the additional elements of claims 7–12 do not provide an inventive concept.
Accordingly, claims 2–12 do not recite additional elements, individually or in combination, that amount to significantly more than the recited judicial exception, and are therefore ineligible under 35 U.S.C. § 101.
Claim Rejections – 35 U.S.C. § 112
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
The following is a quotation of the first paragraph of pre-AIA 35 U.S.C. 112:
The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor of carrying out his invention.
Claims 3 and 9 are rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, as failing to comply with the written description requirement. The claims contain subject matter which was not described in the specification in such a way as to reasonably convey to one skilled in the relevant art that the inventor or a joint inventor, or for applications subject to pre-AIA 35 U.S.C. 112, the inventor(s), at the time the application was filed, had possession of the claimed invention.
Claim 3 recites that "the processor shifts the log-likelihoods in each column" and that "the processor shifts the successive generation probabilities in each row." The only description of shifting where the lengths and timesteps are arranged in the transposed orientation recites shifting the log-likelihoods "in each row of the log-likelihood matrix D1" and the successive generation probabilities "in each column of the successive-generation probability matrix D3" (Spec., p. 25, first full para.). This is the reverse of the row and column assignments recited in claim 3. The specification and drawings do not otherwise describe shifting the log-likelihoods in each column and the successive generation probabilities in each row. Nor do they describe how a shift in each row could reverse a shift in each column, as required by claim 1. The disclosure therefore does not reasonably convey that the inventors had possession of the subject matter of claim 3. See MPEP § 2163. Claim 9 depends from claim 3 and is rejected for the same reason.
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 3 and 7–12 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 pre-AIA , the applicant) regards as the invention.
(1) Claims 3 and 9
Claim 3 recites "when the lengths are arranged in a column direction and the timesteps are arranged in a row direction in the log-likelihood matrix, the processor shifts the log-likelihoods in each column in a direction in which the timesteps decrease by a row number corresponding to a value obtained by subtracting one from a column number," and further recites "the processor shifts the successive generation probabilities in each row in a direction in which the timesteps increase by the row number corresponding to a value obtained by subtracting one from the column number."
The claim is indefinite for the following reasons:
Under the recited arrangement, the timesteps change along each column and do not change within a row. It is therefore unclear how the successive generation probabilities can be shifted "in each row in a direction in which the timesteps increase."
Claim 1, from which claim 3 depends, requires that the successive generation probabilities be shifted "in such a manner that shift destinations and shift sources of components whose values have been shifted through the shifting process are reversed." A shift "in each row" cannot reverse a shift "in each column." Claim 3 is therefore inconsistent with the limitation it purports to further limit.
The specification does not clarify the intended scope. The only description of this arrangement recites the opposite orientation, "when lengths k are arranged in the row direction and timesteps t are arranged in the column direction in the log-likelihood matrix D1," and recites shifting "in each row of the log-likelihood matrix D1" and "in each column of the successive-generation probability matrix D3" (Spec., p. 25, first full para.). Both are the reverse of the row/column assignments recited in claim 3.
One of ordinary skill in the art therefore cannot determine the metes and bounds of claim 3 (MPEP § 2173.02; In re Packard, 751 F.3d 1307 (Fed. Cir. 2014); MPEP § 2173.03). Claim 9 depends from claim 3, recites the same limitation through that dependency, and fails to cure the deficiency.
For purposes of examination, the recitation of shifting the successive generation probabilities "in each row" is interpreted as shifting them in each column, the same lines along which the log-likelihoods are shifted, consistent with the requirement of claim 1 that the shift destinations and shift sources be reversed.
(2) Claims 7–12
Each of claims 7–12 recites "the processor stores the log-likelihood matrix for each of a plurality of dimensions corresponding to a plurality of classes of the unit series, and the processor executes processing in parallel in each of the dimensions other than the timesteps."
The claims introduce "a plurality of dimensions corresponding to a plurality of classes of the unit series," and then recite parallel processing "in each of the dimensions other than the timesteps." The timesteps are not among the recited plurality of dimensions, which correspond to classes. It is therefore unclear what "the dimensions other than the timesteps" refers to:
only the recited plurality of dimensions corresponding to the classes; or
additional dimensions not previously recited, such as the length dimension of the log-likelihood matrix.
"The dimensions other than the timesteps" also lacks clear antecedent basis in the claims (MPEP § 2173.05(e)). The specification describes parallel computation "for each dimension of the multidimensional array other than the timesteps t," in which the array has class, length, and timestep dimensions (Spec., p. 19, second full para.; p. 23, last para., to p. 24, first para.; FIG. 5). The claims, however, define the "dimensions" as corresponding to classes only. One of ordinary skill in the art therefore cannot determine the scope of the claimed parallel processing.
For purposes of examination, "the dimensions other than the timesteps" is interpreted as the class dimension and the length dimension of the stored log-likelihood matrices, consistent with the specification (Spec., p. 19; FIG. 5).
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.
The text of those sections of Title 35, U.S. Code not included in this action can be found in a prior Office action.
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 1–5, 7–11, 13, and 14 are rejected under 35 U.S.C. 103 as being unpatentable over Nakamura et al. (Nakamura), Non-Patent Literature, "Segmenting Continuous Motions with Hidden Semi-Markov Models and Gaussian Processes," Frontiers in Neurorobotics, Vol. 11, Article 67, published December 21, 2017 (cited in the IDS filed 04/07/2025), in view of Mitchell et al. (Mitchell), Non-Patent Literature, "Implementing a Hidden Markov Model with Duration Modeling on the MasPar MP-1," Purdue University Technical Report, published June 1994, and further in view of Rush (Rush), Non-Patent Literature, "Torch-Struct: Deep Structured Prediction Library," arXiv:2002.00876v1, published February 3, 2020.
As to independent claim 1, Nakamura teaches:
"for combinations of predicted values predicting the event for each length up to a maximum length and variances of the predicted values,"
Nakamura teaches Gaussian process regression that learns, for each time step i within a segment, a predictive Gaussian distribution of the emission. Its mean is the predicted value and its variance is c − kᵀC⁻¹k (Nakamura, p. 4, left col., § 3.1, para. 1, Eq. (3): "a predictive distribution whereby the emission of time step i becomes x follows a Gaussian distribution").
The learned mean and standard deviation are shown for each time step (Nakamura, p. 4, Fig. 4 caption: "the solid line represents the mean, and the blue region represents the range of standard deviation").
The time steps within a segment run up to a maximum segment length K (Nakamura, p. 5, right col., para. 1: "C and K denote the number of classes and the maximum length of segments").
"the likelihoods being probabilities of observation values obtained from the event at the respective timesteps being generated;"
Nakamura computes the probability of the observed emission at time step i being generated from the predictive distribution of class c (Nakamura, p. 4, right col., para. 1, Eq. (6): "we assume that each dimension is generated independently, and a predictive distribution GP(x|Xc) is computed as follows").
Nakamura computes the probability of a segment of observations being generated (Nakamura, p. 5, right col., para. 1, Eq. (9): "P(st−k:t|Xc) represents the probability that st−k:t is generated from a class c").
"calculating a forward probability of a unit series having a certain length to be classified into a certain class with a certain timestep being an endpoint"
Nakamura computes the forward probability α[t][k][c] of a segment of length k, ending at time step t, belonging to class c (Nakamura, p. 5, left col., last para. to right col., para. 1, Eq. (8): "the probability that k samples st−k:t prior to time step t in observed sequence s form a segment, and that the resulting segment belongs to class c, is computed as follows"; p. 5, left col., Algorithm 2, lines 1–8).
Nakamura teaches computing, for each class, the probability of each candidate segment from the Gaussian-process predictive distribution, and using it in the forward-filtering recursion of Eq. (8) (Nakamura, p. 5). However, Nakamura does not teach the following limitations. In the same field of endeavor, Mitchell teaches:
"An information processing device comprising: a processor to execute a program; and a memory to store the program which, when executed by the processor, performs processes of,"
Mitchell teaches a parallel computer with processing elements and local memory executing programs (Mitchell, p. 4, § 3.2, para. 1: "The MP-1 is a massively-parallel computer with 16,384 PEs arranged in a 128-by-128 array. Each PE has a 4-bit ALU and 16 KBytes of local memory"; para. 3: "Our parallel programs are written in MPL").
"storing a log-likelihood matrix in which log-likelihoods are arranged as components in ascending order of lengths of unit series predetermined to divide a time series of a predetermined event and timesteps"
Mitchell allots D processing elements to each state, indexed by duration τ = 1, …, D in ascending order (Mitchell, p. 5, § 3.3, para. 1: "each state of the HMM is allotted D PEs"; para. 2: "Let the plural variable τ range from 1 to D across the D PEs assigned to state i").
D is the predetermined maximum duration of a segment dividing the observation sequence (Mitchell, p. 1, § 1, para. 2: "If D is the maximum duration allowed for any state").
The output probabilities of the observations are held across those duration-indexed elements for each time step t (Mitchell, p. 6, para. 2: "The D PEs allocated to a single HMM state can also be utilized in the calculation of the output probabilities"; p. 8, Table 3, line 3: "for t=1 to T").
"generating a shifted log-likelihood matrix by performing a shifting process of shifting the log-likelihoods other than log-likelihoods at the top of each line in the log-likelihood matrix in such a manner that the log-likelihoods are aligned along each line in ascending order of the lengths when the lengths and the timesteps are each increased by one unit;"
At each time step, Mitchell moves each output probability one element along the duration line (Mitchell, p. 8, Table 3, line 5: "out-prob = xnetW[1].out-prob"; p. 4, § 3.2, keyword table: "xnetW[d].variable — Accesses variable located in a PE which is d PEs to the west").
The newly computed output probability is written to the first element of each line, τ = 1, rather than shifted (Mitchell, p. 8, Table 3, line 10: "xnetW[M − 1].out_prob = p_exp(−sum/2.0) / norm").
The value held at duration τ and time step t therefore appears at duration τ + 1 and time step t + 1, aligning the output probabilities along each duration line as length and time step each increase by one unit (Mitchell, p. 7, § 3.4, para. 2: "the D most recent output probabilities are calculated only once and then saved by shifted the probability across the D PEs").
"generating a successive-generation probability matrix by adding the log-likelihoods from the top of each of the lines to the respective components in the shifted log-likelihood matrix, to calculate successive generation probabilities of the respective components;"
Mitchell accumulates the shifted output probabilities from the first element of each duration line to each element with a segmented prefix operation (Mitchell, p. 5, table of MasPar routines: "scanMuld(variable, seg) — Calculate the prefix product of variable; seg marks scan boundaries"; p. 8, Table 3, lines 11 and 13: "prod-tmp = out-prob" and "product = scanMuld(prod_tmp, duration_seg)").
The result at element τ is the probability that the τ most recent observations are successively generated by the state.
"by using a value obtained by adding the successive generation probabilities up to the respective components in ascending order of the lengths at the respective timesteps"
Mitchell computes the forward probability at each time step by summing, in ascending order of duration, the contributions of the segment probabilities (Mitchell, p. 8, Table 3, lines 14–15: "sum-tmp = old-alpha × d × product" and "state_sum = scanAddd(sum_tmp, duration_seg)"; p. 5, table of MasPar routines: "scanAddd(variable, seg) — Calculate the prefix sum of variable"; p. 7, § 3.4, para. 2: "the current forward probability of the successor state is found by summing the contribution of all D possible durations").
Nakamura and Mitchell are analogous to the claimed invention as both are from the same field of endeavor of segmenting time-series data with explicit-duration (semi-Markov) hidden Markov models. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the Gaussian-process forward filtering of Nakamura with the duration-indexed storage, shifting, and prefix accumulation of Mitchell. The motivation to combine is to reduce computation time: Nakamura recognizes that "computational costs are very high, owing to the numerous recursive calculations" (Nakamura, p. 3, right col., last para. of § 2; p. 9, Table 3), and Mitchell teaches computing the output probabilities "only once" and accumulating them in parallel (Mitchell, p. 7, § 3.4, para. 2), such that "Training that use to take more than a week can now be completed in about an hour" (Mitchell, p. 1, § 1, para. 5).
The combination of Nakamura and Mitchell, however, does not teach the following limitations. In the same field of endeavor, Rush teaches:
"the log-likelihoods being obtained by converting likelihoods into logarithms,"
Rush computes segmentation probabilities from log-potentials, i.e., logarithms of unnormalized likelihoods (Rush, p. 4, left col., § 5.1: "Similarly log-potentials are now defined over parts").
For the semi-Markov model, these log-potentials form a tensor indexed by sequence position N, segment length K, and label C (Rush, p. 2, Table 1, "Semi-Markov" row: parts "Edges (NKC²)", algorithm "Segmental F-B").
Rush performs the dynamic program in the log semiring, in which multiplication of probabilities is addition of log values (Rush, p. 5, left col., para. 4: "The log-partition utilizes ⊕, ⊗ = LSE, +"). The prefix product of Mitchell is therefore performed as addition of log-likelihoods.
"generating a shifted successive-generation probability matrix by shifting the successive generation probabilities in the successive-generation-probability matrix in such a manner that shift destinations and shift sources of components whose values have been shifted through the shifting process are reversed; and"
Rush re-indexes a chart of values over length-offset spans in two opposite directions (Rush, p. 5, right col., § 6(b), para. 1, to p. 6, left col., para. 1: "we reindex the chart. Instead of using a single chart C, we split it into two parts: one right-facing Cr[i, d] = C[i, i + d] and one left facing, Cl[i + d, T − d] = C[i, i + d]").
Each value with offset d is relocated to its start index i in Cr and to its end index i + d in Cl. The same offset is thus applied with shift source and shift destination reversed.
"in the shifted successive-generation probability matrix."
Rush performs the dynamic-programming update on the reindexed charts (Rush, p. 6, left col., para. 1: "After this reindexing, the update can be written … this formula can easily be computed as a vectorized semiring dot product").
Because Nakamura's α[t][k][c] is indexed by the segment endpoint t, the values it uses are those of the end-indexed chart.
Nakamura, Mitchell, and Rush are analogous to the claimed invention as all are from the same field of endeavor of computing segmentation probabilities of sequential data by dynamic programming over segment lengths. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the log-domain computation and bidirectional chart reindexing of Rush with the combination of Nakamura and Mitchell. The motivation to combine is computational efficiency: Rush states that dynamic programming algorithms "Implemented naively … are prohibitively slow" and reindexes the chart so the update is computed "in one operation" on GPU hardware (Rush, p. 5, right col., § 6, para. 1; p. 6, left col., para. 1).
As to claim 2, the combination of Nakamura, Mitchell, and Rush teaches "The information processing device according to claim 1," which is rejected under the same rationale set forth above for claim 1.
Nakamura teaches computing forward-filtering values over an array having a segment-length axis k and a time-step axis t (Nakamura, p. 5, Fig. 6, "Recursive computation in forward filtering," depicting axes k, t, and c; p. 5, left col., Algorithm 2, lines 2–3: "for t = 1 to T do" and "for k = 1 to K do"). However, Nakamura does not teach the following limitation. In the same field of endeavor, Mitchell teaches:
"wherein, when the lengths are arranged in a row direction and the timesteps are arranged in a column direction in the log-likelihood matrix, the processor shifts the log-likelihoods in each row in a direction in which the timesteps decrease by a column number corresponding to a value obtained by subtracting one from a row number, and"
Mitchell assigns each duration τ = 1, …, D its own processing element (Mitchell, p. 5, § 3.3, para. 2: "Let the plural variable τ range from 1 to D across the D PEs assigned to state i").
Each value is displaced by τ − 1 time steps toward earlier time steps. The element for duration τ holds the value at time step t + 1 − τ, i.e., t − (τ − 1) (Mitchell, p. 6, para. 1: "For each of the D PEs assigned to state i, let the plural variables, new_alpha and old_alpha, be equal to equation variable, α_{t+1−τ}(i) at times t and t − 1, respectively").
The output probabilities are displaced by the same mechanism. At each time step, each output probability is passed one element along the duration line (Mitchell, p. 8, Table 3, line 3: "for t=1 to T"; line 5: "out-prob = xnetW[1].out-prob"). After τ − 1 time steps, the element for duration τ holds the output probability of observation O_{t−(τ−1)}.
The displacement is therefore τ − 1, i.e., the index of the duration element minus one, in the direction of decreasing time steps. It is performed by the processing elements (Mitchell, p. 7, § 3.4, para. 2: "the D most recent output probabilities are calculated only once and then saved by shifted the probability across the D PEs").
Nakamura and Mitchell are analogous to the claimed invention as both are from the same field of endeavor of segmenting time-series data with explicit-duration (semi-Markov) hidden Markov models. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to shift the per-length log-likelihoods of Nakamura toward decreasing time steps by an offset equal to the length index minus one, as taught by Mitchell. The motivation to combine is to align, for each length, the likelihood of the observation at each position of a segment with the likelihoods of the preceding positions of the same segment, so that each output probability is "calculated only once" and reused for every duration (Mitchell, p. 7, § 3.4, para. 2).
The combination of Nakamura and Mitchell, however, does not teach the following limitation. In the same field of endeavor, Rush teaches:
"the processor shifts the successive generation probabilities in each row in a direction in which the timesteps increase by the column number corresponding to a value obtained by subtracting one from the row number."
Rush stores the dynamic-programming values of each span of positions i through i + d, a span of length d + 1 (Rush, p. 5, right col., § 6(b), para. 1: "C[i, i + d]").
Rush reindexes these values in two opposite directions by the same offset d. In the right-facing chart the value is placed at its start position i; in the left-facing chart it is placed at its end position i + d, i.e., moved toward increasing positions by d (Rush, p. 5, right col., § 6(b), para. 1, to p. 6, left col., para. 1: "one right-facing Cr[i, d] = C[i, i + d] and one left facing, Cl[i + d, T − d] = C[i, i + d]").
Because a span of length d + 1 is moved by d, the offset equals the length minus one, i.e., the row number minus one when rows are ordered by length.
Each length d is processed as one line across all positions (Rush, p. 6, left col., para. 1: "This allows use to compute Cr[·, d] in one operation"). The lengths are thus arranged in the row direction and the positions (timesteps) in the column direction.
Nakamura, Mitchell, and Rush are analogous to the claimed invention as all are from the same field of endeavor of computing segmentation probabilities of sequential data by dynamic programming over segment lengths. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to shift the successive generation probabilities of the combination of Nakamura and Mitchell in each row toward increasing time steps by the row number minus one, as taught by Rush. The motivation to combine is to restore endpoint indexing, so that each row can be processed in a single vectorized operation (Rush, p. 6, left col., para. 1) and Nakamura's forward probability α[t][k][c], which is indexed by the segment endpoint t, can read the successive generation probability directly at column t (Nakamura, p. 5, right col., para. 1, Eq. (8)).
As to claim 3, the combination of Nakamura, Mitchell, and Rush teaches "The information processing device according to claim 1," which is rejected under the same rationale set forth above for claim 1.
Nakamura teaches computing forward-filtering values over an array having a segment-length axis k and a time-step axis t (Nakamura, p. 5, Fig. 6, "Recursive computation in forward filtering," depicting axes k, t, and c; p. 5, left col., Algorithm 2, lines 2–3: "for t = 1 to T do" and "for k = 1 to K do"). However, Nakamura does not teach the following limitation. In the same field of endeavor, Mitchell teaches:
"the processor shifts the log-likelihoods in each column in a direction in which the timesteps decrease by a row number corresponding to a value obtained by subtracting one from a column number, and"
Mitchell assigns each duration τ = 1, …, D its own processing element (Mitchell, p. 5, § 3.3, para. 2: "Let the plural variable τ range from 1 to D across the D PEs assigned to state i").
The element for duration τ holds the value at time step t + 1 − τ, i.e., t − (τ − 1). Each value is thus displaced toward decreasing time steps by the duration index minus one (Mitchell, p. 6, para. 1: "For each of the D PEs assigned to state i, let the plural variables, new_alpha and old_alpha, be equal to equation variable, α_{t+1−τ}(i) at times t and t − 1, respectively").
The output probabilities are displaced by the same once-per-time-step shift, performed by the processing elements (Mitchell, p. 8, Table 3, line 3: "for t=1 to T"; line 5: "out-prob = xnetW[1].out-prob"; p. 7, § 3.4, para. 2: "the D most recent output probabilities are calculated only once and then saved by shifted the probability across the D PEs").
The displacement depends only on the duration index, so it is the same whether the duration index is laid out as rows or as columns. Where the duration index is the column number, each value is shifted within its column by the column number minus one, in the direction of decreasing time steps.
Nakamura and Mitchell are analogous to the claimed invention as both are from the same field of endeavor of segmenting time-series data with explicit-duration (semi-Markov) hidden Markov models. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to shift the per-length log-likelihoods of Nakamura toward decreasing time steps by an offset equal to the length index minus one, as taught by Mitchell. The motivation to combine is to align the likelihoods of successive positions of the same segment, so that each output probability is "calculated only once" and reused for every duration (Mitchell, p. 7, § 3.4, para. 2).
The combination of Nakamura and Mitchell, however, does not teach the following limitations. In the same field of endeavor, Rush teaches:
"wherein, when the lengths are arranged in a column direction and the timesteps are arranged in a row direction in the log-likelihood matrix,"
Rush stores the dynamic-programming values in a two-index chart whose first index is the position i and whose second index is the span length d (Rush, p. 6, left col., para. 1: "Cr[i, d] = C[i, i + d]").
Each length d is computed as a single vector over all positions (Rush, p. 6, left col., para. 1: "This allows use to compute Cr[·, d] in one operation"). With positions as the first (row) index and lengths as the second (column) index, the lengths are arranged in the column direction and the positions (timesteps) in the row direction.
A two-dimensional array indexed by length and time step can be stored in only two orientations: lengths along rows with time steps along columns, or the transpose. Selecting the transposed orientation is choosing from a finite number of identified, predictable solutions with a reasonable expectation of success (MPEP § 2143(I)(E)).
"the processor shifts the successive generation probabilities in each row in a direction in which the timesteps increase by the row number corresponding to a value obtained by subtracting one from the column number."
Rush reindexes each span value from its start position i to its end position i + d. Each value is thus moved toward increasing positions by d (Rush, p. 5, right col., § 6(b), para. 1, to p. 6, left col., para. 1: "one right-facing Cr[i, d] = C[i, i + d] and one left facing, Cl[i + d, T − d] = C[i, i + d]").
A span from position i to i + d has length d + 1, so the offset d equals the length minus one. With the length index as the column number, that is the column number minus one, applied toward increasing time steps.
Nakamura, Mitchell, and Rush are analogous to the claimed invention as all are from the same field of endeavor of computing segmentation probabilities of sequential data by dynamic programming over segment lengths. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to arrange the log-likelihood matrix of the combination of Nakamura and Mitchell with lengths in the column direction, and to shift the successive generation probabilities toward increasing time steps by the column number minus one, as taught by Rush. The motivation to combine is to restore endpoint indexing so each length is processed "in one operation" (Rush, p. 6, left col., para. 1), and so Nakamura's forward probability α[t][k][c], indexed by the segment endpoint t, reads each successive generation probability directly at time step t (Nakamura, p. 5, right col., para. 1, Eq. (8)).
As to claim 4, the combination of Nakamura, Mitchell, and Rush teaches "The information processing device according to claim 1," which is rejected under the same rationale set forth above for claim 1.
Nakamura further teaches:
"wherein the predicted values are values determined through calculation of Gaussian distribution likelihood."
Nakamura determines the predicted value of the emission at each time step i of a segment from a predictive distribution that is Gaussian. Its mean kᵀC⁻¹x is the predicted value and its variance is c − kᵀC⁻¹k (Nakamura, p. 4, left col., § 3.1, para. 1, Eq. (3): "a predictive distribution whereby the emission of time step i becomes x follows a Gaussian distribution").
The predictive distribution is computed with a Gaussian kernel (Nakamura, p. 4, left col., § 3.1, para. 2, Eq. (5): "We use the following Gaussian kernel, which is generally used for Gaussian process regression").
Nakamura evaluates the probability of the observed emission under that Gaussian predictive distribution, per dimension (Nakamura, p. 4, right col., para. 1, Eq. (6): "Figure 4 shows examples of Gaussian processes … the right graph shows the learned probabilistic distribution p(x|i, Xc, i)").
Nakamura uses that probability to compute the segment likelihood (Nakamura, p. 5, right col., para. 1, Eq. (9): "P(st−k:t|Xc) = GP(st−k:t|Xc)Plen(k|λ)").
The predicted values are therefore values determined through calculation of Gaussian distribution likelihood.
As to claim 5, the combination of Nakamura, Mitchell, and Rush teaches "The information processing device according to claim 1," which is rejected under the same rationale set forth above for claim 1.
Nakamura further teaches:
"wherein the predicted values are expected values calculated with a blocked Gibbs sampler."
Nakamura estimates the segments of the observed sequences, and the class of each segment, with a blocked Gibbs sampler (Nakamura, p. 4, right col., § 3.2.1, para. 1: "For efficient sampling, we use the blocked Gibbs sampler, which samples segments and their classes in an observed sequence").
The segments sampled for each class c form the set Xc from which the Gaussian process of that class is learned (Nakamura, p. 5, left col., para. 1: "After sampling xnj and cnj, parameter Xc of the Gaussian process and transition probability P(c|c′) of HSMM are updated by adding them to the learning data"; p. 5, left col., Algorithm 1, lines 7, 12, and 18).
The predicted value of the emission at each time step i is the mean of the Gaussian predictive distribution conditioned on the sampled set Xc, i.e., the expected value of the emission given the segments sampled by the blocked Gibbs sampler (Nakamura, p. 4, left col., § 3.1, para. 1, Eq. (3): "If we obtain pairs (i, Xc) of emissions xi of time step i of segments belonging to the same class c, a predictive distribution whereby the emission of time step i becomes x follows a Gaussian distribution").
The predicted values are therefore expected values calculated with a blocked Gibbs sampler.
As to claim 7, the combination of Nakamura, Mitchell, and Rush teaches "The information processing device according to claim 1," which is rejected under the same rationale set forth above for claim 1.
Nakamura teaches computing segment probabilities separately for each of a plurality of classes, each class having its own Gaussian process (Nakamura, p. 4, left col., para. 1, Eq. (2): "Xc represents a set of segments classified into class c"; p. 5, Fig. 6, depicting a class axis c together with the length axis k and time-step axis t; p. 5, left col., Algorithm 2, line 4: "for c = 1 to C do"). However, Nakamura does not teach the following limitations. In the same field of endeavor, Mitchell teaches:
"wherein, the processor stores the log-likelihood matrix for each of a plurality of dimensions corresponding to a plurality of classes of the unit series, and"
Mitchell allots a separate block of D processing elements to each state of the model (Mitchell, p. 5, § 3.3, para. 1, and Fig. 3: "each state of the HMM is allotted D PEs. One possible layout is shown in figure 3").
Each state's block stores that state's duration-indexed output probabilities (Mitchell, p. 6, para. 2: "The D PEs allocated to a single HMM state can also be utilized in the calculation of the output probabilities").
Each state of Mitchell's explicit-duration model generates a segment of the observation sequence, as each class of Nakamura does. Mitchell therefore stores the duration-indexed likelihoods separately for each of a plurality of dimensions corresponding to the plurality of classes.
"the processor executes processing in parallel in each of the dimensions other than the timesteps."
Mitchell processes the time steps sequentially (Mitchell, p. 8, Table 3, line 3: "for t=1 to T").
Within each time step, Mitchell processes all states and all durations in parallel (Mitchell, p. 7, para. 1: "All other states can be evaluated simultaneously resulting in a speedup of ND"; p. 8, Table 3, lines 4–15, executed on the active set "ALL").
Mitchell thus executes processing in parallel in each dimension (state/class and duration) other than the time steps.
Nakamura and Mitchell are analogous to the claimed invention as both are from the same field of endeavor of segmenting time-series data with explicit-duration (semi-Markov) hidden Markov models. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to store the log-likelihood matrix of the combination of Nakamura, Mitchell, and Rush for each class of Nakamura, and to process every class and length in parallel while stepping sequentially through the time steps, as taught by Mitchell. The motivation to combine is to reduce computation time: Mitchell's per-state parallel layout achieves "a speedup of ND" (Mitchell, p. 7, para. 1), making the implementation "nearly constant in D for both training and recognition" (Mitchell, p. 1, § 1, para. 2). The motivation to further combine Rush is as set forth for claim 1.
Claim 8 is rejected under 35 U.S.C. 103 for the same rationale set forth above for claims 2 and 7. Claim 8 depends from claim 2 and recites the same additional limitations as claim 7.
Claim 9 is rejected under 35 U.S.C. 103 for the same rationale set forth above for claims 3 and 7. Claim 9 depends from claim 3 and recites the same additional limitations as claim 7.
Claim 10 is rejected under 35 U.S.C. 103 for the same rationale set forth above for claims 4 and 7. Claim 10 depends from claim 4 and recites the same additional limitations as claim 7.
Claim 11 is rejected under 35 U.S.C. 103 for the same rationale set forth above for claims 5 and 7. Claim 11 depends from claim 5 and recites the same additional limitations as claim 7.
Claim 13 is rejected under 35 U.S.C. 103 for the same rationale set forth above for claim 1. Claim 13 recites a non-transitory computer-readable storage medium storing a program that causes a computer to execute the same processes recited in claim 1.
As to independent claim 14, Nakamura teaches:
"An information processing method comprising:"
Nakamura teaches a method that processes time-series data to divide it into segments (Nakamura, p. 1, Abstract: "In this paper, we propose a Gaussian process-hidden semi-Markov model (GP-HSMM) that can divide continuous time series data into segments in an unsupervised manner").
"for combinations of predicted values predicting the event for each length up to a maximum length and variances of the predicted values,"
Nakamura learns, for each time step i within a segment, a Gaussian predictive distribution whose mean is the predicted value and whose variance is c − kᵀC⁻¹k (Nakamura, p. 4, left col., § 3.1, para. 1, Eq. (3): "a predictive distribution whereby the emission of time step i becomes x follows a Gaussian distribution"; p. 4, Fig. 4 caption: "the solid line represents the mean, and the blue region represents the range of standard deviation").
The time steps within a segment run up to a maximum length K (Nakamura, p. 5, right col., para. 1: "C and K denote the number of classes and the maximum length of segments").
"the likelihoods being probabilities of observation values obtained from the event at the respective timesteps being generated;"
Nakamura computes the probability of the observed emission at each time step being generated from the predictive distribution, and the probability of a segment being generated from a class (Nakamura, p. 4, right col., para. 1, Eq. (6); p. 5, right col., para. 1, Eq. (9): "P(st−k:t|Xc) represents the probability that st−k:t is generated from a class c").
Nakamura teaches computing, for each class, the probability of each candidate segment from the Gaussian-process predictive distribution (Nakamura, p. 5, Eqs. (8)–(9)). However, Nakamura does not teach the following limitation. In the same field of endeavor, Mitchell teaches:
"using a log-likelihood matrix in which log-likelihoods are arranged as components in ascending order of lengths of unit series predetermined to divide a time series of a predetermined event and timesteps"
Mitchell arranges the output probabilities of the observations across processing elements indexed by duration τ = 1, …, D in ascending order, where D is the predetermined maximum duration of a segment dividing the observation sequence (Mitchell, p. 5, § 3.3, para. 2: "Let the plural variable τ range from 1 to D across the D PEs assigned to state i"; p. 1, § 1, para. 2: "If D is the maximum duration allowed for any state").
Mitchell uses these arranged probabilities at each time step (Mitchell, p. 6, para. 2: "The D PEs allocated to a single HMM state can also be utilized in the calculation of the output probabilities"; p. 8, Table 3, line 3: "for t=1 to T").
Nakamura and Mitchell are analogous to the claimed invention as both are from the same field of endeavor of segmenting time-series data with explicit-duration (semi-Markov) hidden Markov models. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to arrange the per-length likelihoods of Nakamura in ascending order of length and by time step, as taught by Mitchell. The motivation to combine is to compute each output probability "only once" and reuse it for every duration, reducing computation time (Mitchell, p. 7, § 3.4, para. 2; p. 1, § 1, para. 5).
The combination of Nakamura and Mitchell, however, does not teach the following limitation. In the same field of endeavor, Rush teaches:
"the log-likelihoods being obtained by converting likelihoods into logarithms,"
Rush computes segmentation probabilities from log-potentials, i.e., logarithms of unnormalized likelihoods, arranged over sequence position, segment length, and class (Rush, p. 4, left col., § 5.1: "Similarly log-potentials are now defined over parts"; p. 2, Table 1, "Semi-Markov" row: "Edges (NKC²)").
Rush performs the dynamic program in the log semiring (Rush, p. 5, left col., para. 4: "The log-partition utilizes ⊕, ⊗ = LSE, +").
Nakamura, Mitchell, and Rush are analogous to the claimed invention as all are from the same field of endeavor of computing segmentation probabilities of sequential data by dynamic programming over segment lengths. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to convert the arranged likelihoods of the combination of Nakamura and Mitchell into logarithms, as taught by Rush. The motivation to combine is that computing in the log semiring turns products of probabilities into sums, which Rush vectorizes for computational efficiency (Rush, p. 5, left col., para. 4; p. 5, right col., § 6, para. 1).
The remaining limitations of claim 14 are the same as those of claims 1 and 13 and are rejected under the same rationale set forth above for claims 1 and 13.
Claims 6 and 12 are rejected under 35 U.S.C. 103 as being unpatentable over Nakamura in view of Mitchell, further in view of Rush, and further in view of Zhu et al. (Zhu), Non-Patent Literature, "Deep and Confident Prediction for Time Series at Uber," arXiv:1709.01907v1, published September 6, 2017.
As to claim 6, the combination of Nakamura, Mitchell, and Rush teaches "The information processing device according to claim 1," which is rejected under the same rationale set forth above for claim 1.
Nakamura teaches obtaining the predicted values, and the variances of the predicted values, from a Gaussian predictive distribution learned by Gaussian process regression (Nakamura, p. 4, left col., § 3.1, para. 1, Eq. (3); p. 4, Fig. 4 caption). However, the combination of Nakamura, Mitchell, and Rush does not teach the following limitation. In the same field of endeavor, Zhu teaches:
"wherein the predicted values are predicted with a recurrent neural network with dropouts added to introduce uncertainty."
Zhu predicts time-series values with a Long Short Term Memory (LSTM) network, a recurrent neural network, to which dropout is applied (Zhu, p. 4, left col., para. 2: "variational dropout for recurrent neural networks [22] is applied to the LSTM layers in the encoder, and regular dropout [13] is applied to the prediction network").
The dropout introduces uncertainty into the prediction (Zhu, p. 2, right col., § 2.2, last para.: "stochastic dropouts are applied after each hidden layer, and the model output can be approximately viewed as a random sample generated from the posterior predictive distribution").
The dropout outputs are averaged to give the predicted value and their sample variance to give the uncertainty (Zhu, p. 3, right col., § 3.1.1, para. 1, Eq. (3); p. 4, left col., Algorithm 1, lines 6–7: "ŷmc ← (1/B) Σ ŷ(b)" and "η1² ← (1/B) Σ (ŷ*(b) − ŷ*)²").
Zhu thus predicts values, with their variances, using a recurrent neural network with dropouts added to introduce uncertainty.
Nakamura, Mitchell, Rush, and Zhu are analogous to the claimed invention as all are from the same field of endeavor of probabilistic modeling of time-series data. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to replace the Gaussian-process predictor of the combination of Nakamura, Mitchell, and Rush with the recurrent neural network with dropout of Zhu. Both predictors produce a predicted value and a variance for each time step, so the substitution yields predictable results (MPEP § 2143(I)(B)). The motivation to combine is that an LSTM network "can model complex nonlinear feature interactions" and offers "end-to-end modeling, ease of incorporating exogenous variables, and automatic feature extraction abilities," while the dropout framework provides "uncertainty estimation almost for free" (Zhu, p. 1, right col., para. 1; p. 1, left col., § 1, para. 2; p. 2, right col., § 2.2, last para.).
Regarding claim 12, the combination of Nakamura, Mitchell, Rush, and Zhu teaches "The information processing device according to claim 6," which is rejected under the same rationale set forth above for claim 6.
Nakamura teaches computing segment probabilities separately for each of a plurality of classes, each class having its own Gaussian process (Nakamura, p. 4, left col., para. 1, Eq. (2): "Xc represents a set of segments classified into class c"; p. 5, Fig. 6, depicting a class axis c together with the length axis k and time-step axis t; p. 5, left col., Algorithm 2, line 4: "for c = 1 to C do"). However, Nakamura does not teach the following limitations. In the same field of endeavor, Mitchell teaches:
"wherein, the processor stores the log-likelihood matrix for each of a plurality of dimensions corresponding to a plurality of classes of the unit series, and"
Mitchell allots a separate block of D processing elements to each state of the model (Mitchell, p. 5, § 3.3, para. 1, and Fig. 3: "each state of the HMM is allotted D PEs. One possible layout is shown in figure 3").
Each block stores that state's duration-indexed output probabilities (Mitchell, p. 6, para. 2: "The D PEs allocated to a single HMM state can also be utilized in the calculation of the output probabilities").
Each state of Mitchell's explicit-duration model generates a segment of the observation sequence, as each class of Nakamura does. Mitchell therefore stores the duration-indexed likelihoods separately for each of a plurality of dimensions corresponding to the plurality of classes.
"the processor executes processing in parallel in each of the dimensions other than the timesteps."
Mitchell processes the time steps sequentially (Mitchell, p. 8, Table 3, line 3: "for t=1 to T").
Within each time step, Mitchell processes all states and all durations in parallel (Mitchell, p. 7, para. 1: "All other states can be evaluated simultaneously resulting in a speedup of ND"; p. 8, Table 3, lines 4–15, executed on the active set "ALL").
Mitchell thus executes processing in parallel in each dimension (state/class and duration) other than the time steps.
Nakamura and Mitchell are analogous to the claimed invention as both are from the same field of endeavor of segmenting time-series data with explicit-duration (semi-Markov) hidden Markov models. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to store the log-likelihood matrix of the combination of Nakamura, Mitchell, Rush, and Zhu for each class of Nakamura, and to process every class and length in parallel while stepping sequentially through the time steps, as taught by Mitchell. The motivation to combine is to reduce computation time: Mitchell's per-state parallel layout achieves "a speedup of ND" (Mitchell, p. 7, para. 1), making the implementation "nearly constant in D for both training and recognition" (Mitchell, p. 1, § 1, para. 2). Storing and processing each class separately applies equally where the predicted values of each class are produced by the recurrent neural network of Zhu, because Zhu's network produces a predicted value and variance for each time step in the same manner as the Gaussian process of Nakamura. The motivation to combine Rush and Zhu is as set forth for claims 1 and 6.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to HUNG VAN LE whose telephone number is (571)270-0164. The examiner can normally be reached 8 a.m. - 5 p.m..
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, Cesar Paula can be reached at (571) 272-4128. 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.
/HUNG VAN LE/Examiner, Art Unit 2145
/CESAR B PAULA/Supervisory Patent Examiner, Art Unit 2145
Prosecution Insights