# US 2019/0377792 A1 · Graph representations for identifying a next word

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0377792 A1
- Document ID: US20190377792A1
- Status: Published application
- Kind: A1
- Application number: 16/022,001
- Filed: 2018-06-28
- Published: 2019-12-12
- Earliest claimed: 2018-06-08
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Minjia Zhang; Xiaodong Liu; Wenhan Wang; Jianfeng Gao; Yuxiong He
- Web page: https://patentgrep.com/patent/US20190377792A1

## CPC

- G06F 40/30: Semantic analysis
- G06N 3/084: Backpropagation, e.g. using gradient descent
- G06F 16/3347: {using vector based model}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06N 3/044: Recurrent networks, e.g. Hopfield networks
- G06N 3/0442: characterised by memory or gating, e.g. long short-term memory [LSTM] or gated recurrent units [GRU]
- G06N 3/0455: Auto-encoder networks; Encoder-decoder networks
- G06N 3/048: Activation functions
- G06N 3/09: Supervised learning
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 5/022: Knowledge engineering; Knowledge acquisition
- G06N 3/082: modifying the architecture, e.g. adding, deleting or silencing nodes or connections
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Systems, methods, and computer-executable instructions for approximating a softmax layer are disclosed. A small world graph that includes a plurality of nodes is constructed for a vocabulary of a natural language model. A context vector is transformed. The small world graph is searched using the transformed context vector to identify a top-K hypothesis. A distance from the context vector for each of the top-K hypothesis is determined. The distance is transformed to an original inner product space. A softmax distribution is computed for the softmax layer over the inner product space of the top-K hypothesis. The softmax layer is useful for determining a next word in a speech recognition or machine translation.

## Claims

### Claim 1

A method for approximating a softmax layer, the method comprising operations performed using an electronic processor, the operations comprising:
constructing a small world graph comprising a plurality of nodes for a vocabulary of a natural language model (NLM);
transforming a context vector using an inner product preserving transformation;
searching the small world graph using the transformed context vector to identify a top-K hypothesis for a next word;
determining a distance from the context vector for each of the top-K hypothesis;
transforming the distance to an original inner product space;
computing a softmax distribution for the softmax layer over the inner product space of the top-K hypothesis for the next word;
storing the softmax distribution; and
identifying the next word based on the top-K hypothesis.

### Claim 2 (depends on 1)

The method of claim 1, wherein constructing a small world graph comprising a plurality of nodes comprises for each word in the vocabulary:
inserting a node into the small world graph as one of the plurality of nodes;
connecting the node to a plurality of nearest neighbor nodes;
selecting a random long range node; and
connecting the node to the random long range node.

### Claim 3 (depends on 2)

The method of claim 2, wherein the long range node is not a nearest neighbor node.

### Claim 4 (depends on 2)

The method of claim 2, further comprising:
determining Euclidian distances between the node and other nodes within the small world graph; and
selecting the nearest neighbor nodes based on the determined Euclidean distances.

### Claim 5 (depends on 1)

The method of claim 1, wherein searching the small world graph using the transformed context vector to identify the top-K hypothesis comprises:
storing candidate nearest neighbor nodes in a queue, wherein a size of the queue is set to a predetermined value; and
stopping the search when a number of distance calculations reaches a predetermined count.

### Claim 6 (depends on 1)

The method of claim 1, wherein the small world graph comprises a number of layers.

### Claim 7 (depends on 1)

The method of claim 1, further comprising selecting the next word in a sentence from the vocabulary based on the softmax distribution, wherein the context vector is based on words prior to the next word in the sentence.

### Claim 8 (depends on 7)

The method of claim 7, further comprising storing the next word.

### Claim 9

A system for approximating a softmax layer, the system comprising:
an electronic processor:
a memory including instructions that configured the electronic processor to:
construct a small world graph comprising a plurality of nodes for a vocabulary of a natural language model (NLM);
transform a context vector using an inner product preserving transformation;
search the small world graph using the transformed context vector to identify a top-K hypothesis for a next word;
determine a distance from the context vector for each of the top-K hypothesis;
transform the distance to an original inner product space;
compute a softmax distribution for the softmax layer over the inner product space of the top-K hypothesis for the next word; and
identify the next word based on the top-K hypothesis.

### Claim 10 (depends on 9)

The system of claim 9, wherein to construct a small world graph comprising a plurality of nodes, the electronic processor is further configured to for each word in the vocabulary:
insert a node into the small world graph as one of the plurality of nodes;
connect the node to a plurality of nearest neighbor nodes;
select a random long range node; and
connect the node to the random long range node.

### Claim 11 (depends on 10)

The system of claim 10, wherein the electronic processor is further configured to:
determine Euclidian distances between the node and other nodes within the small world graph; and
select the nearest neighbor nodes based on the determined Euclidean distances.

### Claim 12 (depends on 11)

The system of claim 11, wherein the long range node is not a nearest neighbor node.

### Claim 13 (depends on 9)

The system of claim 9, to search the small world graph using the transformed context vector to identify the top-K hypothesis, the electronic processor is further configured to:
store candidate nearest neighbor nodes in a queue, wherein a size of the queue is set to a predetermined value; and
stop the search when a number of distance calculations reaches a predetermined count.

### Claim 14 (depends on 9)

The system of claim 9, wherein the small world graph comprises a number of layers.

### Claim 15 (depends on 9)

The system of claim 9, wherein the electronic processor is further configured to select the next word in a sentence from the vocabulary based on the softmax distribution, wherein the context vector is based on words prior to the next word in the sentence.

### Claim 16 (depends on 15)

The system of claim 15, wherein the electronic processor is further configured to store the next word.

### Claim 17

A computer-readable storage medium storing computer-executable instructions for approximating a softmax layer, the stored instructions comprising:
instructions to construct a small world graph comprising a plurality of nodes for a vocabulary of a natural language model (NLM);
instructions to transform a context vector using an inner product preserving transformation;
instructions to search the small world graph using the transformed context vector to identify a top-K hypothesis for a next word;
instructions to determine a distance from the context vector for each of the top-K hypothesis;
instructions to transform the distance to an original inner product space;
instructions to compute a softmax distribution for the softmax layer over the inner product space of the top-K hypothesis for the next word; and
instructions to identify the next word based on the top-K hypothesis.

### Claim 18 (depends on 17)

The computer-readable storage medium of claim 17, wherein the instructions to construct a small world graph comprising a plurality of nodes comprises, for each word in the vocabulary:
instructions to insert a node into the small world graph as one of the plurality of nodes;
instructions to connect the node to a plurality of nearest neighbor nodes;
instructions to select a random long range node; and
instructions to connect the node to the long range node.

### Claim 19 (depends on 18)

The computer-readable storage medium of claim 18, wherein the instructions further comprise:
instructions to determine Euclidian distances between the node and other nodes within the small world graph; and
instructions to select the nearest neighbor nodes based on the determined Euclidean distances.

### Claim 20 (depends on 19)

The computer-readable storage medium of claim 19, wherein the long range node is not a nearest neighbor node.
