Large-scale classification in neural networks using hashing

Patent metadata

Field	Value
Publication number	US-10049305-B2
Application number	US-201715656192-A
Country	US
Kind code	B2
Filing date	Jul 21, 2017
Priority date	Dec 19, 2014
Publication date	Aug 14, 2018
Grant date	Aug 14, 2018

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for classification using a neural network. One of the methods for processing an input through each of multiple layers of a neural network to generate an output, wherein each of the multiple layers of the neural network includes a respective multiple nodes includes for a particular layer of the multiple layers: receiving, by a classification system, an activation vector as input for the particular layer, selecting one or more nodes in the particular layer using the activation vector and a hash table that maps numeric values to nodes in the particular layer, and processing the activation vector using the selected nodes to generate an output for the particular layer.

First claim

What is claimed is:

1. A method for processing an input through each of a plurality of layers of a neural network to generate an output, wherein each of the plurality of layers of the neural network comprises a respective plurality of nodes, the method comprising, for a particular layer of the plurality of layers:
determining, by a classification system, one or more hash codes of an activation vector that is input for the particular layer;
selecting one or more nodes in the particular layer using the one or more hash codes of the activation vector as input to a lookup function for a hash table that maps hash codes of activation vectors to data for weight values for nodes in the particular layer, the selecting comprising:
determining, for at least some of the one or more hash codes, an entry in the hash table at an index having a value that is the same as the hash code; and
determining, for each of the entries in the hash table, one or more weight value vectors that are identified by the entry in the hash table at the index having a value that is the same as the hash code, wherein each of the one or more weight value vectors is for a corresponding one of the selected nodes; and

generating an output for the particular layer by combining the weight values for the selected nodes with the activation vector, the generating comprising:
combining, for each of the selected nodes, the corresponding weight value vector with the activation vector.

2. The method of claim 1 , wherein determining, for each of the entries in the hash table, the one or more weight value vectors that are identified by the entry in the hash table at the index having a value that is the same as the hash code comprises:
determining, for each of the entries in the hash table, one or more node identifiers that are included in the entry in the hash table at the index having a value that is the same as the hash code, wherein each of the node identifiers in the one or more node identifiers corresponds to one of the selected nodes, wherein the data for the weight values for nodes in the particular layer comprises the one or more node identifiers; and
determining, for each of the selected nodes using the corresponding node identifier, the one or more weight value vectors for the selected node.

3. The method of claim 2 , wherein determining, for each of the selected nodes using the corresponding node identifier, the one or more weight value vectors for the selected node comprises requesting, from a parameter database, the one or more weight value vectors for the selected node.

4. The method of claim 1 , wherein determining the one or more weight value vectors that are identified in the entry in the hash table at the index having a value that is the same as the hash code comprises determining, for at least some of the entries in the hash table, the one or more weight value vectors that are included in the entry in the hash table at the index having a value that is the same as the hash code, wherein the data for the weight values for nodes in the particular layer comprise the one or more weight value vectors.

5. The method of claim 1 , wherein combining the weight values for the selected nodes with the activation vector comprises multiplying the activation vector with the weight values.

6. The method of claim 1 , wherein:
the activation vector comprises a vector of real number values;
determining the one or more hash codes of the activation vector that is input for the particular layer comprises:
converting each of the real number values in the activation vector to binary values to create a binary vector;
determining a plurality of portions of the binary vector; and
converting, for each of the portions of the binary vector, the binary values in the respective portion into an integer; and

selecting the one or more nodes in the particular layer using the one or more hash codes of the activation vector as input to the lookup function for the hash table that maps hash codes to data for weight values for nodes in the particular layer comprises selecting, using the integers as input to the lookup function for the hash table, the weight values for nodes in the particular layer.

7. A system comprising one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
determining one or more hash codes of an activation vector that is input for a particular layer of a neural network;
selecting one or more nodes in the particular layer using the one or more hash codes of the activation vector as input to a lookup function for a hash table that maps hash codes of activation vectors to data for weight values for nodes in the particular layer, the selecting comprising:
determining, for at least some of the one or more hash codes, an entry in the hash table at an index having a value that is the same as the hash code; and
determining, for each of the entries in the hash table, one or more weight value vectors that are identified by the entry in the hash table at the index having a value that is the same as the hash code, wherein each of the one or more weight value vectors is for a corresponding one of the selected nodes; and

generating an output for the particular layer by combining the weight values for the selected nodes with the activation vector, the generating comprising:
combining, for each of the selected nodes, the corresponding weight value vector with the activation vector.

8. The system of claim 7 , wherein determining, for each of the entries in the hash table, the one or more weight value vectors that are identified by the entry in the hash table at the index having a value that is the same as the hash code comprises:
determining, for each of the entries in the hash table, one or more node identifiers that are included in the entry in the hash table at the index having a value that is the same as the hash code, wherein each of the node identifiers in the one or more node identifiers corresponds to one of the selected nodes, wherein the data for the weight values for nodes in the particular layer comprises the one or more node identifiers; and
determining, for each of the selected nodes using the corresponding node identifier, the one or more weight value vectors for the selected node.

9. The system of claim 8 , wherein determining, for each of the selected nodes using the corresponding node identifier, the one or more weight value vectors for the selected node comprises requesting, from a parameter database, the one or more weight value vectors for the selected node.

10. The system of claim 7 , wherein determining the one or more weight value vectors that are identified in the entry in the hash table at the index having a value that is the same as the hash code comprises determining, for at least some of the entries in the hash table, the one or more weight value vectors that are included in the entry in the hash table at the index having a value that is the same as the hash code, wherein the data for the weight values for nodes in the particular layer comprise the one or more weight value vectors.

11. The system of claim 7 , wherein combining the weight values for the selected nodes with the activation vector comprises multiplying the activation vector with the weight values.

12. The system of claim 7 , wherein:
the activation vector comprises a vector of real number values;
determining the one or more hash codes of the activation vector that is input for the particular layer comprises:
converting each of the real number values in the activation vector to binary

Assignees

• Google Llc

Inventors

• Vijayanarasimhan Sudheendra
• Yagnik Jay

Classifications

• G06N3/082 Primary

  modifying the architecture, e.g. adding, deleting or silencing nodes or connections · CPC title

• G06F18/24

  Classification techniques · CPC title

• G06N3/04

  Architecture, e.g. interconnection topology · CPC title

• G06N3/08 Primary

  Learning methods · CPC title

• G06N3/0495

  Quantised networks; Sparse networks; Compressed networks · CPC title