Ex Parte Cantin

Patent Trial and Appeal Board

Jun 14, 2016

13174441 (P.T.A.B. Jun. 14, 2016)

UNITED STA TES p A TENT AND TRADEMARK OFFICE
APPLICATION NO. FILING DATE
13/174,441 06/30/2011
70426 7590 06/16/2016
IBM AUSTIN IPLA W (DL)
DeLizioLaw
C/O DELIZIO LAW, PLLC
15201 MASON ROAD, SUITE 1000-312
CYPRESS, TX 77433
FIRST NAMED INVENTOR
Jason F. Cantin
UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
Address: COMMISSIONER FOR PATENTS
P.O. Box 1450
Alexandria, Virginia 22313-1450
www .uspto.gov
ATTORNEY DOCKET NO. CONFIRMATION NO.
A US920110051US1 1847
EXAMINER
BEJCEK II, ROBERT H
ART UNIT PAPER NUMBER
2129
NOTIFICATION DATE DELIVERY MODE
06/16/2016 ELECTRONIC
Please find below and/or attached an Office communication concerning this application or proceeding.
The time period for reply, if any, is set in the attached communication.
Notice of the Office communication was sent electronically on above-indicated "Notification Date" to the
following e-mail address( es):
USPTO@DELIZIOLA W.COM
USPT02@DELIZIOLA W.COM
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
BEFORE THE PATENT TRIAL AND APPEAL BOARD
Ex parte JASON F. CANTIN1
Appeal2015-000807
Application 13/174,441
Technology Center 2100
Before JASON V. MORGAN, JOSEPH P. LENTIVECH, and
MICHAEL J. ENGLE, Administrative Patent Judges.
ENGLE, Administrative Patent Judge.
DECISION ON APPEAL
Appellant appeals under 35 U.S.C. § 134(a) from a final rejection of
claims 9-24, which are all of the claims pending in the application. We
have jurisdiction under 35 U.S.C. § 6(b ).
We AFFIRM-IN-PART.
Technology
The application is related to using speculation to overcome stalls or
failures in iterative computing such as evolutionary algorithms. Spec.
i-fi-1 18-20, Abstract. "Evolutionary algorithms use techniques loosely based
on Darwinian evolution and biological mechanisms to evolve solutions to
1 According to Appellant, the real party in interest is International Business
Machines Corporation. App. Br. 1.
1
Appeal2015-000807
Application 13/174,441
tough design problems." Id. if 3. An evolutionary algorithm run on a
computer "starts with a randomly generated population of solutions, and
uses sexual recombination, crossover, mutation, and the Darwinian
principles of natural selection to create new, more fit solutions." Id.
Representative Claims
Claims 9 and 14 are representative and reproduced below with key
limitations emphasized:
9. A computer program product for speculative evolutionary
computing, the computer program product comprising:
a non-transitory computer readable storage medium
having computer usable program code embodied therewith, the
computer usable program code comprising a computer usable
program code configured to:
compute fitness values for a first generation of a
first sub-population of a plurality of sub-populations,
wherein a population of candidate solutions for an
optimization problem was previously divided into the
plurality of sub-populations, wherein the population of
candidate solutions was created for an iterative computing
process in accordance with an evolutionary algorithm to
identify a most fit candidate solution for the optimization
problem;
determine a speculative ranking of the first
generation of the first sub-population prior to the fitness
values being computed for all candidate solutions in the
first generation of the first sub-population; and
generate a next generation of the first sub-
population based, at least in part, on the speculative
ranking prior to completion of computation of the fitness
values for the first generation of the first sub-population.
14. A computer program product for speculative evolutionary
computing, the computer program product comprising:
a non-transitory computer readable storage medium
having computer usable program code embodied therewith, the
2
Appeal2015-000807
Application 13/174,441
computer usable program code comprising a computer usable
program code configured to:
receive fitness values for a first generation of a first
sub-population of a plurality of subpopulations, wherein a
population of candidate solutions for an optimization
problem was previously divided into the plurality of sub-
populations, wherein the population of candidate solutions
was created for an iterative computing process in
accordance with an evolutionary algorithm to identify a
most fit candidate solution for the optimization problem;
determine whether the first generation of the first
sub-population does not satisfy a termination criterion for
the iterative computing processing;
determine whether the first generation corresponds
to a later iteration of the iterative computing process than
a second generation of a second sub-population of the
plurality of sub-populations;
determine whether a difference between the first
generation and the second generation does not exceed a
termination speculation threshold; and
generate a third generation of the first sub-
population responsive to a determination that the
difference between the first generation and the second
generation does not exceed the termination speculation
threshold, wherein the computer usable program code is
configured to generate the third generation of the first
subpopulation based, at least in part, on the fitness values.
Rejections on Appeal
Claims 14--18, 22, and 24 stand rejected under 35 U.S.C. § 102(b) as
being anticipated by Branke et al. (US 2004/0210545 Al; Oct. 21, 2004).
Final Act. 11.
Claim 9 stands rejected under 35 U.S.C. § 103(a) as being
unpatentable over the combination of Branke and Chen (US 2004/0044633
Al; Mar. 4, 2004). Final Act. 15.
3
Appeal2015-000807
Application 13/174,441
Claims 10 and 11 stand rejected under 35 U.S.C. § 103(a) as being
unpatentable over the combination of Branke; Chen; Zhu (US 2005/0044052
Al; Feb. 24, 2005); and Mitrevski et al., Prediction and Speculation
Techniques in !LP, Proceedings of the 22nd Int'l Conf. on Information
Technology Interfaces, pp. 67-72 (2000). Final Act. 17.
Claims 12 and 13 stand rejected under 35 U.S.C. § 103(a) as being
unpatentable over the combination of Branke, Chen, and Sidorowich (US
6,532,076 Bl; Mar. 11, 2003). Final Act. 19.
Claims 19, 20, and 23 stand rejected under 35 U.S.C. § 103(a) as
being unpatentable over the combination of Branke and Koza et al. (US
6,532,453 B 1; Mar. 11, 2003). Final Act. 21.
Claim 21 stands rejected under 35 U.S.C. § 103(a) as being
unpatentable over the combination of Branke, Koza, and Sander et al. (US
7,937,569 Bl; May 3, 2011). Final Act. 24.
Rejections Not on Appeal
Claims 14, 18, and 22 were rejected under 35 U.S.C. § 112 second
paragraph as being indefinite. Final Act. 10. However, the Examiner
subsequently withdrew that rejection. Ans. 2.
Claims 14--21 stand rejected on the ground of non-statutory
obviousness-type double patenting over claims 1-8 of co-pending
Application No. 13/592,851. Final Act. 3. Similarly, claims 22 and 23
stand rejected on the ground of non-statutory obviousness-type double
patenting over claims 1 and 6 of the same co-pending application. Final
Act. 7. Application No. 13/592,851 has since been abandoned and thus the
Examiner's non-statutory obviousness-type double patenting rejections are
moot.
4
Appeal2015-000807
Application 13/174,441
ISSUES
1. Did the Examiner err in finding Branke discloses "determine
whether the first generation corresponds to a later iteration of the iterative
computing process than a second generation of a second sub-population of
the plurality of sub-populations," as recited in claim 14?
2. Did the Examiner err in finding Branke discloses "determine
whether a difference between the first generation and the second generation
does not exceed a termination speculation threshold," as recited in claim 14?
3. Did the Examiner err in finding Chen teaches or suggests
"determine a speculative ranking of the first generation of the first sub-
population prior to the fitness values being computed for all candidate
solutions in the first generation of the first sub-population," as recited in
claim 9?
4. Did the Examiner err in finding Chen teaches or suggests
"generate a next generation of the first sub-population based, at least in part,
on the speculative ranking prior to completion of computation of the fitness
values for the first generation of the first sub-population," as recited in claim
9?
ANALYSIS
Claims 14-24
Branke discloses a method and system for implementing evolutionary
algorithms. Branke at Title. In Branke, a central process delegates portions
of work to separate computers, each called a peripheral process. Id. ,-r 54,
Abstract. The central process divides a population of individual candidates
5
Appeal2015-000807
Application 13/174,441
into subpopulations of similar fitness, the central process gives each
peripheral process a subpopulation, and the peripheral processes then evolve
their subpopulations until a termination condition is reached, after which the
subpopulation is merged back into the central pool to repeat the process. Id.
i-f 29, Abstract; see generally i-fi-151-60. The "termination condition" of each
peripheral process could be, for example, "after a predetermined number of
generations have occurred" (also known as the number of "iterations") or
when the fitness of each subsequent generation "is not significantly
improving." Id. i-fi-157, 4. Similarly, the central process has a "stop criteria"
to stop all processing, which may involve "stopping immediately upon
meeting the stop criteria"; "waiting for all peripheral processes to finish"; or
"waiting until most (75%) do so." Id. i-f 52. Similar to the termination
condition of the peripheral processes, the stop condition of the central
process can be based on "the total number of evolution cycles" (i.e.,
iterations) or when "the fitness of the current population cease to improve
significantly." Id. i-f 70.
a) "determine whether the first generation corresponds to a later
iteration of the iterative computing process than a second
generation of a second sub-population of the plurality of sub-
populations"
Claim 14 requires program code configured to "determine whether the
first generation corresponds to a later iteration of the iterative computing
process than a second generation of a second sub-population of the plurality
of sub-populations," but Appellant argues "Branke does not disclose
comparing where two subpopulations are in an iterative computing process"
because "[t]he only comparison made is between the fitness levels of
candidate solutions." App. Br. 16-17. "The mere fact that differences may
6
Appeal2015-000807
Application 13/174,441
exist between two subpopulations does not mean that any determination is
made based on those differences." Id. at 17.
We are not persuaded. We agree with the Examiner (Ans. 4) that
Branke discloses "processing each subpopulation with the evolutionary
algorithm until a termination condition is reached" (Branke i-f 29) and
provides an example of a termination condition as "a predetermined number
of generations have occurred." Id. i-f 57. The number of generations is the
number of iterations. Id. i-f 4 ("each iteration is known as a 'generation'").
Branke also discloses a stop condition for the central process that waits until
75% of the peripheral processes have finished. Id. i-f 52. We agree with the
Examiner that the central process determining that at least 75% of the
peripheral processes have completed a predetermined number of a
generations (i.e., iterations) constitutes determining that one or more
generations correspond to a later iteration (i.e., the 75% that have reached
the predetermined number of iterations) than the one or more generations
that have not reached the predetermined number of iterations.
Appellant's contrived example involving a counter is not persuasive
both because it does not track the claim language as written and because
even in Appellant's example, the central process still knows which
peripheral processes have completed the predetermined number of iterations.
See Reply Br. 3 ("When each peripheral process stops and notifies the
central process") (emphasis added); Branke i-fi-158, 72.
Accordingly, we find that Branke discloses "determine whether the
first generation corresponds to a later iteration of the iterative computing
process than a second generation of a second sub-population of the plurality
of sub-populations," as recited in claim 14.
7
Appeal2015-000807
Application 13/174,441
b) "determine whether a difference between the first generation and
the second generation does not exceed a termination speculation
threshold"
Appellant also contends Branke fails to disclose program code to
"determine whether a difference between the first generation and the second
generation does not exceed a termination speculation threshold" because
"[a]t no point does the Examiner point to anything in Branke that describes
any form of speculation." App. Br. 19. Here, we agree with Appellant. The
Examiner finds that "under [the] broadest reasonable interpretation in light
of the specification" the termination speculation threshold "can be any
predicted, suggested, guessed, or speculated termination threshold," yet then
proceeds to identify only a "termination threshold" in Branke, not a
termination speculation threshold. Ans. 5; Final Act. 12. Accordingly, we
do not sustain the Examiner's rejection of claim 14.
Independent claim 22 contains the identical disputed limitations as
claim 14 so its rejection is reversed for the same reason. Dependent claims
15-21, 23, and 24 stand with their respective independent claims.
Since we agree with at least one of the arguments advanced by
Appellant for claims 14--24, we need not reach the merits of Appellant's
other arguments for claims 14--24.
Claims 9-13
Chen relates to techniques for genetic algorithms (Chen i-f 4), which
are a type of evolutionary algorithms. Spec. i-f 2; Branke i-f 3. Evolutionary
algorithms involve determining the "fitness" of potential solutions using a
fitness function. Spec. i-fi-117-18; Branke i-f 3. However, "evaluating the
'fitness' of the chromosomes of a population has proved to be time
consuming." Chen i-f 6; see also Branke i-f 11. Chen proposes a way to
8
Appeal2015-000807
Application 13/174,441
reduce computation time by using a trained neural network "to predict
fitness values for any arbitrary set of solution chromosomes without having
to perform actual fitness algorithm computations." Chen i-f 19.
a) "determine a speculative ranking of the first generation of the first
sub-population prior to the fitness values being computed for all
candidate solutions in the first generation of the first sub-
population"
Appellant argues Chen fails to teach or suggest program code to
"determine a speculative ranking of the first generation of the first sub-
population prior to the fitness values being computed for all candidate
solutions in the first generation of the first sub-population" because "Chen
does not disclose determining any kind of ranking, speculative or not." App.
Br. 24. Appellant further argues the Examiner "conveniently fails to cite
anything for the 'prior to' language." Id. at 25.
We are not persuaded. Chen discloses "the network is able to predict
fitness values"; "the neural network evaluates the fitness of the
chromosomes by a predictive methodology"; and "[t]he neural network's
ability to approximate correct results ... make the neural network much
faster." Chen i-f 19 (emphasis added). The Examiner correctly "views
predicting and speculating as synonymous without an explicit definition to
the contrary" (Ans. 9), and Appellant has offered no such contrary
definition. Appellant's argument that "Chen does not actually predict fitness
values" (Reply Br. 6) is not sufficiently supported by Appellant's briefs and
is contradicted by Chen itself, which says it uses "predictive" and
"approximate" methodologies "without having to perform actual fitness
algorithm computations." Chen i-f 19.
9
Appeal2015-000807
Application 13/174,441
Appellant's argument that "Chen actually substitutes a neural network
for a normal fitness function" (Reply Br. 6) also is not tied to the claim as
written and is contradicted by Chen itself, which discloses embodiments
using first the predictive methodology then the more time-intensive
analytical algorithms. Chen i-f 19; Ans. 8.
We also agree with the Examiner that using predicted fitness values to
eliminate "particularly unfit chromosomes" ranks solutions as fit vs. unfit.
Ans. 8. Appellant's own brief admits, "The results, however, are still ranked
based on the fitness values generated by the neural network." Reply Br. 7.
Finally, we agree with the Examiner that the determination of a
speculative ranking occurs "prior to the fitness values being computed for all
candidate solutions" because Chen expressly says the ad hoc analytical
algorithms can be used after the predictive methodology eliminates unfit
candidates (Chen i-f 19) and "[i]t would make no sense to predict fitness
values after the actual values were known." Ans. 8.
Accordingly, we find that Chen teaches or suggests "determine a
speculative ranking of the first generation of the first sub-population prior to
the fitness values being computed for all candidate solutions in the first
generation of the first sub-population," as recited in claim 9.
b) "generate a next generation of the first sub-population based, at
least in part, on the speculative ranking prior to completion of
computation of the fitness values for the first generation of the first
sub-population"
Appellant also contends Chen fails to teach or suggest program code
to "generate a next generation of the first sub-population based, at least in
part, on the speculative ranking prior to completion of computation of the
fitness values for the first generation of the first sub-population." Appellant
10
Appeal2015-000807
Application 13/174,441
first relies on the same arguments used for the "determine a speculative
ranking" limitation, which we do not find persuasive for the same reasons.
Appellant next argues that "prior to" modifies the verb "generate"
(App. Br. 27), whereas the Examiner finds "prior to" modifies "speculative
ranking." Ans. 9-10. Appellant provides "basic grammar rules" in support
if its assertion but provides no source or evidence supporting such "rules."
Reply Br. 8. For example, Appellant contends "'prior to ... ' only applies
to verbs" because "[a] prepositional phrase that describes when something
happens can only apply to a verb." Id. Yet prepositions involving time
regularly modify nouns, such as "the weather in January"; "the night before
last"; or "our dog prior to this one." The Examiner's interpretation may not
be the only reasonable interpretation, but given the similarity of the "prior
to" clause here to that in the "determine a speculative ranking prior to"
limitation discussed above, we are not persuaded that the Examiner's
interpretation is unreasonable under the broadest reasonable interpretation
standard. Appellant remains free to amend the claims to clarify any desired
intent, but we review claims as written and § 112 "puts the burden of precise
claim drafting squarely on the applicant." In re Morris, 127 F.3d 1048, 1056
(Fed. Cir. 1997).
Thus, we find Chen teaches or suggests "generate a next generation of
the first sub-population based, at least in part, on the speculative ranking
prior to completion of computation of the fitness values for the first
generation of the first sub-population," as recited in claim 9.
Accordingly, we sustain the Examiner's rejection of claim 9, and
claims 10-13, which Appellant argues are patentable for similar reasons.
See App. Br. 29; 37 C.F.R. § 41.37(c)(l)(iv) (2013).
11
Appeal2015-000807
Application 13/174,441
DECISION
For the reasons above, we affirm the Examiner's decision rejecting
claims 9-13. We reverse the Examiner's decision rejecting claims 14--24.
TIME TO RESPOND
No time period for taking any subsequent action in connection with
this appeal may be extended under 37 C.F.R. § 1.136(a). See 37 C.F.R.
§ 41.50(±).
AFFIRMED-IN-PART
12