Ex Parte Zhou

Board of Patent Appeals and Interferences

Apr 14, 2008

10186174 (B.P.A.I. Apr. 14, 2008)

UNITED STATES PATENT AND TRADEMARK OFFICE
____________________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
____________________

Ex parte MING ZHOU
____________________

Appeal 2007-2947
Application 10/186,1741
Technology Center 2600
____________________

Decided: April 14, 2008
____________________

Before KENNETH W. HAIRSTON, JOHN A. JEFFERY, and MARC S.
HOFF, Administrative Patent Judges.

HOFF, Administrative Patent Judge.

DECISION ON APPEAL

STATEMENT OF CASE
Appellant appeals under 35 U.S.C. § 134 from a Final Rejection of
claims 1, 4-8, and 11-15. We have jurisdiction under 35 U.S.C. § 6(b).
We affirm.
Appellant’s invention is directed to automatic retrieval of effective
example sentences based on text input provided by a user, for example a
user writing in a non-native language. Candidate example sentences are

1 Application filed June 28, 2002. The real party in interest is Microsoft
Corporation.
Appeal 2007-2947
Application 10/186,174

selected using a term frequency-inverse document frequency (TF-IDF)
algorithm. The selected example sentences are then re-ranked based upon
weighted editing distances between the selected candidate example
sentences and the input query sentence (Spec. 2-3).
Claims 1 and 15 are exemplary:
1. A method of retrieving example sentences from a collection of
sentences, the method comprising:
receiving an input query sentence;
selecting candidate example sentences for the input query sentence
from the collection of sentences using a term frequency-inverse
document frequency (TF-IDF) algorithm; and
re-ranking the selected candidate example sentences based
upon editing distances between the selected candidate example
sentences and the input query sentence, wherein editing
distance between the selected candidate example sentence and
the input query sentence is based on a minimum number of
operations required to change one of the selected candidate
example sentence and the input query sentence into the other of
the input query sentence and the candidate example sentence.

15 A system for retrieving example sentences from a collection of
sentences, the system comprising:
an input which receives a query sentence;
a term frequency-inverse document frequency (TF-IDF)
sentence retrieval component coupled to the input which selects
candidate example sentences for the query sentence from the
collection of sentences using a TF-IDF algorithm;
a weighted editing distance computation component, coupled to
the TF-IDF component, which calculates a separate weighted
editing distance for each selected candidate example sentence
as a function of terms in the candidate example sentence, and as
a function of weighted scores corresponding to the terms in the
candidate example sentence, wherein the weighted scores have
differing values based upon a part of speech associated with the
corresponding terms in the candidate example sentence; and
2
Appeal 2007-2947
Application 10/186,174

a ranking component, coupled to the weighted editing distance
computation component, which ranks the selected candidate
example sentences based upon the calculated separate weighted
editing distances for each candidate example sentence.

The prior art relied upon by the Examiner in rejecting the claims on
appeal is:
Liddy US 6,006,221 Dec. 21, 1999
Schabes US 6,424,983 B1 Jul. 23, 2002
Schalk US 6,922,669 B2 Jul. 26, 2005

Claims 1, 4, 8, and 11 stand rejected under 35 U.S.C. § 103(a) as
being unpatentable over Liddy in view of Schalk.
Claims 5-7 and 12-15 stand rejected under 35 U.S.C. § 103(a) as
being unpatentable over Liddy in view of Schalk and Schabes.
Appellant contends that the Examiner has failed to make out a prima
facie case of obviousness, with respect to claim 1, because (a) Schalk does
not teach re-ranking candidate example sentences based on editing distances
between candidate example sentences and an input query sentence (Br. 13)
and (b) Liddy does not teach re-ranking candidate example sentences based
on editing distance (Br. 15). With respect to claim 15, Appellant repeats the
arguments made with respect to claim 1, and further argues that Schabes
provides no teaching of using part of speech related weights in the
calculation of weighted editing distances for candidate example sentences.
Appellant also argues against the combinability of the applied references.
Rather than repeat the arguments of Appellant or the Examiner, we
make reference to the Brief and the Answer for their respective details.
3
Appeal 2007-2947
Application 10/186,174

