DETAILED ACTION
Status of Claims
Claim(s) 1-6, 8-13, and 15-20 are pending and are examined herein.
Claim(s) 1, 8, and 15 have been Amended. Claim(s) 7 and 14 previously Cancelled.
Claim(s) 1-6, 8-13, and 15-20 remain rejected under 35 U.S.C. §§ 112 and 103.
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 .
Continued Examination Under 37 CFR 1.114
A request for continued examination under 37 CFR 1.114, including the fee set forth in 37 CFR 1.17(e), was filed in this application after final rejection. Since this application is eligible for continued examination under 37 CFR 1.114, and the fee set forth in 37 CFR 1.17(e) has been timely paid, the finality of the previous Office action has been withdrawn pursuant to 37 CFR 1.114. Applicant's submission filed on 12/16/2025 has been entered.
Response to Amendment
The amendment filed on September 10, 2025 has been entered. Claims 1-6, 8-13, and 15-20 pending in the application. Applicant’s amendments to the claims have been fully considered and are addressed in the rejections below.
Response to Arguments
Applicant's arguments, with respect to the rejection under 35 U.S.C. § 103 filed on 12/16/2025 (see remarks Pp. 11-14) have been fully considered but are moot in view of the new grounds of rejection necessitated by amendments.
The examiner refers to the updated rejection under 35 U.S.C. § 103 for more details.
Claim Rejections - 35 USC § 112
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.
Claim(s) 1-20 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor, for pre-AIA the applicant regards as the invention.
Regarding Currently Amended Claim 1, the claim recites limitations that renders the scope of the claimed invention indefinite for the following reasons:
The claim recites that “the input data is processed in parallel within each of distinct pre-trained decision tree base learners via a graph traversal,” and then further recites that “the input data processed in parallel by walking in parallel each of the distinct pre-trained decision tree base learners until leaf nodes are reached;” lines 14-17. These recitations fail to clearly define the scope of the claimed parallel processing. Specifically, the first recitation indicates that processing occurs in parallel “within each” individual decision tree base learners, while the second recitation indicates that processing occurs in parallel across multiple distinct decision tree base learners. Thus, it is unclear whether the claim requires parallel processing within individual decision trees, parallel processing across multiple decision tress, or both. Accordingly, the scope of the claim is not clearly defined, and a person ordinary skill in the art cannot determine the metes and bounds of the claim. For examination, the claim limitation is broadly interpreted as graph traversal in a tree with multiple nodes and branches and the input data executed across multiple trees in parallel.
The claim further recites the limitations “repeatedly evaluating by the ensemble model an exit condition for interruption of the remaining machine learning tasks within each tree of the pre-trained decision tree base learners by computing a deterministic function ... wherein the deterministic function is associated with an arithmetic mean of values outputted by the pre-trained decision tree base learners ...” lines 19-27. The claim recitation is internally inconsistent with the claimed deterministic function. Specifically, the claim recites that the exit condition is evaluated “within each tree,” which suggest the evaluation is performed per decision tree base learner, while also reciting that the deterministic function comprises an arithmetic mean of values outputted by the pre-trained decision tree base learners, which defines an ensemble level aggregation across multiple decision base learners. As such, it is unclear whether the exit condition is evaluated individually within each tree, or the exit condition is evaluated at the ensemble level based on outputs from multiple trees. Accordingly, one of ordinary skill in the art would not be reasonably apprised by the scope of the deterministic function and the corresponding exit condition evaluation. For examination, the claim limitation is interpreted as the deterministic function is computed across outputs of multiple decision tree base learners, and the exit condition is evaluated at the ensemble level.
For at least the above reasons, claim 1 does not particularly point out and distinctly claim the invention and it therefore indefinite under 35 USC § 112(b).
Regarding Currently Amended Claims 8 and 15, the claims recite substantially similar limitations as those of claim 1 and are rejected for similar reasons and rationale.
Regarding dependent Claims 2-6, 9-13, and 16-20, dependent claims inherit the deficiencies of the respective parent claim.
Appropriate correction is required.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claim(s) 1-3, 5-6, 8-10, 12-13, 15-17, and 19-20 are rejected under 35 U.S.C. 103 as being unpatentable over Ruiz et al., (NPL: “Anytime Inference with Distilled Hierarchical Neural Ensembles.” (2020)) in view of Wang et al., (NPL: “Quit When You Can: Efficient Evaluation of Ensembles with Ordering Optimization.” (2018)), and further in view of Lettich et al. (NPL: "Parallel Traversal of Large Ensembles of Decision Trees." (2018)).
Regarding Currently Amended Claim 1,
Ruiz discloses the following:
A computer-implemented method of utilizing an ensemble model associated with a plurality of pre-trained decision … base learners to accelerate accelerating machine learning inferences performed by the ensemble model during an inference phase, and thereby save time and computer resources, the method comprising: (Ruiz, [Abstract] “Inference in deep neural networks can be computationally ex pensive, and networks capable of anytime inference are important in scenarios where the amount of compute or quantity of input data varies over time. In such networks the inference process can interrupted to provide a result faster, or continued to obtain a more accurate result. We propose Hierarchical Neural Ensembles (HNE), a novel framework to embed an ensemble of multiple networks in a hierarchical tree structure, sharing intermediate layers. In HNE we control the complexity of inference on-the-fly by evaluating more or less models in the ensemble.” [P. 1, Section: 1] “In particular, we focus on methods capable of any time inference, i.e. methods where the inference process can be interrupted for early results, or continued for more accurate results.”)
providing input data to an ensemble model, the ensemble model associated with a plurality of pre-trained decision … base learners, the plurality of pre-trained decision … base learners ready for performing machine-learning inferences without training the pre-trained decision … base learners; (Ruiz, [P. 3, Section: 3] “HNE embed an ensemble of deep networks computing an output
y
E
=
1
N
=
∑
n
=
1
N
F
n
(
x
;
θ
n
)
from an input x, where Fn is a network with parameters θn and N is the total number of models.” [P. 1, Section: 1] “In these situations, models must be able to scale the number of the operations on-the-fly de pending on the amount of available compute at any point in time. In particular, we focus on methods capable of any time inference, i.e. methods where the inference process can be interrupted for early results, or continued for more accurate results. This contrasts with other methods, where the accuracy-speed trade-off has be decided before the computation for inference starts. We address this problem by introducing Hierarchical Neural Ensembles (HNE). Inspired by ensemble learning (Breiman 1996), HNE embeds a large number of networks whose combined outputs provide a more accurate prediction than any individual model.”) [Examiner’s Note: The HNE provides input x to a pre-trained ensemble of N base learners F(x;θn) during inference without any further training. The HNE is mainly used during inference phase to accelerate the prediction results.]
starting by the ensemble model an execution of machine learning tasks by the plurality of pre-trained decision … base learners with a view to obtain respective task outcomes from execution of one or more of the plurality of pre-trained decision … base learners, whereby for each of the machine learning tasks each one of the pre-trained ... base learners executes utilizing at least a subset of the input data input into the ensemble model, the input data at least partially the same for each of the pre-trained ... base learners (Ruiz, [P. 1, Section: 1] “Figure 1: (Top) HNE shares parameters and computation in a hierarchical manner. Tree leafs represent separate models in the ensemble. Anytime inference is obtained via depth first traversal of the tree, and using at any given time the ensemble prediction of the N models evaluated so far. (Bottom) Hierarchical distillation leverages the full ensemble to supervise parts of the tree that are used in small ensembles.” [P. 3, Section: 3] “HNE embed an ensemble of deep networks computing an output
y
E
=
1
N
=
∑
n
=
1
N
F
n
(
x
;
θ
n
)
from an input x, where Fn is a network with parameters θn and N is the total number of models... each network is a composition of B + 1 functions, or “blocks” as
F
n
(
x
;
θ
n
)
=
f
θ
n
B
◦
·
·
·
◦
f
θ
n
1
◦
f
θ
n
0
(
x
)
, where each block
f
θ
n
b
(
·
)
is a set of layers with parameters
θ
n
b
... In order to reduce the computational complexity, we design HNE to share parameters and computation employing a binary tree structure, where each node of the tree represents a computational block. Each of the N = 2B paths from the root to a leaf represents a different model composed of B + 1 computational blocks. The first (root) computational block is shared among all models, and after each block the computational path is continued along two branches, each with a different set of parameters from the next block onward... See Figure 1 for an illustration. Therefore, for each block b there are K = 2b independent sets of parameters θb k. The parameters of an HNE composed of N = 2B models are collectively denoted as
Θ
=
{
θ
1
0
,
…
θ
1
:
2
b
b
,
…
,
θ
1
:
2
B
B
}
.”) [Examiner’s note: The HNE reference teaches execution of individual base learners networks to perform inference computation (i.e., image classification tasks), where individual outputs y represents task outcomes based on the input x. The HNE uses the same input x that is fed to all N base learner networks , which corresponds to the recitation of “input data at least partially the same for each base learner.”]
while the machine learning tasks execute ...., repeatedly evaluating by the ensemble model an exit condition for interruption of the remaining machine learning tasks within each tree of the pre-trained decision ... base learners by computing a deterministic function associated with the machine learning task outcomes obtained so far, the exit condition indicating that remaining machine learning tasks being executed by the pre-trained decision … base learners should be interrupted when an output value of the deterministic function indicate whether an inference result of the ensemble model has converged wherein the deterministic function is associated with an arithmetic mean of values outputted by the pre-trained decision tree base learners and the arithmetic mean ... to determine convergence, (Ruiz, [P. 1, Section: 1] “Figure 1: (Top) HNE shares parameters and computation in a hierarchical manner. Tree leafs represent separate models in the ensemble. Anytime inference is obtained via depth first traversal of the tree, and using at any given time the ensemble prediction of the N models evaluated so far. (Bottom) Hierarchical distillation leverages the full ensemble to supervise parts of the tree that are used in small ensembles.” [P. 3, Section: 3] “HNE embed an ensemble of deep networks computing an output
y
E
=
1
N
=
∑
n
=
1
N
F
n
(
x
;
θ
n
)
from an input x, where Fn is a network with parameters θn and N is the total number of models... each network is a composition of B + 1 functions, or “blocks” as
F
n
(
x
;
θ
n
)
=
f
θ
n
B
◦
·
·
·
◦
f
θ
n
1
◦
f
θ
n
0
(
x
)
, where each block
f
θ
n
b
(
·
)
is a set of layers with parameters
θ
n
b
... In order to reduce the computational complexity, we design HNE to share parameters and computation employing a binary tree structure, where each node of the tree represents a computational block. Each of the N = 2B paths from the root to a leaf represents a different model composed of B + 1 computational blocks. The first (root) computational block is shared among all models, and after each block the computational path is continued along two branches, each with a different set of parameters from the next block onward... See Figure 1 for an illustration. Therefore, for each block b there are K = 2b independent sets of parameters θb k. The parameters of an HNE composed of N = 2B models are collectively denoted as
Θ
=
{
θ
1
0
,
…
θ
1
:
2
b
b
,
…
,
θ
1
:
2
B
B
}
... In the case of HNE, this is achieved by evaluating only a subset of the paths from the root to the leafs, see Figure 1. More formally, we can choose any value b ∈ {0,1,...,B} and compute the ensemble output using a subset of N= 2b networks as
y
b
=
1
2
b
∑
n
=
1
2
b
F
(
x
;
θ
n
)
. (1) The evaluated subset of
N
=
2
b
networks is obtained by traversing the binary tree structure in a depth-first manner, where the first evaluated leaf model is always the same. Thus, we evaluate the first branch, as well as all the other
2
b
-
1
branches that share the last b blocks with this branch. See Figure 1... Fortunately, the evaluation of the different networks in the HNE can be parallelized by means of group convolutions, where different sets of input channels are used to compute an independent set of outputs, see Figure 2.”) [Examiner’s Note: The HNE implementation describes that models of the ensemble are evaluated in parallel batches using group of convolutions. The anytime stopping is evaluated and applied between batches. The averaging prediction outputs function of the multiple independent models of the ensemble, where the sum accumulates the individual task outcomes corresponds to the broader recitation of computing a deterministic function associated with the machine learning task outcomes obtained so far. The inference process of the ensemble can be interrupted for early results based on the evaluation result and the accuracy trad-off (i.e., convergence) described in 3.3 equation (5). The paper also describes that anytime inference is obtained via depth first traversal of the tree, and using at any given time the ensemble prediction of the N models evaluated so far. ] and
interrupting by the ensemble model the execution of the remaining machine learning tasks being executed by the pre-trained decision … base learners, if the exit condition evaluated last is fulfilled and the deterministic function indicates the inference result of the ensemble model has converged; and (Ruiz, [Abstract] “In such networks the inference process can interrupted to provide a result faster, or continued to obtain a more accurate result. We propose Hierarchical Neural Ensembles (HNE), a novel framework to embed an ensemble of multiple networks in a hierarchical tree structure, sharing intermediate layers. In HNE we control the complexity of inference on-the-fly by evaluating more or less models in the ensemble.” [P. 3, Section: 3] “the speed-accuracy trade-off can be controlled by choosing how many models to evaluate to ap proximate the full ensemble output. In the case of HNE, this is achieved by evaluating only a subset of the paths from the root to the leafs, see Figure 1. More formally, we can choose any value b ∈ {0,1,...,B} and compute the ensemble output using a subset of N= 2b networks as
y
b
=
1
2
b
∑
n
=
1
2
b
F
(
x
;
θ
n
)
. (1) The evaluated subset of
N
=
2
b
networks is obtained by traversing the binary tree structure in a depth-first manner, where the first evaluated leaf model is always the same. Thus, we evaluate the first branch, as well as all the other
2
b
-
1
branches that share the last b blocks with this branch. See Figure 1.”) [Examiner’s Note: The HNE implementation interrupt the execution of individual networks (i.e., pre-trained learners) and exit the inference process.]
returning the inference result of the ensemble model based on the obtained machine learning task outcomes obtained in at least one of the pre-trained decision ... base learners before interruption of the execution of the remaining machine learning tasks in remaining pre-trained decision ... base learners. (Ruiz, [Abstract] “In such networks the inference process can interrupted to provide a result faster, or continued to obtain a more accurate result. We propose Hierarchical Neural Ensembles (HNE), a novel framework to embed an ensemble of multiple networks in a hierarchical tree structure, sharing intermediate layers. In HNE we control the complexity of inference on-the-fly by evaluating more or less models in the ensemble.” [P. 1, Section: 1] “Figure 1: (Top) HNE shares parameters and computation in a hierarchical manner. Tree leafs represent separate models in the ensemble. Anytime inference is obtained via depth first traversal of the tree, and using at any given time the ensemble prediction of the N models evaluated so far. (Bottom) Hierarchical distillation leverages the full ensemble to supervise parts of the tree that are used in small ensembles.”) [Examiner’s Note: The HNE provides the prediction outputs of the ensemble from only a subset of models evaluated before interruption.]
As noted above, Ruiz teaches the HNE framework to embed an ensemble of multiple trained network (i.e., base learners) for inference, providing input x to the ensemble, parallel execution of the individual learners to perform inference on the input data, computing an arithmetic summation of outputs to evaluate the predictions obtained so far for early inference results, interrupting the inference process based on accuracy confidence (i.e., sufficient convergence, and returning the ensemble inference results including partial result, Ruiz does not appear to explicitly teach:
Ruiz does not appear explicitly define the individual pre-trained learners of the ensemble as “decision tee-based learners.”
Ruiz does not explicitly state the “exit condition” evaluation by comparing the arithmetic mean against a “decisive threshold” to determine convergence and trigger interruption of the remaining task.
Ruiz does not explicitly teach that “the input data is processed in parallel within each of distinct pre-trained decision tree base learners via a graph traversal” and “the input data processed in parallel by walking in parallel each of the distinct pre-trained decision tree base learners until leaf nodes are reached.”
However, Ruiz in view of Wang teaches the following:
providing input data to an ensemble model, the ensemble model associated with a plurality of pre-trained decision tree base learners, the plurality of pre-trained decision tree base learners ready for performing machine-learning inferences without training the pre-trained decision tree base learners; (Wang, [Abstract] “Given a classifier ensemble and a dataset, many examples may be confidently and accurately classified after only a subset of the base models in the ensemble is evaluated. Dynamically deciding to classify early can reduce both mean latency and CPU without harming the accuracy of the original ensemble. To achieve such gains, we propose jointly optimizing the evaluation order of the base models and early-stopping thresholds. Given a classifier ensemble and a dataset, many examples may be confidently and accurately classified after only a subset of the base models in the ensemble is evaluated. Dynamically deciding to classify early can reduce both mean latency and CPU without harming the accuracy of the original ensemble. To achieve such gains, we propose jointly optimizing the evaluation order of the base models and early-stopping thresholds... the proposed Quit When You Can (QWYC) algorithm can speed up average evaluation time by 1.8–2.7 times on even jointly trained ensembles...” [p.1. Section: 1] “We consider the problem of efficiently evaluating a binary classifier that can be expressed as an ensemble of T base models:... where each base model ft(x) ∈ R contributes a score. The ensemble may have been trained: • Independently: Each ft is trained individually, e.g., random forests [4]. • Sequentially: The
t
t
h
base model ft is trained taking into account base models f1, f2, ..., ft−1, e.g., boosted trees [11]. • Jointly: All base models {ft} are trained together, e.g., generalized additive models [14]or an ensemble of lattices [6].” [p.4, Section 2] “In this article, we take the ensemble as given, and propose a method for speeding up a given already-trained ensemble. Last, another strategy for fast evaluation of ensembles is to evaluate the base models in parallel.” [p.11, Section: 5.5] “A GBT ensemble model is an additive model where the output is the sum of T regression trees... When training the full ensemble, we perform hyperparameter optimization on a validation set over the number of base trees in the ensemble, the maximum depth of a single base tree, and the learning rate. We treat the evaluation cost of each base model as a constant ct = 1 for all t, which is a conservative assumption as the maximum depth of each base tree is bounded... This is a binary classification task where the objective is to predict whether or not a person’s income is greater than $50,000. The full ensemble has T = 500 base trees of maximum depth 5 and acts on a total of D = 14 features. We use the predefined train/test split provided in the repository.”) [Examiner’s Note: Wang explicitly teaches that the ensemble base learners are decision trees (GBT regression trees) that are already trained and ready for validation/optimization. The feature vector x is the input provided to the ensemble model and passed to each individual base model.]
starting by the ensemble model an execution of machine learning tasks by the plurality of pre-trained decision tree base learners with a view to obtain respective task outcomes from execution of one or more of the plurality of pre-trained decision tree base learners, (Wang, [p.4, Section 2] “In this article, we take the ensemble as given, and propose a method for speeding up a given already-trained ensemble. Last, another strategy for fast evaluation of ensembles is to evaluate the base models in parallel.” [p.4, Section: 3] “We take as given a linearly separable model f (x) : x ∈ RD → R such that f (x) = T t=1 ft(x),an expected time (or other cost) ct ∈ R+ to evaluate the tth base model ft(x) for t = 1,...,T, and a decision threshold β ∈ R for classifying f (x). We propose producing a fast classifier by optimizing the ordering of base models over the set of all permutations Π that map {1,2,...,T}→{1,2,...,T}, and over the positive and negative threshold vectors ϵ+,ϵ− ∈ RT to minimize the expected evaluation cost of a random sample X ∈ RD drawn from a data distribution PX, with a constraint specified as a percent α of samples that may be classified differently by the fast classifier compared to the full classifier f (x).”) [Examiner’s Note: Wang teaches that each base model evaluated by feeding the input x to produce task outcomes (i.e., scores). The accumulated sum represents the respective task outcomes. Wang also suggest that this evaluation process can performed by executing the base models of the ensemble in parallel.]
while the machine learning tasks execute in parallel utilizing the input data at least partially the same, repeatedly evaluating by the ensemble model an exit condition for interruption of the remaining machine learning tasks within each tree of the pre-trained decision tree base learners by computing a deterministic function associated with the machine learning task outcomes obtained so far, the exit condition indicating that remaining machine learning tasks being executed by the pre-trained decision tree base learners should be interrupted when an output value of the deterministic function indicates an inference result of the ensemble model has converged wherein the deterministic function is associated with an arithmetic mean of values outputted by the pre-trained decision tree base learners and the arithmetic mean is compared to a decisive threshold to determine convergence, (Wang, [P.2, Section: 1] “Specifically, we apply the following simple early stopping mechanism for a given example x: after evaluating the
r
t
h
ordered base model, if the accumulated sum
∑
t
=
1
r
f
t
(
x
)
is above the
r
t
h
early positive thresholdϵ+r , then the example is classified as the positive class, and the evaluation is stopped early (and vice-versa if the sum is below the
r
t
h
negative threshold ϵ−r ). If the running sum does not exceed an early stopping threshold, one continues on to evaluate the
r
+
1
t
h
base model.” [p.4, Section 2] “In this article, we take the ensemble as given, and propose a method for speeding up a given already-trained ensemble. Last, another strategy for fast evaluation of ensembles is to evaluate the base models in parallel.” [p.4, Section: 3] “We take as given a linearly separable model f (x) : x ∈ RD → R such that f (x) = T t=1 ft(x), an expected time (or other cost)
c
t
∈
R
+
to evaluate the tth base model
f
t
(
x
)
for
t
=
1
,
.
.
.
,
T
, and a decision threshold
β
∈
R
for classifying
f
(
x
)
. We propose producing a fast classifier by optimizing the ordering of base models over the set of all permutations
Π
that map
{
1,2
,
.
.
.
,
T
}
→
{
1,2
,
.
.
.
,
T
}
,
and over the positive and negative threshold vectors
ϵ
+
,
ϵ
-
∈
R
T
to minimize the expected evaluation cost of a random sample
X
∈
R
D
drawn from a data distribution
P
X
, with a constraint specified as a percent α of samples that may be classified differently by the fast classifier compared to the full classifier
f
(
x
)
... after evaluating t base models in the ordering π and with early-stopping decision threshold vectors
ϵ
+
and
ϵ
-
,and is 0 otherwise; and
Z
X
,
π
,
ϵ
+
,
ϵ
-
,
is a Bernoulli random variable that is 1 if the fast classification of X differs from the full evaluation classifier decision for X, and 0 otherwise.... Let
g
r
(
x
,
π
)
denote the accumulated sum (incomplete score) after r base models ordered as per
π
:
g
r
(
x
,
π
)
=
∑
t
=
1
r
f
π
t
x
. After evaluating the
r
t
h
base model for r ∈ {1,...,T}, an example x belongs to one of three mutually exclusive sets: the predicted positive set
P
r
:
=
{
x
|
g
r
(
x
,
π
)
>
ϵ
r
+
}
, the predicted negative set
N
r
:
=
{
x
|
g
r
x
,
π
<
ϵ
r
-
}
,, and the uncertain set
U
r
:
=
{
x
|
ϵ
r
-
≤
g
r
(
x
,
π
)
≤
ϵ
r
+
}
.Note
U
0
=
R
D
,
P
O
=
∅
,
N
0
=
∅
.
If
x
∈
P
r
o
r
x
∈
N
r
,, then the fast classifier classifies x as the positive or negative class, respectively, and we terminate the evaluation. Otherwise,
x
∈
U
r
, the classification decision is not yet uncertain, and we continue on to evaluate the
π
(
r
+
1
)
t
h
base model. Let
C
r
:
=
⋂
t
=
0
r
U
t
denote the set of samples that remain unclassified after evaluating the
r
t
h
base model.”) [Examiner’s Note: Wang teaches the early stopping mechanism (i.e., exit condition). The accumulated sum function is the deterministic function computed from task outcomes obtained so far (i.e., from r base models evaluated). The sum is compared after each model evaluation against thresholds (i.e., the arithmetic mean is compared to a decisive threshold to determine convergence). Wang also acknowledges that the prior art Fan et al. used averaged base models outputs (see section 5.4).]
interrupting by the ensemble model the execution of remaining machine learning tasks being executed by the pre-trained decision tree base learners, if the exit condition evaluated last is fulfilled and the deterministic function indicates the inference result of the ensemble model has converged; (Wang, [Abstract] “Given a classifier ensemble and a dataset, many examples may be confidently and accurately classified after only a subset of the base models in the ensemble is evaluated. Dynamically deciding to classify early can reduce both mean latency and CPU without harming the accuracy of the original ensemble. To achieve such gains, we propose jointly optimizing the evaluation order of the base models and early-stopping thresholds.” [P.2, Section: 1] “Specifically, we apply the following simple early stopping mechanism for a given example x: after evaluating the
r
t
h
ordered base model, if the accumulated sum
∑
t
=
1
r
f
t
(
x
)
is above the
r
t
h
early positive thresholdϵ+r , then the example is classified as the positive class, and the evaluation is stopped early (and vice-versa if the sum is below the
r
t
h
negative threshold ϵ−r ). If the running sum does not exceed an early stopping threshold, one continues on to evaluate the
r
+
1
t
h
base model.” [p.4, Section: 3] “We take as given a linearly separable model f (x) : x ∈ RD → R such that f (x) = T t=1 ft(x), an expected time (or other cost)
c
t
∈
R
+
to evaluate the tth base model
f
t
(
x
)
for
t
=
1
,
.
.
.
,
T
, and a decision threshold
β
∈
R
for classifying
f
(
x
)
. We propose producing a fast classifier by optimizing the ordering of base models over the set of all permutations
Π
that map
{
1,2
,
.
.
.
,
T
}
→
{
1,2
,
.
.
.
,
T
}
,
and over the positive and negative threshold vectors
ϵ
+
,
ϵ
-
∈
R
T
to minimize the expected evaluation cost of a random sample
X
∈
R
D
drawn from a data distribution
P
X
, with a constraint specified as a percent α of samples that may be classified differently by the fast classifier compared to the full classifier
f
(
x
)
... after evaluating t base models in the ordering π and with early-stopping decision threshold vectors
ϵ
+
and
ϵ
-
,and is 0 otherwise; and
Z
X
,
π
,
ϵ
+
,
ϵ
-
,
is a Bernoulli random variable that is 1 if the fast classification of X differs from the full evaluation classifier decision for X, and 0 otherwise.... Let
g
r
(
x
,
π
)
denote the accumulated sum (incomplete score) after r base models ordered as per
π
:
g
r
(
x
,
π
)
=
∑
t
=
1
r
f
π
t
x
. After evaluating the
r
t
h
base model for r ∈ {1,...,T}, an example x belongs to one of three mutually exclusive sets: the predicted positive set
P
r
:
=
{
x
|
g
r
(
x
,
π
)
>
ϵ
r
+
}
, the predicted negative set
N
r
:
=
{
x
|
g
r
x
,
π
<
ϵ
r
-
}
,, and the uncertain set
U
r
:
=
{
x
|
ϵ
r
-
≤
g
r
(
x
,
π
)
≤
ϵ
r
+
}
.Note
U
0
=
R
D
,
P
O
=
∅
,
N
0
=
∅
.
If
x
∈
P
r
o
r
x
∈
N
r
,, then the fast classifier classifies x as the positive or negative class, respectively, and we terminate the evaluation. Otherwise,
x
∈
U
r
, the classification decision is not yet uncertain, and we continue on to evaluate the
π
(
r
+
1
)
t
h
base model. Let
C
r
:
=
⋂
t
=
0
r
U
t
denote the set of samples that remain unclassified after evaluating the
r
t
h
base model.”) [Examiner’s Note: Wang teaches terminating the evaluation of remaining base models based on the early stopping mechanism once the accumulated sum meets the convergence threshold. This corresponds to the claimed step of interrupting remaining machine learning tasks when the exit condition is fulfilled.]
Ruiz and Wang are analogous art because they are from the same field of endeavor (i.e., machine learning), and their disclosure generally relates to optimizing ensemble-based models to speed up evaluation/inference while reducing computation time.
Accordingly, at the effective filing date, it would have been prima facie obvious to one ordinarily skilled in the art of machine learning to modify the proposed HNE anytime inference method of Ruiz to incorporate the joint optimization approach using decision base trees for early stopping as taught by Wang. One would have been motivated to make such a combination in order to efficiently evaluate a binary classifier that can be expressed as an ensemble of tree base models. Doing so would speed up a given already-trained ensemble (Wang [Abstract]).
While Ruiz in view of Wang teaches the parallel execution of the pre-trained decision trees to perform inference and evaluating the predictions to decide whether or not stop early. Ruiz in view of Wang does not appear to explicitly teach the parallel execution of the pre-trained decision tree base learners and walking in parallel each of the pre-trained decision tree base learners via graph traversal until leaf nodes are reached. Specifically, Ruiz in view of Wang does not appear to explicitly teach:
the input data is processed in parallel within each of distinct pre-trained decision tree base learners via a graph traversal, the input data processed in parallel by walking in parallel each of the distinct pre-trained decision tree base learners until leaf nodes are reached;
However, Lettich, in combination with Ruiz in view of Wang, teaches the following:
for each of the machine learning tasks each one of the pre-trained decision tree base learners executes utilizing at least a subset of the input data input into the ensemble model, the input data at least partially the same for each of the pre-trained decision tree base learners (Lettich, [Pp. 2-3, Section: 2] “Let us denote with T = {T0, T1, . . .} an ensemble of binary decision trees, and let Λ be the maximum number of leaves of each tree. Moreover, let x be the feature vector representing an input instance (e.g., a query-document pair in the LtR WSE scenario). Let F be the feature set, and let |F| be the number of dimensions of vector x. We use φ to refer to the φ−th feature, with x[φ] storing the value of feature fφ ∈ F. Moreover, let s(x) be the numerical score eventually computed for x by traversing T.”)
the input data is processed in parallel within each of distinct pre-trained decision tree base learners via a graph traversal, (Lettich, [Pp. 3-4, Section: 3] “QUICKSCORER PARALLELIZATION In the following we will focus our analysis on the parallelization of the mask computation step as the parallelization of the score computation step can be achieved with a straightforward parallel reduction. Given a set of query-document pairs, we want to investigate the following scoring parallelization strategies: • Inter-document parallelism: multiple documents are evaluated in parallel; • Intra-document parallelism: multiple features, trees, or nodes are evaluated in parallel; • Hybrid parallelism: combining the two strategies above.” [P. 4, Section: 4, Col. 1] “Inter-document parallelism represents the most natural source of parallelism that can be exploited in VQS, although the number of documents scored in parallel is bounded by the number of parallel ways of the AVX-256 extension. Both the mask computation and score computation steps of QS can be parallelized. During the first step, multiple documents can be tested against a given node condition, and their leafindexes updated in parallel. Similarly, the scores of multiple documents can be computed simultaneously during the second step. Inter-document parallelism requires to replicate the data structure leafindexes used to encode the exit leaves. VQS interleaves bitvectors of 8 different documents (256 bits) in consecutive memory locations, i.e., leafindexes[8h+i], ∀i = 7:0. This allows to update 8 leafindexes simultaneously with a single SIMD operation.” Further see Algorithm 4.) the input data processed in parallel by walking in parallel each of the distinct pre-trained decision tree base learners until leaf nodes are reached; (Lettich, [p. 2, Section: 2] “Branching decisions in internal nodes of a tree take the form of a Boolean test x[φ] ≤ γ, where γ is a real-valued threshold for feature fφ. The output of each decision tree Th ∈ T , i.e., its contribution to the score s(x), corresponds to the so-called exit leaf of Th, identified by traversing the tree with the input instance x... The traversal of a decision tree performed by QS can be viewed as the process of converting a bitvector leaf indexes [h],where all bits are initially set to1, to a final bitvector where the leftmost 1 identifies the exit leaf of the tree[15].” [Pp. 8-9, Section: 6.2] “First, the elements of leafindexes are initialized (line4) – we use the keyword parallel_thread to indicate that iterations of the loop are partitioned among the threads of the thread-block and executed in parallel... First, the vector leafindexes is partitioned among the threads of the thread-block (line 12) such that each thread accumulates in a private, local register the contributions of a subset of trees by identifying their exit leaves in leafindexes.” Further See Algorithm 4.) [Examiner’s Note: Lettich Quick Score strategy to parallelize the traversal of large ensembles of decision trees by walking each decision tree in parallel through its branching decision nodes (via Boolean test) until the exit leaf node is identified through leafindexes. The claimed “walking” is broadly interpreted as graph traversal in a tree with multiple branches.]
while the machine learning tasks execute in parallel utilizing the input data at least partially the same, repeatedly evaluating by the ensemble model an exit condition .... (Lettich, [Pp. 2-3, Section: 2] “The traversal of a decision tree performed by QS can be viewed as the process of converting a bitvector leafindexes[h], where all bits are initially set to 1, to a final bitvector where the leftmost 1 identifies the exit leaf of the tree [?].” [P. 4, Section: 3, Col. 3] “Regarding the score computation step, a trivial parallel add reduction is performed, after accessing in parallel the exit leaves of all trees in T , to retrieve their additive contributions to the final score of a given query-document pair.” [P. 7, Col. 2] “Model partition and allocation. We recall that QS adopts two main data structures besides the input vector D: • the model data structure, composed of the tuples (γ, mask, h) encoding the branch nodes of the forest T , and of leafvalues, the vector that stores the scores associated with the leaves of the trees in T ; • the output vectors leafindexes – one for each tree of the forest T; these are updated during the computation to eventually identify the exit leaves of the trees.”) [Examiner’s Note: Lettich discloses QuickScore algorithms to perform ensemble decision tree computation on input instances represented by a feature vector x. Each tree Th traverses its nodes using tests x[f] < g, updating pre-tree leafindexs[h], while all tree operate on the same input vector x. Inter-document parallelism processes multiple features in parallel within each tree, and the determination of exit leaves via leafindexs[h] provides an early exit condition. Accordingly, Lettich teaches parallel execution of pre-trained decision trees via graph traversal and identification of early exit node.]
Accordingly, at the effective filing date of the claimed invention, it would have been prima facie obvious to one of ordinary skill in the art to modify the combination of Ruiz and Wang to incorporate the Parallel Traversal of Large Ensembles of Decision Trees as taught by Lettich. One would have been motivated to make such a combination in order to speed up the traversal of large ensembles of regression trees, thereby obtaining machine-learnt models that are effective, fast, and scalable (Lettich [Abstract]).
Regarding Previously presented Claim 2, the combination of Ruiz, Wang, and Lettich teaches the elements of claim 1 as outlined above, and further teaches:
wherein, at starting execution of the machine learning tasks in order to obtain an inference result based on the input data, the machine learning tasks are grouped into disjoint subsets of the machine learning tasks in each of the pre-trained decision tree base learners. (Lettich, [P. 4, Col. 1] “Intra-Document Parallelism. The key idea behind this strategy is to partition the scoring of a single document into subtasks that can be executed in parallel. Consequently, intra-document parallelization aims at reducing the scoring latency of each document, which in turn has the effect of increasing the throughput. Subtasks can be naturally identified in QS by decomposing the work performed over features; more precisely, each subtask consists in processing the list of tuples ðg; mask; hÞ2N f associated with a single feature ff, and updating the corresponding leafindexes. Note that different tuples in N f, related to different features ff, may be associated with the same tree Th.” [P. 7, Col. 2] “Model partition and allocation. We recall that QS adopts two main data structures besides the input vector D: • the model data structure, composed of the tuples (γ, mask, h) encoding the branch nodes of the forest T , and of leafvalues, the vector that stores the scores associated with the leaves of the trees in T ; • the output vectors leafindexes – one for each tree of the forest T ; these are updated during the computation to eventually identify the exit leaves of the trees. ... Hence, rather than storing leafindexes into the global memory it is far more efficient to partition the model, as already discussed in Section 3. More precisely, T is partitioned into multiple tree-blocks T ⊆ T of size τ = |T|, where τ is chosen to be small enough to make the corresponding leafindexes fitting the amount of shared memory available per threadblock. ” [P. 8, Col. 1] “The GPU algorithm. GPU-QUICKSCORER (QSGPU), the GPU version of QUICKSCORER5 , is sketched in Algorithm 3. The algorithm starts by transferring the entire model from the host (CPU) memory to the GPU global memory (line 2). We note that the model is stored in a partitioned layout of disjoint tree-blocks T ⊆ T , and it is entirely loaded into the global memory (line 2). ... “) [Examiner’s Note: Lettich teaches partitioning the forest of decision trees into disjoint tree-blocks and assigning tasks to parallel threads. This reads on the claimed “grouped into disjoint subset” within the ensemble of decision tree learners.]
Regarding Previously presented Claim 3, the combination of Ruiz, Wang, and Lettich teaches the elements of claim 2 as outlined above, and further teaches:
wherein the deterministic function is computed upon completing each of successive ones of the subsets of the machine learning tasks in each of the pre-trained decision tree base learners. (Ruiz, [P. 1, Section: 1] “Figure 1: (Top) HNE shares parameters and computation in a hierarchical manner. Tree leafs represent separate models in the ensemble. Anytime inference is obtained via depth first traversal of the tree, and using at any given time the ensemble prediction of the N models evaluated so far. (Bottom) Hierarchical distillation leverages the full ensemble to supervise parts of the tree that are used in small ensembles.” [p. 3, Section: 3] “Given that the models in the ensemble can be evaluated sequentially, the speed-accuracy trade-off can be controlled by choosing how many models to evaluate to approximate the full ensemble output. In the case of HNE, this is achieved by evaluating only a subset of the paths from the root to the leafs, see Figure 1. More formally, we can choose any value b ∈ {0,1,...,B} and compute the ensemble output using a subset of N= 2b networks as
y
b
=
1
2
b
∑
n
=
1
2
b
F
(
x
;
θ
n
)
. (1) The evaluated subset of
N
=
2
b
networks is obtained by traversing the binary tree structure in a depth-first manner, where the first evaluated leaf model is always the same. Thus, we evaluate the first branch, as well as all the other
2
b
-
1
branches that share the last b blocks with this branch. See Figure 1)
Regarding Original Claim 5, the combination of Ruiz, Wang, and Lettich teaches the elements of claim 1 as outlined above, and further teaches:
wherein the deterministic function is repeatedly computed to obtain, each time, a characterization value of the inference result, and the characterization value obtained is compared to one or more reference values to obtain a comparison outcome, the latter determining an antecedent of the exit condition. (Wang, [P. 2, Section: 1] “we propose a combinatorial optimization problem that minimizes the average number of base models that need to be evaluated to achieve the same classification decision as the full classifier. We simultaneously optimize the 2T corresponding early decision threshold vectors {ϵ+,ϵ−}.” [Pp. 4-5, Section: 3] “after evaluating t base models in the ordering π and with early-stopping decision threshold vectors
ϵ
+
and
ϵ
-
,and is 0 otherwise; and
Z
X
,
π
,
ϵ
+
,
ϵ
-
,
is a Bernoulli random variable that is 1 if the fast classification of X differs from the full evaluation classifier decision for X, and 0 otherwise.... Let
g
r
(
x
,
π
)
denote the accumulated sum (incomplete score) after r base models ordered as per
π
:
g
r
(
x
,
π
)
=
∑
t
=
1
r
f
π
t
x
. After evaluating the
r
t
h
base model for r ∈ {1,...,T}, an example x belongs to one of three mutually exclusive sets: the predicted positive set
P
r
:
=
{
x
|
g
r
(
x
,
π
)
>
ϵ
r
+
}
, the predicted negative set
N
r
:
=
{
x
|
g
r
x
,
π
<
ϵ
r
-
}
,, and the uncertain set
U
r
:
=
{
x
|
ϵ
r
-
≤
g
r
(
x
,
π
)
≤
ϵ
r
+
}
.Note
U
0
=
R
D
,
P
O
=
∅
,
N
0
=
∅
.
If
x
∈
P
r
o
r
x
∈
N
r
,, then the fast classifier classifies x as the positive or negative class, respectively, and we terminate the evaluation. Otherwise,
x
∈
U
r
, the classification decision is not yet uncertain, and we continue on to evaluate the
π
(
r
+
1
)
t
h
base model. Let
C
r
:
=
⋂
t
=
0
r
U
t
denote the set of samples that remain unclassified after evaluating the
r
t
h
base model.”) [Examiner’s Note: the averaged function is iteratively computed and compared to reference values and the comparison outcome (Pr, Nr, Ur) determines the antecedent of the early stopping condition.]
Regarding Previously presented Claim 6, the combination of Ruiz, Wang, and Lettich teaches the elements of claim 5 as outlined above, and further teaches:
wherein each of the pre-trained decision tree base learners provided is designed to produce output values restricted to a same range of output values. (Wang, [P. 4, Section: 3.1] “After evaluating the rth base model, an example x belongs to one of three classes–positive, negative, or uncertain: …., then x is classified as a positive or negative class, respectively, and we terminate the evaluation at the rth step.” [P. 5, Section: 4.1] “Let St(i) be the maximal set of examples for which base model ft can make an early negative or early positive classification while satisfying the constraint when α = 0 and π(i) = t after a binary search over ǫ + i , ǫ − i (assuming no early stopping before reaching the ith base model). For i ≥ 1, St(i) ⊇ St(1).”)
Regarding Currently Amended Claim 8,
The claim recites substantially similar limitation as corresponding claim 1 and is rejected for similar reasons as claim 1 using similar teachings and rationale. Claim 1 is directed to a method, and claim 8 is directed to a computer program product.
Ruiz also teaches HNE implementation on a computer architecture see pages 10-11.
Regarding Previously presented Claim 9,
The claim recites substantially similar limitations as corresponding claim 2 and is rejected for similar reasons as claim 2 using similar teachings and rationale.
Regarding Previously presented Claim 10,
The claim recites substantially similar limitations as corresponding claim 3 and is rejected for similar reasons as claim 3 using similar teachings and rationale.
Regarding Original Claim 12,
The claim recites substantially similar limitations as corresponding claim 5 and is rejected for similar reasons as claim 5 using similar teachings and rationale.
Regarding Previously presented Claim 13,
The claim recites substantially similar limitations as corresponding claim 6 and is rejected for similar reasons as claim 6 using similar teachings and rationale.
Regarding Currently Amended Claim 15,
The claim recites substantially similar limitation as corresponding claim 1 and is rejected for similar reasons as claim 1 using similar teachings and rationale. Claim 1 is directed to a method, and claim 15 is directed to a computer system.
Ruiz also teaches HNE implementation and the experiments performed on a computer architecture (e.g., GPUs) see Section 4 and pages 10-11.
Regarding Previously presented Claim 16,
The claim recites substantially similar limitations as corresponding claim 2 and is rejected for similar reasons as claim 2 using similar teachings and rationale.
Regarding Previously presented Claim 17,
The claim recites substantially similar limitations as corresponding claim 3 and is rejected for similar reasons as claim 3 using similar teachings and rationale.
Regarding Previously presented Claim 19,
The claim recites substantially similar limitations as corresponding claim 5 and is rejected for similar reasons as claim 5 using similar teachings and rationale.
Regarding Previously presented Claim 20,
The claim recites substantially similar limitations as corresponding claim 6 and is rejected for similar reasons as claim 6 using similar teachings and rationale.
Claim(s) 4, 11 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over the combination of Ruiz, Wang, and Lettich as described above, and further in view of Basilico et al., (NPL: “COMET: A Recipe for Learning and Using Large Ensembles on Massive Data” (2011)).
Regarding Previously presented Claim 4, the combination of Ruiz, Wang, and Lettich teaches the elements of claim 1 as outlined above:
While Ruiz, Wang, and Lettich teaches the process of evaluating an early stopping for at least a subset of decision tree base learners during inference, the combination does not appear to explicitly teach:
wherein the exit condition is devised so that it can only be fulfilled if at least a predetermined number or a fraction of the machine learning tasks have been completed in one of the pre-trained decision tree base learners.
However, Basilico, in combination with Ruiz, Wang, and Lettich, teaches the limitation:
wherein the exit condition is devised so that it can only be fulfilled if at least a predetermined number or a fraction of the machine learning tasks have been completed in one of the pre-trained decision tree base learners. (Basilico, [P. 3, Section: B] “Initially all m models are in the unqueried set U. In each step, a model T is randomly chosen and removed from U to vote on x; the vote is added to the running tallies of how many votes each class has received. Based on the accumulated tallies and how many ensemble members have not yet voted, the stopping criterion decides if it is safe to stop and return the classification receiving the most votes. If it is not safe, a new ensemble member is drawn, and the process is repeated until it is safe to stop or all m ensemble members have been queried.” [Pp. 3-4, Section: C] “We propose Gaussian Lazy Ensemble Evaluation (GLEE), which uses the Gaussian distribution to infer a (1 − α) confidence interval around the observed mean pˆ. The interval is used to test the hypothesis that the unobserved proportion of positive votes p falls on the same side of 0.5 as pˆ (and consequently, that the current estimated classification agrees with the full ensemble’s classification). If 0.5 falls outside the interval, GLEE rejects the null hypothesis that p and pˆ are on different sides of 0.5 and terminates voting early. …, To ensure the Gaussian approximation is reasonable, GLEE only stops evaluation only once some minimum number of models have voted.”)
Accordingly, it would have been obvious to a person having ordinary skill in the art, before the effective filing date of the claimed invention, having the combination of Ruiz, Wang, and Lettich before them, to incorporate the Gaussian Lazy Ensemble Evaluation (GLEE) method as taught by Basilico. One would have been motivated to make such a combination in order to reduce evaluation cost by 100X or more. Doing so would provide a significant speed-up over evaluating the entire ensemble (Basilico [Abstract]).
Regarding Previously presented Claim 11,
The claim recites substantially similar limitations as corresponding claim 4 and is rejected for similar reasons as claim 4 using similar teachings and rationale.
Regarding Previously presented Claim 18,
The claim recites substantially similar limitations as corresponding claim 4 and is rejected for similar reasons as claim 4 using similar teachings and rationale.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SADIK ALSHAHARI whose telephone number is (703)756-4749. The examiner can normally be reached Monday - Friday, 9 a.m. 6 p.m. ET.
Examiner interviews are available via telephone, 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, Li Zhen can be reached on (571) 272-3768. 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.
/S.A.A./Examiner, Art Unit 2121
/Li B. Zhen/Supervisory Patent Examiner, Art Unit 2121
Prosecution Insights