Large-scale classification in neural networks using hashing

Patent metadata

Field	Value
Publication number	US-9721190-B2
Application number	US-201514933256-A
Country	US
Kind code	B2
Filing date	Nov 5, 2015
Priority date	Dec 19, 2014
Publication date	Aug 1, 2017
Grant date	Aug 1, 2017

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:
receiving, by a classification system, an activation vector as input for the particular layer;
computing a hash code for at least a portion of the activation vector;
determining, using a hash table that maps hash values to nodes in the particular layer, one or more most similar hash values in the hash table to the hash code of the portion of the activation vector;
selecting one or more nodes in the particular layer that correspond to the one or more most similar hash values, and
processing the activation vector using the selected nodes to generate an output for the particular layer.

2. The method of claim 1 , further comprising creating a modified activation vector by setting the values in the activation vector that correspond to the nodes that were not selected to zero, wherein processing the activation vector using the selected nodes to generate the output for the particular layer comprises processing the modified activation vector to generate the output for the particular layer.

3. The method of claim 1 , wherein the hash table stores, for each of the nodes of the particular layer, a respective hash of weight values of the node.

4. The method of claim 1 , wherein the hash table stores, for each of the nodes of the particular layer, a respective node identifier of the node.

5. The method of claim 1 , wherein the activation vector comprises real number values, the method comprising:
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, the binary values in the respective portion into an integer, wherein determining, using the hash table that maps hash values to nodes in the particular layer, one or more most similar hash values in the hash table to the hash code of the portion of the activation vector comprises determining, using the integers as input to the hash table, the one or more most similar hash values.

6. The method of claim 5 , wherein:
the integers comprise a first subset and a second, mutually exclusive subset; and
determining, using the integers as input to the hash table, the one or more most similar hash values comprises:
determining, for each of the integers in the first subset, that the hash table does not include a corresponding first entry for a node; and
determining, for each of the integers in the second subset, that the hash table includes a corresponding second entry for a node; and

selecting one or more nodes in the particular layer that correspond to the one or more most similar hash values comprises selecting the one or more nodes in the particular layer as the nodes identified by the second entries.

7. The method of claim 6 , wherein:
determining, for each of the integers in the first subset, that the hash table does not include a corresponding first entry for a node comprises determining, for at least some of the integers in the first subset, that the hash table does not include a corresponding first entry with a current time stamp.

8. The method of claim 7 , wherein the hash table comprises a plurality of node entries each of which include a hash value and at least one node identifier, the method comprising:
determining, for at least some output values in the output, an accuracy value of a respective output value; and
updating at least some of plurality of node entries in the hash table using the accuracy values by updating time stamps for a first node entry in the plurality of node entries for a particular node in the particular layer and not updating time stamps for a second node entry in the plurality of node entries that does not correspond to any nodes in the particular layer.

9. The method of claim 8 comprising:
determining, by the classification system, old entries in the hash table that have an old timestamp; and
removing the old entries from the hash table.

10. The method of claim 1 , wherein the particular layer comprises an output layer of the neural network, the method comprising:
determining a best output value from the output for the particular layer; and
using the best output value as output for the neural network.

11. The method of claim 10 , wherein:
the classification system comprises an image classification system; and
each of the nodes in the output layer corresponds to a respective object class, the method comprising:
receiving an image; and
using the image as input to the neural network, wherein using the best output value as output for the neural network comprises classifying an object in the image as belonging to the class corresponding to the node that generated the best output value.

12. The method of claim 11 wherein:
receiving the image comprises receiving, from a device, data identifying the image; and
using the image as input to the neural network comprises using, by the classification system on another device, the image as input to the neural network in response to receiving the data identifying the image.

13. 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:
receiving, by a classification system, an activation vector as input for a particular layer in a neural network;
computing a hash code for at least a portion of the activation vector;
determining, using a hash table that maps hash values to nodes in the particular layer, one or more most similar hash values in the hash table to the hash code of the portion of the activation vector;
selecting one or more nodes in the particular layer that correspond to the one or more most similar hash values; and
processing the activation vector using the selected nodes to generate an output for the particular layer.

14. The system of claim 13 , wherein the activation vector comprises real number values, the operations comprising:
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, the binary values in the respective portion into an integer, wherein determining, using the hash table that maps hash values to nodes in the particular layer, one or more most similar hash values in the hash table to the hash code of the portion of the activation vector comprises determining, using the integers as input to the hash table, the one or more most similar hash values.

15. The system of claim 14 , wherein:
the integers comprise a first subset and a second, mutually exclusive subset; and
determining, using the integers as input to the hash table, the one or more most similar hash values comprises:
determining, for each of the integers in the first subset, that the hash table does not include a corresponding first entry for a node; and
determining, for each of the integers in the second subset, that the hash table includes a corresponding second entry for a node; and

selecting one or more nodes in the particular layer that correspond to the one or more most similar hash values comprises selecting the one or more nodes in the particular layer as the nodes identified by the se

Assignees

• Google Inc

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