ISSUES
There are two principal issues in the appeal before us.
The first issue is whether the Examiner erred in holding that Liddy in
combination with Schalk properly teaches or suggests re-ranking selected
candidate example sentences based upon editing distances between the
selected candidate example sentences and the input query sentence.
The second issue is whether the Examiner erred in holding that Liddy
in combination with Schalk and Schabes properly teaches or suggests
calculating weighted editing distances for each selected candidate example
sentence as a function of weighted scores corresponding to terms in the
candidate example sentence, wherein the weighted scores have differing
values based upon a part of speech associated with the corresponding terms.

FINDINGS OF FACT
The following Findings of Fact (FF) are shown by a preponderance of
the evidence.
The Invention
1. According to Appellant, he/she has invented a method and
system for automatic retrieval of effective example sentences based on text
input provided by a user, for example a user writing in a non-native
language (Spec. 2).
2. Candidate example sentences are selected using a term
frequency-inverse document frequency (TF-IDF) algorithm. The selected
example sentences are then re-ranked based upon weighted editing distances
4
Appeal 2007-2947
Application 10/186,174

between the selected candidate example sentences and the input query
sentence (Spec. 3).
3. In one embodiment, the weighted editing distances for each
candidate example sentence are calculated as a function of weighted scores,
which have differing values based upon a part of speech associated with
corresponding terms (Spec. 3-4).
Liddy
4. Liddy teaches document retrieval techniques that enable a user
to enter a natural language query in a desired one of a plurality of supported
languages and retrieve documents in at least one other language of the
plurality of supported languages (col. 2, ll. 43-48).
5. Appellant admits that Liddy ranks candidate matches based on
a distance between vectors (Br. 13; Liddy, col. 18, ll. 39-42 and col. 19, ll.
58-59).
Schalk
6. Schalk teaches method and system for accurately recognizing
spoken digit strings (col. 1, ll. 55-56).
7. A recognition engine receives a spoken digit string and, using a
known speech recognition engine, generates a list of hypothesized digit
strings ranked by likelihood of matching the spoken digit string (col. 2, ll.
37-53).
8. Each hypothesized string is then analyzed for compliance with
a given constraint. The first hypothesized string in the list satisfying the
constraint is selected as the recognized string (col. 2, ll. 57-65).
5
Appeal 2007-2947
Application 10/186,174

9. Schalk teaches the use of the Levenshtein distance algorithm to
determine editing distance between two strings, which is the minimum
number of substitutions, deletions, and insertions required to transform one
string into the other (col. 5, ll. 41-51).
Schabes
10. Schabes teaches a system for correcting the spelling and
grammar of words, using finite state machines. For each word in a text
sequence, the invention provides a list of alternative words ranked according
to a context of the text sequence, and uses the list to correct words in the text
(col. 2, ll. 35-41).
11. Schabes teaches determining alternative words for at least one
word in the input text, evaluating possible alternatives using a scoring
system which includes different weights for different parts of speech (col.
20, ll. 15-26).
PRINCIPLES OF LAW
In rejecting claims under 35 U.S.C. § 103, the Examiner bears the
initial burden of establishing a prima facie case of obviousness. In re
Piasecki, 745 F.2d 1468, 1472 (Fed. Cir. 1984). The Examiner can satisfy
this burden by showing some articulated reasoning with some rational
underpinning to support the legal conclusion of obviousness. KSR Int’l. v.
Teleflex Inc., 127 S. Ct. 1727, 1741 (2007) (citing In re Kahn, 441 F.3d 977,
988 (Fed. Cir. 2006)). Only if this initial burden is met does the burden of
coming forward with evidence or argument shift to the Appellant. Piasecki,
745 F.2d at 1472. Thus, the Examiner must not only assure that the requisite
findings are made, based on evidence of record, but must also explain the
6
Appeal 2007-2947
Application 10/186,174

