US 6317707

Patent Overview

Title: Automatic clustering of tokens from a corpus for grammar acquisition
Patent No.: US6317707B1
Application No.: US09/207,326
Inventors: Srinivas Bangalore; Giuseppe Riccardi
Original Assignee: AT&T Inc.
Current Assignee (as listed): Nuance Communications Inc; AT&T Properties LLC
Priority/Filing Date: 1998-12-07
Publication (Grant) Date: 2001-11-13
Status (as listed): Expired – Lifetime (anticipated expiration 2018-12-07)
Classifications: G06F40/253 (grammatical analysis); G06F40/284 (lexical analysis, e.g. tokenisation); G06F18/24323 (tree-organised classifiers), among others.

Purpose. The patent concerns building linguistic models from a corpus of speech. Per the supplied text, prior clustering for language modeling induced classes to predict smoothed probabilities for rare or unseen events and "does not provide insight into language model of grammar." The disclosed method instead uses clustering to group words and/or phrases by lexical significance so the resulting clusters "provide an indicator of grammatical structure."

Plain-language scope. The method: (1) identifies high-frequency "context words" (e.g., a predetermined number such as 50); (2) for the remaining "input words," counts occurrences of predetermined relationships with context words (e.g., adjacency at −2, −1, +1, +2 positions), yielding frequency values such as f₁₁₁–f₁₁₄ for "Chicago" and "to"; (3) maps each input word to an N-dimensional frequency vector, N being a multiple of context words, input words, and relations; (4) grows clusters recursively, forming a hierarchical "cluster tree" with centroid and radius per node up to a "root cluster"; (5) cuts the tree at a predetermined line (e.g., the median of inter-cluster merge distances), discarding larger clusters; and (6) ranks remaining clusters by compactness. The text states Manhattan distance performed better than Euclidean or maximum metrics. The list of clusters is the grammatical model. The method applies to words, phrases, syllables, or phonemes, and to relationships beyond adjacency. The abstract adds that words in the same cluster possess the same lexical significancy.

Source: https://patents.google.com/patent/[US6317707](/patent/US6317707)/en

What the excerpt does not establish. It provides no claims text, no complete description (the description is explicitly marked an excerpt), no tables, no dependent-claim limitations, no experimental results beyond the cited tables, and no litigation or validity analysis. Claim scope, prosecution history, and the full specification are not established here.