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 .
Status of the Claims
Claims 1-3, 6-8, 10-12 and 15-19 are pending for examination.
Claims 1, 10 and 17 are independent Claims.
Claims 1-3, 6-8, 10-12 and 15-19 are rejected under 35 U.S.C. §103.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-3, 6-8, 10-12 and 15-19 is/are rejected under 35 U.S.C. 103 as being unpatentable over Interlandi (U.S. 20220051104 hereinafter Interlandi) in view of Tago et al. (U.S. 2010/0036815 hereinafter Tago) in further view of Crawford et al. (U.S. 7,831,526 hereinafter Crawford).
As Claim 1, Interlandi teaches a computer system for facilitating processing within a computing environment, the computer system comprising:
a memory (Interlandi (¶0129 line 3, fig. 11 item 1104), system memory); and
a processing circuit in communication with the memory (Interlandi (¶0129 line 2-3, fig. 11 item 1102), processor circuit), wherein the computer system is configured to perform a method, the method comprising:
inflating, by the processing circuit, an trained source decision tree to establish inflated decision tree (Interlandi (¶0057 line 1-2, fig. 4 step 404), one or more dummy nodes are inserted to convert an unbalanced tree into a balanced tree. Applicant specification (¶0065 line 1-2) specifies that “trained decision trees” are typically not fully-populated to the constructed maximum depth), the establishing including inserting one or more phantom decision nodes into the source decision tree to obtain the inflated decision tree (Interlandi (¶0057 line 1-2, fig. 4 step 404), one or more dummy nodes are inserted to convert an unbalanced tree into a balanced tree) and adjusting one or more leaf node tree depth position to a maximum depth of the inflated decision tree (Interlandi (¶0058 line 1-9), system adjusts decision tree to a balanced tree);
based on the inflating, ascertaining, by the processing circuit, adjusted decision node data and adjusted leaf node data for the inflated decision tree (Interlandi (¶0058), system evaluates leaf node and decision node), the ascertaining including adjusting respective path vectors through the inflated decision tree to obtain for each leaf node of a plurality of leaf nodes of the inflated decision tree a respective, predetermined path vector through the inflated decision tree (Interlandi (¶058 line 9-14), leaf node with a depth Dk<D will be pushed to depth D (predetermined path vector) by relacing Lk with a perfect sub-tree of depth D-Dk), the adjusted leaf node data including the respective, predetermined path vectors through the inflated decision tree of the plurality of leaf nodes (Interlandi (¶0058 line 1-9), system adjusts decision tree to a balanced tree)
for use by an inference accelerator in parallel processing the plurality of leaf nodes of a decision node result vector to determine which leaf node is selected (Interlandi (¶0028 line 7-12), “resulting in improved overall performance when deployed (e.g., by leveraging parallel processing capabilities of such accelerators when executing the neural network framework, in contrast to traditional ML models where a tree, or collection of trees, is typically traversed).” Interlandi (¶0057 line -10), “ML pipeline parser 302 may convert the unbalanced tree into a tree in all internal nodes have two children and all leaf nodes are at the same depth level.”); and
providing, by the processing circuit, the adjusted decision node data and the adjusted leaf node data to an inference accelerator absent to facilitate accelerated processing (Interlandi (¶0106 line 14-22), three sets of data structures (tensors) are created instead of the inflated decision tree. Information about left and right node is not relevant. “to facilitate accelerated processing” is intended use), the inference accelerator to determine, at least in part therefrom therefrom which leaf node of a plurality of leaf nodes of the inflated decision tree is selected (Interlandi (¶0090 last 4 lines and algorithm 1), tree inference is processed until a leaf node is reached).
Interlandi may not explicitly disclose:
wherein the adjusting respective path vectors comprises determining, for a leaf node, a string value to insert into the respective path vector based on a distance the leaf node descends pursuant to the adjusting one or more leaf node tree depth positions to the maximum depth of the inflated decision tree, and inserting the string value into that respective path vector to obtain the respective, predetermined path vector for the leaf node, and further inserting, for at least one other leaf node of the plurality of leaf nodes, a 'don't care' string at the same insertion position into its path vector, the 'don't care' string being same-sized as the determined string value;
Tago teaches:
wherein the adjusting respective path vectors comprises determining, for a leaf node, a string value to insert into the respective path vector based on a distance the leaf node descends pursuant to the adjusting one or more leaf node tree depth positions to the maximum depth of the inflated decision tree (Tago (¶0315, ¶0316 line 1-4), node B is at level 6, system adjust node B by select two character string to insert before B value ), and inserting the string value into that respective path vector to obtain the respective, predetermined path vector for the leaf node (Tago (¶0315, ¶0316 line 1-4), node B is at level 6, system adjust node B by select two character string to insert before B value ), and further inserting, for at least one other leaf node of the plurality of leaf nodes, a 'don't care' string at the same insertion position into its path vector, the 'don't care' string being same-sized as the determined string value (Tago (¶0315, ¶0316 line 1-4), node B is at level 6, system adjust node B by select two character string to insert before B value. “Don’t care” string such as “*” are inserted to the two positions of the string before B value);
Interlandi teaches a system/method to utilize parallel processing on a balanced tree in order to accelerate tree processing operation. Tago teaches to fill in missing mode with value in order to make all the decision tree the same length (balanced tree). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the dummy node of Interlandi instead be a string node taught by Tago, with a reasonable expectation of success. The motivation would be to “eliminating the need of deciding the number of digits of bit strings for comparison for every transaction-destination node and efficiently making a true/false decision” (Tago (¶0312 line 4-7)).
Interlandi in view of Tago may not explicitly disclose:
wherein the respective, determined path vectors each specify decision nodes and a path used to reach the corresponding leaf node
Crawford teaches:
wherein the respective, determined path vectors each specify decision nodes and a path used to reach the corresponding leaf node (Crawford (col. 4 line 57-62 and 65-67, col. 5 line 1-6, fig. 12), “input decision tree to a collection of independent Decision Chains (path vectors) having the same length: This entire Step 1 corresponds to Box 2 in the flowchart of FIG.12. A decision chain is a path from the root of the tree to a leaf node such that each node, except the root, has a single parent and each node, except a leaf, has a single child.” Crawford (col. 1 line 54-58, fig. 14B, fig. 15B), “"Job," "Income" and "Assets" are the variables on which conditions are defined. For example, if a customer satisfies the conditions, "Job=Business AND Income<$100K" AND "Assets>$200K," the conclusion leaf node reached is "Card=Bronze””)
Interlandi in view of Tago teaches the transforming of regular tree to balanced tree in order to accelerate tree traversing operation. Crawford suggests to make input tree a balanced decision tree by adding dummy “true” node into the input tree. Crawford suggests that the leaf node is the decision node. Also, all the decision chains, from the root node to the leaf node, is modified so that they are at the same length. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the dummy node of Interlandi in view of Tago instead decision chains taught by Crawford, with a reasonable expectation of success. The motivation would be to “creating a more comprehensible and compact representation of the original decision tree” (Crawford (col. 4 line 52-54)).
As Claim 2, besides Claim 1, Interlandi in view of Tago in further view of Crawford teaches wherein the source decision tree is a trained pruned decision tree (Interlandi (¶0057 line 1-2, fig. 4 step 404), one or more dummy nodes are inserted to convert an unbalanced tree into a balanced tree. Unbalanced tree is a pruned version of a balance tree).
As Claim 3, besides Claim 1, Interlandi in view of Tago in further view of Crawford teaches wherein the interference accelerator processing is accelerated, ate least in part, by the providing of the respective, predetermined path vectors through the inflated decision tree for each leaf node of the plurality of leaf nodes (Interlandi (¶0106 line 14-22), system processes faster without having to look up for finishing the left and right child node IDs), and by processing a decision node result vector by the plurality of leaf nodes in parallel (Interlandi (¶0028 line 7-11), leaf nodes are traversed in parallel).
As Claim 6, besides Claim 5, Interlandi in view of Tago in further view of Crawford teaches wherein the string value to insert is equivalent to a last entry in a fully-populated path table for that descended-level size (Interlandi (¶0058 line 1-9), system replicates the leaf nodes to make the tree a balanced tree).
As Claim 7, besides Claim 5, Interlandi in view of Tago in further view of Crawford teaches wherein the adjusting comprises determining an insertion position for the string value by identifying a last decision node in the path vector, and based on the last decision node being true, or the last decision node being at the end of the path, the insertion position is 1 position beyond the last decision node (Tago (¶0312 line 4-6, ¶0313 line 2-8), dummy node with “1” is added to the tree before the decision node).
As Claim 8, besides Claim 7, Interlandi in view of Tago in further view of Crawford teaches wherein based on the last decision node being false and other than the end of the path, the insertion position is 2 positions beyond the last decision node (Interlandi (¶0058), system replicates the leaf nodes to make the tree a balanced tree based on maximum depth. The dummy node could be at any position).
As Claims 10-12, the Claims are rejected for the same reasons as Claims 1-3, respectively.
As Claims 15-16, the Claims are rejected for the same reasons as Claims 7-8, respectively.
As Claims 17-19, the Claims are rejected for the same reasons as Claims 1-3, respectively.
Response to Arguments
As Claim 1, Applicant argues that Interlandi does not explicitly disclose “path vectors” that represent the path through decision nodes (second paragraph of page 10 in the remarks).
PNG
media_image1.png
117
638
media_image1.png
Greyscale
Applicant’s arguments are moot because new reference Crawford (figures 14B, 15B) teaches the limitation(s).
As Claim 1, Applicant argues that Interlandi does not explicitly disclose amended limitation “determing … a string value to insert into the respective path vector based on a distance the leaf node descends …” (second paragraph of page 11 in the remarks).
PNG
media_image2.png
311
649
media_image2.png
Greyscale
Applicant’s arguments are moot because new reference Crawford (figures 14B, 15B) teaches path vectors and the insertion of dummy node into the path vectors. Tago suggests the use of string characters to indicate distance between nodes.
As Claim 1, Applicant argues that Interlandi in view of Tago does not disclose “a coordinated insertion across multiple leaf nodes” because Tago just show insertion at one position and not a coordinated string insertion across multiple leaf node path vectors (last paragraph of page 11 in the remarks).
PNG
media_image3.png
110
640
media_image3.png
Greyscale
PNG
media_image4.png
60
643
media_image4.png
Greyscale
Applicant’s arguments are moot because new reference Crawford (figures 14B, 15B) teaches path vectors and the insertion of dummy node into the path vectors. Tago suggests the use of string characters to indicate distance between the nodes and the leaf node. Therefore, Crawford in view of Tago teaches the coordination between path vectors.
As Claim 1, Applicant argues that motivation to combine Interlandi and Tago is improper because Tago’s purpose is fundamentally different form the claimed invention’s purpose (second paragraph of page 12 in the remarks).
PNG
media_image5.png
261
651
media_image5.png
Greyscale
Applicants’ arguments are not persuasive because Tago provides the motivation to combine. Tago’s motiviation does not have to be similar to applicants’ purpose for the combination to take place.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to NHAT HUY T NGUYEN whose telephone number is (571)270-7333. The examiner can normally be reached M-F: 12:00-8:00 EST.
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, Viker Lamardo can be reached on 571-270-5871. 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.
/NHAT HUY T NGUYEN/Primary Examiner, Art Unit 2147
Prosecution Insights