reasoning by which the findings are deemed to support the Examiner’s
conclusion.
“[W]hen a patent ‘simply arranges old elements with each performing
the same function it had been known to perform’ and yields no more than
one would expect from such an arrangement, the combination is obvious.”
KSR Int’l v. Teleflex Inc., 127 S. Ct. 1727, 1740 (2007) (quoting Sakraida v.
AG Pro, Inc., 425 U.S. 273, 282 (1976)).
References within the statutory terms of 35 U.S.C. § 102 qualify as
prior art for an obviousness determination only when analogous to the
claimed invention. In re Clay, 966 F.2d 656, 658 (Fed. Cir. 1992). Two
separate tests define the scope of analogous prior art: (1) whether the art is
from the same field of endeavor, regardless of the problem addressed and,
(2) if the reference is not within the field of the inventor's endeavor, whether
the reference still is reasonably pertinent to the particular problem with
which the inventor is involved. In re Deminski, 796 F.2d 436, 442 (Fed. Cir.
1986); see also In re Wood, 599 F.2d 1032, 1036 (CCPA 1979) and In re
Bigio, 381 F.3d 1320 (Fed. Cir. 2004).
One cannot show nonobviousness by attacking references individually
where the rejections are based on combinations of references. In re Keller,
642 F.2d 413, 425 (CCPA 1981). The test of obviousness is what the
combined teachings would have suggested to those of ordinary skill in the
art. Id. at 425.
7
Appeal 2007-2947
Application 10/186,174

ANALYSIS
Claims 1, 4, 8, and 11
Because Appellant states that claims 4 and 11 should be allowable for
the same reasons they advance for claims 1 and 8, we will treat these claims
together. We select claim 1 as representative of this group, pursuant to our
authority under 37 C.F.R. § 41.37(c)(1)(vii).
Appellant argues that the combination of Liddy and Schalk fails to
teach or fairly suggest the claimed “re-ranking the selected candidate
example sentences based upon editing distances between the selected
candidate example sentences and the input query sentence” (Br. 12;
emphasis added). Appellant argues that one of ordinary skill in the art would
not look to the speech recognition art of Schalk to provide a candidate
sentence ranking solution (Br. 11); that Liddy provides no teaching that the
distance between vectors is an editing distance (Br. 13); and that Schalk does
not teach computation of an editing distance relative to an input query (Br.
13)2.
Without explicitly saying so, Appellant appears to be arguing that the
combination of Liddy and Schalk is improper because Schalk is not
analogous prior art. As discussed supra, the determination whether a
reference is analogous to the claimed invention is a two-pronged inquiry: (1)
whether the art is from the same field of endeavor, regardless of the problem
addressed and, (2) if the reference is not within the field of the inventor's
endeavor, whether the reference still is reasonably pertinent to the particular

2 Appellant also argues that Schabes fails to teach this claim limitation.
Because the Examiner’s rejection does not cite Schabes, we need not reach
this argument.
8
Appeal 2007-2947
Application 10/186,174

problem with which the inventor is involved. In re Deminski, supra. Because
the invention is directed to providing example sentences in response to user
text input (FF 1), while Schalk is directed to automatic recognition of spoken
digit strings (FF 6), Appellant appears to be correct that Schalk is not from
the same field of endeavor as the instant invention. With respect to the
second prong of the analogous art inquiry, Appellant here is involved with
the problem of identifying appropriate example sentences in response to user
input, or put another way, finding “good” matches for the user input in a
database (FF 1). Schalk is involved with the problem of properly identifying
spoken digit strings, i.e., identifying the best match between the spoken user
input and representations of known digits (FF 7). We recognize that Schalk
also performs a subsequent step of testing hypothesized digit strings against
a knowledge-based recognition constraint, such as a checksum, in order to
arrive at a recognized digit string (FF 8), but that does not detract from
Schalk’s overall teaching. We therefore find that Schalk is reasonably
pertinent to the particular problem with which Appellant is involved.
Appellant, after admitting that Liddy ranks candidate matches based
on a distance between vectors (Br. 13); argues that Liddy provides no
teaching that said distance between vectors is an editing distance (id.). The
Examiner concedes that Liddy does not teach the concept of editing distance
(Ans. 5), relying on Schalk to supply the missing teaching (Ans. 5-6; FF 9).
Appellant’s argument that Schalk does not teach computation of an editing
distance relative to an input query is not persuasive. The Examiner does not
rely on Schalk to teach computation of an editing distance relative to an
input query, but looks to Schalk only for the concept of editing distance per
9
Appeal 2007-2947
Application 10/186,174

