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 .
Priority
The present application, 18247942, filed 04/05/2023 is a National Stage entry of PCT/JP2020/041426, international filing date: 11/05/2020.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 04/05/2023 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Specification
The title of the invention is not descriptive. A new title is required that is clearly indicative of the invention to which the claims are directed.
The following title is suggested: Estimating a maximum a posteriori solution of a collective graphical model based on discrete difference-of-convex programming.
Claim Objections
Claims 1-5 are objected to under 37 C.F.R. 1.71(a) which requires “full, clear, concise, and exact terms” as to enable any person skilled in the art or science to which the invention or discovery appertains, or with which it is most nearly connected, to make and use the same. The following should be corrected.
A. Claim 1 recites “DC” in line 10. This acronym should be spelled out in the first recitation in each claim set to define how this acronym is to be interpreted. Claims 2-3 and 5 inherit the same deficiency as claim 1 by reason of dependence.
B. Claim 4 recites “MAP” in line 1; “CGM” in line 2; and “DC” in line 11. These acronyms should be spelled out in the first recitation in each claim set to define how these acronyms are to be interpreted.
C. In claim 5 line 2, “a computer” should read “the computer” instead because a computer is already introduced in claim 1 from which the claim depends.
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-5 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Under Step 1, claims 1-3 recite a series of steps and, therefore, is a process. Claim 4 recites an apparatus and, therefore, is a machine. Claim 5 recites a non-transitory computer-readable recording medium and, therefore, is an article of manufacture.
Under Step 2A prong 1, claim 4 recites
An estimation apparatus that estimates a MAP solution of a CGM on a path graph, the apparatus comprising:
a memory; and
a processor coupled to the memory and configured to:
receive, as inputs, aggregate data and potentials of the CGM on the path graph;
solve a MAP estimation problem of the CGM by a technique based on discrete DC programming using the aggregate data and the potentials, and calculate a MAP estimation solution; and
output the MAP estimation solution.
The above underlined limitations of solving/estimating a solution to an estimation problem amounts to processing mathematical relationships/calculations and falls within the “Mathematical Concepts” grouping of abstract ideas. See at least paragraph [0025] for the equations of the MAP estimation problem being solved/calculated. Accordingly, the claim is directed to recite an abstract idea.
Under step 2A prong 2, the claim recites the following additional elements: a memory; a processor coupled to the memory and configured to: receive, as inputs, aggregate data and potentials of the CGM on the path graph; and output the MAP estimation solution. However, the additional elements of “a memory” and “a processor” are recited at a high-level of generality (i.e., as a generic computer memory; and as a generic computer processor for executing a series of operations) such that they amount to no more than mere instructions using a generic computer component or merely as tools to implement the abstract idea or merely reciting the words “apply it” (or an equivalent) with the judicial exception. Use of a computer or other machinery in its ordinary capacity for economic or other tasks (e.g., to receive, store, or transmit data) or simply adding a general purpose computer or computer components after the fact to an abstract idea (e.g., a fundamental economic practice or mathematical equation) does not integrate a judicial exception into a practical application or provide significantly more. See 2106.05(f)(2) for more information. The additional elements of “receive, as inputs, aggregate data and potentials of the CGM on the path graph” and “output the MAP estimation solution” are merely adding insignificant extra-solution activities, i.e. mere data gathering and outputting steps. The additional elements do not, individually or in combination, integrate the exception into a practical application. Accordingly, the claim is not integrated into a practical application.
Under step 2B, claim 4 does not include additional elements that, individually or in combination, are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a practical application, the additional elements of “a memory” and “a processor” are recited at a high-level of generality (i.e., as a generic computer memory; and as a generic computer processor for executing a series of operations) such that they amount to no more than mere instructions using a generic computer component or merely as tools to implement the abstract idea or merely reciting the words “apply it” (or an equivalent) with the judicial exception. Use of a computer or other machinery in its ordinary capacity for economic or other tasks (e.g., to receive, store, or transmit data) or simply adding a general purpose computer or computer components after the fact to an abstract idea (e.g., a fundamental economic practice or mathematical equation) does not integrate a judicial exception into a practical application or provide significantly more. See 2106.05(f)(2) for more information. The additional elements of “receive, as inputs, aggregate data and potentials of the CGM on the path graph” and “output the MAP estimation solution” are merely adding insignificant extra-solution activities, i.e. mere data gathering and outputting steps. See MPEP 2106.05(d)(II) which states that the courts have recognized computer functions such as “Receiving or transmitting data over a network” and “Storing and retrieving information in memory” as well‐understood, routine, and conventional functions when they are claimed in a merely generic manner (e.g., at a high level of generality) or as insignificant extra-solution activity. The claim does not recite additional elements that alone or in combination amount to an inventive concept. Accordingly, the claim does not amount to significantly more than the abstract idea.
Regarding claim 1, it is directed to a method practiced by the apparatus of claim 4. All steps performed by the method of claim 1 would be practiced by the apparatus of claim 4. Claim 4 analysis applies equally to claim 1.
Regarding claims 2-3, they recite the same abstract idea as claim 1 by reason of dependence. Furthermore, under step 2A prong 1, claim 2 recites further details of the abstract idea of solving the MAP estimation problem “wherein in the solving of the MAP estimation problem of the CGM, a minimum cost flow problem is constructed using the aggregate data and the potentials, and the minimum cost flow problem is solved by the technique based on the discrete DC programming”; and claim 3 recites further details of the abstract idea of calculating the MAP estimation solution “wherein in the calculating of the MAP estimation solution, correction of a cost function on a network targeted by the minimum cost flow problem and calculation of an optimum solution of a minimum convex cost flow problem using a corrected cost function, by the technique based on the discrete DC programming, is repeated” which falls within the “Mathematical Concepts” grouping of abstract ideas. In particular claims 2-3 do not include additional elements that would require further analysis under step 2A prong 2 and step 2B. Accordingly, the claims are directed to recite an abstract idea.
Regarding claim 5, it is directed to a non-transitory computer-readable recording medium storing a program that causes the computer to execute the estimation method according to claim 1. Claim 4/1 analysis applies equally to claim 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.
Claims 1-5 are rejected under 35 U.S.C. 103 as being unpatentable over Kumar (NPL – “Exploiting Domain Structure in Multiagent Decision-Theoretic Planning and Reasoning”), in view of Jebara (US 20120066172 A1).
Regrading claim 4, Kumar teaches (Kumar section 2.1 “A Markov random field is a class of undirected graphical models which define a probability distribution over a collection of random variables”; Equations 2.2-2.3; 3.1.2; section 3.4; section 3.4.1; section 3.4.3 “the DC programming framework of MAP we have developed is quite general and subsumes existing frameworks to solve the LP relaxation of the MAP”; MAP solution – solution to Equation 2.2/2.3; CGM - graphical model):
receive, as inputs, aggregate data and potentials of the CGM on the path graph (Kumar section 2.1 “Associated with each edge (i, j)
∈
E is a potential function
θ
i
,
j
(
x
i
,
x
j
)”; section 3.4.1; page 43 Algorithm 1; aggregate data – graph data including the nodes and edges (G = (V, E); potentials -
θ
i
,
j
;);
solve a MAP estimation problem of the CGM by a technique based on discrete DC programming using the aggregate data and the potentials, and calculate a MAP estimation solution (Kumar section 3.4.1 “We now describe how optimization over different variational formulations of MAP can be formulated as a DC program”; section 3.4.2 “We now describe how we can solve each iteration of CCCP, which itself is a convex optimization problem, in the context of MAP DC program”; page 43 Algorithm 1; page 10 first full paragraph “We also develop a message-passing algorithm called Hybrid Belief Propagation (HBP) that solves the hybrid variational formulation. This message-passing approach is developed by exploiting the connection between the MAP problem and the difference-of-convex function programming”; MAP estimation problem – Equation 3.10 or 3.14-3.15; discrete DC programming – difference-of-convex function (DC) programming; MAP estimation solution – solution to Equation 3.10 or 3.14-3.15); and
.
Kumar does not explicitly teach an estimation apparatus that estimates a MAP solution of a CGM on a path graph, the apparatus comprising: a memory; and a processor coupled to the memory and configured to: output the MAP estimation solution.
However, on the same field of endeavor, Jebara discloses an estimation apparatus that estimates a MAP solution of a CGM on a path graph, the apparatus comprising: a memory: and a processor coupled to the memory and configured to: output the MAP estimation solution (Jebara Fig. 2 and paragraphs [0049-0050, 0141] “One embodiment includes a system for maximum a posteriori (MAP) estimation of a graphical model. The system comprises a computer-readable medium, a MAP estimation processor coupled to the computer-readable … The operations can further include outputting the MAP estimate”; Figs. 1C-1D and paragraphs [0136] “The processor 106 is programmed to determine a MAP estimate configuration of the NMRF 104, which is represented as X* 108”; estimation apparatus – MAP estimation system; memory - computer-readable medium; processor – processor).
Accordingly, 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 Kumar using Jebara and implement the algorithm of Kumar in a computer system comprising: a memory and a processor coupled to the memory because computers can take in and process large amounts of the most tedious information round the clock to provide valuable intelligence that can be used to augment or supplement human decisions and provide automated control and information (Jebara paragraph [0002]). Further, configure the processor to output the MAP estimation solution in order to provide a visual representation of the output depending on the particular application (Jebara paragraph [0136]).
Therefore, the combination of Kumar as modified in view of Jebara teaches an estimation apparatus that estimates a MAP solution of a CGM on a path graph, the apparatus comprising: a memory; and a processor coupled to the memory and configured to: receive, as inputs, aggregate data and potentials of the CGM on the path graph; solve a MAP estimation problem of the CGM by a technique based on discrete DC programming using the aggregate data and the potentials, and calculate a MAP estimation solution; and output the MAP estimation solution.
Regarding claim 1, it is directed to a method practiced by the apparatus of claim 4. All steps performed by the method of claim 1 would be practiced by the apparatus of claim 4. Claim 4 analysis applies equally to claim 1.
Regarding claim 2, Kumar as modified in view of Jebara teaches all the limitations of claim 1 as stated above. Further, Kumar as modified in view of Jebara teaches wherein in the solving of the MAP estimation problem of the CGM, a minimum cost flow problem is constructed using the aggregate data and the potentials, and the minimum cost flow problem is solved by the technique based on the discrete DC programming (Kumar section 3.4.1 Equations 3.10-3.13; section 3.4.2 Equation 3.14-3.15; minimum cost flow problem - Equation 3.14 subject to Equation 3.15).
Regarding claim 3, Kumar as modified in view of Jebara teaches all the limitations of claim 2 as stated above. Further, Kumar as modified in view of Jebara teaches wherein in the calculating of the MAP estimation solution, correction of a cost function on a network targeted by the minimum cost flow problem and calculation of an optimum solution of a minimum convex cost flow problem using a corrected cost function, by the technique based on the discrete DC programming, is repeated (Kumar section 3.4.1 “noting that all the marginals must be positive, a simple substitution … makes it convex … we further perform the following optimality preserving modifications … This is deliberate to simplify the CCCP iteration without changing the feasible parameter space”; section 3.4.2 “Thus it might appear that we may not be able to optimally solve the CCCP iteration. However, this is remedied by again substituting … back to the above problem resulting in … Equations 3.14-3.15”; section 3.5 including Algorithm 1; the calculation is repeated until convergence; corrected cost function - Equations 3.11-3.13 or Equations 3.14-3.15).
Regarding claim 5, it is directed to a non-transitory computer-readable recording medium storing a program that causes the computer to execute the estimation method according to claim 1. Claim 4 analysis applies equally to claim 5.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Wang et al. (NPL – “New Convex Relaxations for MRF Inference with Unknown Graphs”) related to estimating a MAP solution of a CGM using difference-of-convex programming similar to Kumar.
Sun et al. (NPL – “Message Passing for Collective Graphical Models”) generally related to estimating a MAP solution of a CGM using message passing algorithm. Sun et al. is cited in the IDS submitted on 04/05/2023.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Carlo Waje whose telephone number is (571)272-5767. The examiner can normally be reached 9:00-6:00 M-F.
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, James Trujillo can be reached at (571) 272-3677. 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.
/Carlo Waje/Examiner, Art Unit 2151 (571)272-5767
Prosecution Insights