Large-scale classification in neural networks using hashing

Patent metadata

Field	Value
Publication number	US-2016180200-A1
Application number	US-201514933256-A
Country	US
Kind code	A1
Filing date	Nov 5, 2015
Priority date	Dec 19, 2014
Publication date	Jun 23, 2016
Grant date	—

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; 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.

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 selecting the one or more nodes comprises:
computing a hash code for at least a portion of the activation vector; determining one or more most similar hashes in the hash table to the hash code of the portion of the activation vector; and selecting the nodes corresponding to the one or more most similar hashes.

5 . 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.

6 . The method of claim 1 , wherein the activation vector comprises real number values, the method comprising:
converting each of the real numbers 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 selecting the nodes in the particular layer using the activation vector and the hash table comprises selecting the one or more nodes in the particular layer by using the integers as input to the hash table.

7 . The method of claim 6 , wherein:
the integers comprises a first subset and a second, mutually exclusive subset; and selecting the one or more nodes in the particular layer by using the integers as input to the hash table 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;
determining, for each of the integers in the second subset, that the hash table includes a corresponding second entry for a node; and
selecting the one or more nodes in the particular layer as the nodes identified by the second entries.

8 . The method of claim 7 , 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.

9 . The method of claim 8 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 the mappings in the hash table using the accuracy values by updating time stamps for a first node entry in the hash table for a particular node in the particular layer and not updating time stamps for a second node entry in the hash table that does not correspond to any nodes in the particular layer.

10 . The method of claim 9 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.

11 . 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.

12 . The method of claim 11 , 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.

13 . The method of claim 12 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.

14 . 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 the operations comprising:
receiving, by a classification system, an activation vector as input for a particular layer in a neural network;
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.

15 . The system of claim 14 , wherein selecting the one or more nodes comprises:
computing a hash code for at least a portion of the activation vector; determining one or more most similar hashes in the hash table to the hash code of the portion of the activation vector; and selecting the nodes corresponding to the one or more most similar hashes.

16 . The system of claim 14 , wherein the activation vector comprises real number values, the operations comprising:
converting each of the real numbers 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 selecting the nodes in the particular layer using the activation vector and the hash table comprises selecting the one or more nodes in the particular layer by using the integers as input to the hash table.

17 . The system of claim 16 , wherein:
the integers comprises a first subset and a second, mutually exclusive subset; and selecting the one or more nodes in the particular layer by using the integers as input to the hash table 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;
determining, for each of the integers in the second subset, that the hash table includes a corresponding second entry for a node; and
selecting the one or more nodes in the particular layer as the nodes identified by the second entries.

18 . The system of claim 17 , 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

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