se, i.e. the minimum number of “corrections” (substitutions + deletions +
insertions) required to perform the transformation (FF 9). Appellant’s
argument against Schalk individually is further unpersuasive because one
cannot show nonobviousness by attacking references individually where the
rejections are based on combinations of references. In re Keller, supra.
We concur in the Examiner’s stated motivation, and conclude that it
would have been obvious to combine Liddy and Schalk because the asserted
combination would contribute to achieving more robust database-matching
(Ans. 6). We note Appellant’s discussion of Ruiz v. A.B. Chance Co. (Br. 9-
10), but because we do not find error in the Examiner’s motivation to
combine Liddy and Schalk, we need not reach Appellant’s argument
whether the nature of the problem to be solved suggests the combination.
We also find Appellant’s reliance on In re Ratti (Br. 11) to be unpersuasive,
because as noted supra, the Examiner relies on Schalk only for the concept
of “editing distance” per se, rather than its specific implementation in the
Schalk device.
We therefore do not find error in the Examiner’s rejection of claims 1,
4, 8, and 11 under 35 U.S.C. § 103.
Claims 5-7 and 12-15
We select claim 15 as representative of this group, pursuant to our
authority under 37 C.F.R. § 41.37(c)(1)(vii). Appellant argues that the
Examiner’s combination of Liddy, Schalk, and Schabes fails to teach or
fairly suggest the claimed invention, because Schabes provides no teaching
or suggestion of using part-of-speech related weights in the calculation of
weighted editing distances for candidate example sentences (Br. 17).
10
Appeal 2007-2947
Application 10/186,174

The Examiner relies on Schabes to teach the claim limitation “wherein
the weighted scores have differing values based upon a part of speech
associated with the corresponding terms in the candidate example sentence”
(Ans. 10), rather than the calculation of weighted editing distances as
asserted by Appellant. We agree with the Examiner that Schabes teaches
such part-of-speech weighting (FF 11). We concur with the Examiner’s
rationale and conclude that it would have been obvious to modify Liddy and
Schalk to include such part-of-speech weighting to make sure that
insignificant words do not interfere with the matching of the input query to
the document (Final Rej. 14). We further find Appellant’s argument
unpersuasive as constituting an attack on the references individually (see In
re Keller, supra). To the extent Appellant relies on the arguments made with
reference to claims 1 and 8 (Br. 18-19), we consider those arguments
unpersuasive as well, since we affirm the rejection of claims 1 and 8, supra.
We do not find error in the Examiner’s rejection of claims 5-7 and 12-
15 under 35 U.S.C. § 103.
CONCLUSION OF LAW
We conclude that Appellant has not shown that the Examiner erred in
rejecting claims 1, 4-8, and 11-15. Claims 1, 4-8, and 11-15 are not
patentable.
DECISION
The Examiner’s rejection of claims 1, 4-8, and 11-15 is affirmed.
No time period for taking any subsequent action in connection with
this appeal may be extended under 37 C.F.R. § 1.136(a)(1)(iv).

11
Appeal 2007-2947
Application 10/186,174

AFFIRMED

eld

WESTMAN CHAMPLIN (MICROSOFT CORPORATION)
SUITE 1400
900 SECOND AVENUE SOUTH
MINNEAPOLIS MN 55402-3319
12