Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
RESOURCE CONSTRAINED NEURAL NETWORK ARCHITECTURE SEARCH
Document Type and Number:
WIPO Patent Application WO/2021/041133
Kind Code:
A1
Abstract:
A method (200) includes defining a neural network computational cell (122), the computational cell including a directed graph of nodes (402) representing respective neural network latent representations and edges (404) representing respective operations that transform a respective neural network latent representation; replacing each operation that transforms a respective neural network latent representation with a respective linear combination of candidate operations, where each candidate operation in a respective linear combination has a respective mixing weight that is parameterized by one or more computational cell hyper parameters; iteratively adjusting values of the computational cell hyper parameters (132a) and weights (132b) to optimize a validation loss function subject to computational resource constraints (106); and generating a neural network (152) for performing a machine learning task using the defined computational cell and the adjusted values of the computational cell hyper parameters and weights.

Inventors:
YANG MING-HSUAN (US)
SLOCUM JOSHUA (US)
JIN XIAOJIE (US)
WANG JIANG (US)
DAI SHENGYANG (US)
Application Number:
PCT/US2020/047073
Publication Date:
March 04, 2021
Filing Date:
August 19, 2020
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
GOOGLE LLC (US)
International Classes:
G06N3/08; G06N3/04; G06N3/063
Foreign References:
Other References:
HANXIAO LIU ET AL: "DARTS: Differentiable Architecture Search", 23 April 2019 (2019-04-23), XP055748345, Retrieved from the Internet [retrieved on 20201109]
TAN MINGXING ET AL: "MnasNet: Platform-Aware Neural Architecture Search for Mobile", 2019 IEEE/CVF CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION (CVPR), IEEE, 15 June 2019 (2019-06-15), pages 2815 - 2823, XP033687287, DOI: 10.1109/CVPR.2019.00293
YANQI ZHOU ET AL: "Resource-Efficient Neural Architect", ARXIV.ORG, CORNELL UNIVERSITY LIBRARY, 201 OLIN LIBRARY CORNELL UNIVERSITY ITHACA, NY 14853, 12 June 2018 (2018-06-12), XP080892856
XIAOJIE JIN ET AL: "RC-DARTS: Resource Constrained Differentiable Architecture Search", ARXIV.ORG, CORNELL UNIVERSITY LIBRARY, 201 OLIN LIBRARY CORNELL UNIVERSITY ITHACA, NY 14853, 30 December 2019 (2019-12-30), XP081567868
Attorney, Agent or Firm:
KRUEGER, Brett, A. (US)
Download PDF:
Claims:
What is claimed is:

1. A computer implemented method (200), the method (200) comprising: defining a computational cell (122) of a neural network, wherein the computational cell (122) comprises a directed graph of nodes (402) and edges (404), each node (402) representing a respective neural network latent representation and each edge (404) representing a respective operation that transforms a respective neural network latent representation, replacing each operation that transforms a respective neural network latent representation with a respective linear combination of candidate operations from a predefined set of candidate operations, wherein each candidate operation in a respective linear combination has a respective mixing weight that is parameterized by one or more computational cell hyper parameters (132a);

Iteratively adjusting values ofi) the computational cell hyper parameters (132a), and ii) computational cell weights (132b), to optimize a validation loss function subject to one or more computational resource constraints (106), comprising, for each iteration: performing an unconstrained optimization of the validation loss function to update values of the computational cell hyper parameters (132a) for a previous Iteration and to obtain adjusted values of the computational cell weights (132b); and projecting the updated values of the computational cell hyper parameters (132a) to a nearest point in a feasible set defined by the one or more resource constraints (106) to obtain adjusted values of the computational cell hyper parameters (132a); and generating a neural network (152) for performing a machine learning task using the defined computational cell (122) and the adjusted values of the computational cell hyper parameters (132a) and computational cell weights (132b).

2. The method (200) of claim 1, wherein generating a neural network (152) for performing a machine learning task using the defined computational cell (122) and the adjusted values of the computational cell hyper parameters (132a) and computational cell weights (132b) comprises: defining a discrete (152) computational cell architecture by replacing each linear combination of candidate operations with a single operation with a largest mixing weight that is parameterized by one or more adjusted computational cell hyper parameters (132a); and generating a neural network for performing a machine learning task using the defined discrete computational cell architecture and the adjusted values of the computational cell weights

(132b).

5 3. The method (200) of claim 1 or 2, wherein generating a neural network (152) for performing a machine learning task using the defined computational cell (122) and the adjusted values of the computational cell hyper parameters (132a) and computational cell weights (132b) comprises stacking multiple copies of the defined computational cell (122), wherein each copy has a same cell architecture defined by the adjusted values of the computational cell hyper 10 parameters (132a).

4. The method (200) of claim 3, further comprising: generating the multiple copies of the defined computational cell (122); and training each generated copy of the defined computational cell (122) on respective

15 training data (102).

5. The method (200) of claim 3 or 4. wherein stacking multiple copies of the defined computational cell (122) comprises interleaving one or more additional neural network layers between the copies of the defined computational cell (122).

20

6. The method (200) of claim 5, wherein the one or more additional neural network layers comprises a connection computational cell (122) that includes one input node (402) and one intermediate node (402), and wherein the method (200) further comprises learning the connection cell by iteratively adjusting values of i) the connection computational cell hyper

25 parameters (132a), and ii) connection computational cell weights (132b), to optimize the validation loss function subject to one or more computational resource constraints (106).

7. The method (200) of any of claims 1-6, wherein the validation loss function represents a measure of error obtained after running a validation dataset through the defined computational

30 set.

8. The method (200) of any of claims 1-7, wherein iteratively adjusting values of i) the computational cell hyper parameters (132a), and ii) computational cell weights (132b), to optimize a validation loss function comprises performing a bi-level optimization of the validation loss function and a training loss function that represents a measure of error obtained on training data (102), wherein the computational cell hyper parameters (132a) comprise upper level parameters and the computational cell weights (132b) comprise lower level parameters.

9. The method (200) of any of claims 1-8, wherein the one or more computational resource constraints (106) comprise user defined constraints on one or more of memory, number of float point operations, or inference speed.

10. The method (200) of any of claims 1-9, wherein iteratively adjusting values of i) the computational cell hyper parameters (132a), and ii) computational cell weights (132b), to optimize a validation loss function subject to one or more computational resource constraints (106) comprises defining a respective cost function for each computational resource constraint, wherein each defined cost function maps the computational cell hyper parameters (132a) to a respective resource cost.

11. The method (200) of claim 10, wherein a respective resource cost of an edge (404) in the computational cell (122) is calculated as a softmax over the costs of operations in the candidate set of operations.

12 The method (200) of claim 10 or 11, further comprising setting lower and higher bound constraints for each defined cost function.

13. The method (200) of any of claims 1-12, wherein performing an unconstrained optimization of the validation loss function to update values of the computational cell hyper parameters (132a) for a previous iteration and to obtain adjusted values of the computational cell weights (132b) comprises iteratively performing the unconstrained optimization of the validation loss function, comprising, for each iteration: obtaining values of the computational cell hyper parameters (132a) and computational ceil weights (132b) for the iteration, comprising obtaining randomly initialized values of the computational cell hyper parameters (132a) and the computational ceil weights (132b) for a first Iteration or obtaining values of the computational cell hyper parameters (132a) and the computational cell weights (132b) from a previous iteration; and iteratively, for a predetermined number of iterations or until predefined convergence criteria are met: fixing the obtained values of the computational cell hyper parameters (132a) for the iteration and obtaining updated computational cell weights (132b) based on a gradient of a training loss function with respect to the computational cell weights ( 132b); and fixing the updated computational cell weights (132b) and obtaining the updated values of the computational cell hyper parameters (132a) based on a gradient of the validation loss function with respect to the computational cell hyper parameters (132a).

14. The method (200) of claim 13 wherein fixing the updated computational cell weights (132b) and obtaining updated computational cell hyper parameters (132a) based on a gradient of the validation loss function with respect to the computational cell hyper parameters (132a) comprises assuming that the computational cell hyper parameters (132a) and the computational cell weights (132b) are independent.

15. The method (200) of any of claims 1-14, wherein projecting the updated values of the computational cell hyper parameters (132a) to a nearest point in a feasible set defined by the one or more resource constraints (106) comprises identifying an element in the feasible set that minimizes a 2-norm of the difference between i) the updated values of the computational cell hyper parameters (132a), and ii) the element.

16. The method (200) of any of claims 1-15, wherein the predefined set of candidate operations comprises pooling operations, convolutional operations or connection operations.

17. The method (200) of any of claims 1-16, further comprising: defining multiple computational cells (122) of the neural network, wherein each defined computational cell (122) can be represented by a respective directed graph of nodes (402) and edges (404); and for each defined computational cell (122) of the multiple defined computational cells

(122): replacing each operation that transforms a respective neural network latent representation with a respective linear combination of candidate operations from a predefined set of candidate operations, wherein each candidate operation in a respective linear combination has a respective mixing weight that is parameterized by one or more computational cell hyper parameters (132a); and iteratively adjusting values of i) the computational cell hyper parameters (132a), and ii) computational cell weights (132b), to optimize a validation loss function subject to one or more computational resource constraints (106), comprising, for each iteration: performing an unconstrained optimization of the validation loss function to update values of the computational cell hyper parameters (132a) for a previous iteration and to obtain adjusted values of the computational cell weights (132b); and projecting the updated values of the computational cell hyper parameters (132a) to a nearest point in a feasible set defined by the one or more resource constraints (106) to obtain adjusted values of the computational ceil hyper parameters (132a); and generating a neural network for performing a machine learning task using the defined multiple computational cells (122) and the adjusted values of the respective computational cell hyper parameters (132a) and computational cell weights (132b).

18. The method (200) of any of claims 1- 17, further comprising: training the generated neural network (152) on training data (102) to obtain a trained neural network (152); and performing the machine learning task using the trained neural network (152).

19. A system (100) 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: defining a computational cell (122) of a neural network, wherein the computational cell (122) comprises a directed graph of nodes (402) and edges (404), each node (402) representing a respective neural network latent representation and each edge (404) representing a respective operation that transforms a respective neural network latent representation; replacing each operation that transforms a respective neural network latent representation with a respective linear combination of candidate operations from a predefined set of candidate operations, wherein each candidate operation in a respective linear combination has a respective mixing weight that is parameterized by one or more computational cell hyper parameters (132a) iteratively adjusting values of i) the computational cell hyper parameters (132a), and ii) computational cell weights (132b), to optimize a validation loss function subject to one or more computational resource constraints (106), comprising, for each iteration: performing an unconstrained optimization of the validation loss function to update values of the computational cell hyper parameters (132a) for a previous iteration and to obtain adjusted values of the computational cell weights (132b), and projecting the updated values of the computational cell hyper parameters (132a) to a nearest point in a feasible set defined by the one or more resource constraints (106) to obtain adjusted values of the computational cell hyper parameters (132a); and generating a neural network (152) for performing a machine learning task using the defined computational cell (122) and the adjusted values of the computational cell hyper parameters (132a) and computational cell weights (132b).

20. A computer-readable storage medium comprising instructions stored thereon that are executable by a processing device and upon such execution cause the processing device to perform operations comprising: defining a computational cell (122) of a neural network, wherein the computational cell (122) comprises a directed graph of nodes (402) and edges (404), each node (402) representing a respective neural network latent representation and each edge (404) representing a respective operation that transforms a respective neural network latent representation; replacing each operation that transforms a respective neural network latent representation with a respective linear combination of candidate operations from a predefined set of candidate operations, wherein each candidate operation in a respective linear combination has a respective mixing weight that is parameterized by one or more computational cell hyper parameters (132a); iteratively adjusting values of i) the computational cell hyper parameters (132a), and ii) computational cell weights (132b), to optimize a validation loss function subject to one or more computational resource constraints (106), comprising, for each iteration: performing an unconstrained optimization of the validation loss function to update values of the computational cell hyper parameters (132a) for a previous iteration and to obtain adjusted values of the computational cell weights (132b); and projecting the updated values of the computational cell hyper parameters (132a) to a nearest point in a feasible set defined by the one or more resource constraints (106) to obtain adjusted values of the computational ceil hyper parameters (132a); and generating a neural network (152) for performing a machine learning task using the defined computational cell (122) and the adjusted values of the computational cell hyper parameters (132a) and computational cell weights (132b).

Description:
RESOURCE CONSTRAINED NEURAL NETWORK ARCHITECTURE SEARCH

TECHNICAL FIELD

[0001] This specification relates to determining architectures for neural networks.

BACKGROUND

[0002] Neural networks are machine learning models that employ one or more layers of nonlinear units to predict an output for a received input. Some neural networks include one or more hidden layers in addition to an output layer The output of each hidden layer is used as input to the next layer in the network, i .e., the next hidden layer or the output layer. Each layer of the network generates an output from a received input in accordance with current values of a respective set of parameters.

SUMMARY

[0003] This specification describes an end-to-end neural architecture search framework for one-shot neural architecture search under resource constraints, where a customized network architecture can be learned for any machine learning task dataset.

[0004] In general, one innovative aspect of the subject matter described in this specification includes a method for neural network architecture search, the method including defining a computational cell of a neural network, wherein the computational cell comprises a directed graph of nodes and edges, each node representing a respective neural network latent representation and each edge representing a respective operation that transforms a respective neural network latent representation; replacing each operation that transforms a respective neural network latent representation with a respective linear combination of candidate operations from a predefined set of candidate operations, wherein each candidate operation in a respective linear combination has a respective mixing weight that is parameterized by one or more computational cell hyper parameters; iteratively adjusting values ofi) the computational cell hyper parameters, and ii) computational cell weights, to optimize a validation loss function subject to one or more computational resource constraints, comprising, for each iteration: performing an unconstrained optimization of the validation loss function to update values of the computational cell hyper parameters for a previous iteration and to obtain adjusted values of the computational cell weights; and projecting the updated values of the computational cell hyper parameters to a nearest point in a feasible set defined by the one or more resource constraints to obtain adjusted values of the compu tational cell hyper parameters; and generating a neural network for performing a machine learning task using the defined computational cell and the adjusted values of the computational cell hyper parameters and computational cell weights.

[0005] Other embodiments of this aspect include corresponding computer systems, apparatus, and computer programs recorded on one or more computer storage devices, each configured to perform the actions of the methods. A system of one or more computers can be configured to perform particular operations or actions by virtue of software, firmware, hardware, or any combination thereof installed on the system that in operation may cause the system to perform the actions One or more computer programs can be configured to perform particular operations or actions by virtue of including instructions that, when executed by data processing apparatus, cause the apparatus to perform the actions.

[0006] The foregoing and other embodiments can each optionally include one or more of the following features, alone or in combination. In some implementations generating a neural network for performing a machine learning task using the defined computational cell and the adjusted values of the computational cell hyper parameters and computational cell weights comprises: defining a discrete computational cell architecture by replacing each linear combination of candidate operations with a single operation with a largest mixing weight that is parameterized by one or more adjusted computational cell hyper parameters, and generating a neural network for performing a machine learning task using the defined discrete computational cell architecture and the adjusted values of the computational cell weights.

[0007] In some implementations generating a neural network for performing a machine learning task using the defined computational cell and the adjusted values of the computational cell hyper parameters and computational cell weights comprises stacking multiple copies of the defined computational cell, wherein each copy has a same cell architecture defined by the adjusted values of the computational cell hyper parameters.

[0008] In some implementations the method further comprises generating the multiple copies of the defined computational cell; and training each generated copy of the defined computational cell on respective training data. [0009] In some implementations stacking multiple copies of the defined computational cell comprises interlea ving one or more additional neural network layers between the copies of the defined computational cell.

[0010] In some implementations the one or more additional neural network layers comprises a connection computational cell that includes one input node and one intermediate node, and wherein the method further comprises learning the connection cell by iteratively adjusting values of i) the connection computational cell hyper parameters, and ii) connection computational cell weights, to optimize the validation loss function subject to one or more computational resource constraints

[00 ] In some Implementations the validation loss function represents a measure of error obtained after running a validation dataset through the defined computational set

[0012] In some implementations iteratively adjusting values of i) the computational cell hyper parameters, and ii) computational cell weights, to optimize a validation loss function comprises performing a bi-level optimization of the validation loss function and a training loss function that represents a measure of error obtained on training data, wherein the computational cell hyper parameters comprise upper level parameters and the computational cell weights comprise lower level parameters.

[0013] In some Implementations the one or more computational resource constraints comprise user defined constraints on one or more of memory, number of float point operations, or inference speed.

[0014] In some implementations iteratively adjusting values of i) the computational cell hyper parameters, and ii) computational cell weights, to optimize a validation loss function subject to one or more computational resource constraints comprises: defining a respective cost function for each computational resource constraint, wherein each defined cost function maps the computational cell hyper parameters to a respective resource cost.

[0015] In some implementations a respective resource cost of an edge in the computational cell is calculated as a sorimax over the costs of operations in the candidate set of operations. [0016] In some Implementations the method further comprises setting lower and higher bound constraints for each defined cost function.

[0017] In some implementations performing an unconstrained optimization of the validation loss function to update values of the computational cell hyper parameters for a previous Iteration and to obtain adjusted values of the computational cell weights comprises iteratively performing the unconstrained optimization of the validation loss function, comprising for each iteration obtaining values of the computational cell hyper parameters and computational cell weights for the iteration, comprising obtaining randomly initialized values of the computational cell hyper parameters and the computational cell weights for a first Iteration or obtaining values of the computational cell hyper parameters and the computational cell weights from a previous iteration; iteratively, for a predetermined number of iterations or until predefined convergence criteria are met: fixing the obtained values of the computational cell hyper parameters for the iteration and obtaining updated computational cell weights based on a gradient of a training loss function with respect to the computational cell weights, and fixing the updated computational cell weights and obtaining the updated values of the computational cell hyper parameters based on a gradient of the validation loss function with respect to the computational cell hyper parameters.

[0018] In some implementations fixing the updated computational cell weights and obtaining updated computational cell hyper parameters based on a gradient of the validation loss function with respect to the computational cell hyper parameters comprises assuming that the computational cell hyper parameters and the computational cell weights are independent

[0019] In some implementations projecting the updated values of the computational cell hyper parameters to a nearest point in a feasible set defined by the one or more resource constraints comprises identifying an element in the feasible set that minimizes a 2-norm of the difference between i) the updated values of the computational cell hyper parameters, and ii) the element.

[0020] In some implementations the predefined set of candidate operations comprises pooling operations, convolutional operations or connection operations.

[0021] In some implementations the method further comprises defining multiple computational cells of the neural network, wherein each defined computational cell can be represented by a respective directed graph of nodes and edges; for each defined computational eell of the multiple defined computational cells: replacing each operation that transforms a respective neural network latent representation with a respective linear combination of candidate operations from a predefined set of candidate operations, wherein each candidate operation in a respective linear combination has a respective mixing weight that is parameterized by one or more computational cell hyper parameters; iteratively adjusting values of i) the computational cell hyper parameters, and ii) computational cell weights, to optimize a validation loss function subject to one or more computational resource constraints, comprising, for each iteration; performing an unconstrained optimization of the validation loss function to update values of the computational cell hyper parameters for a previous iteration and to obtain adjusted values of the computational cell weights; and projecting the updated values of the computational cell hyper parameters to a nearest point in a feasible set defined by the one or more resource constraints to obtain adjusted values of the computational cell hyper parameters; and generating a neural network for performing a machine learning task using the defined multiple computational cells and the adjusted values of the respective computational cell hyper parameters and computational cell weights.

[0022] In some implementations the method further comprises training the generated neural network on training data to obtain a trained neural network; and performing the machine learning task using the trained neural network.

(0023] The subject matter described in this specification can be implemented in particular embodiments so as to realize one or more of the following advantages.

[0024] A system implementing the presently described techniques can learn neural network architectures that satisfy task dependent resource constraints, such as model size and computational complexity. For example, the system can learn lightweight neural network architectures that can be efficiently implemented by mobile platforms with constrained computing resources.

[0025] In addition, lightweight neural network architectures can be learned under resource constraints without compromising the quality of the neural network architecture, e.g., its accuracy and performance. For example, learned neural network architectures can achieve state of the art performance in terms of accuracy, model size and complexity. The presently described techniques for performing neural network architecture search can also achieve Improved neural architecture search speed.

[0026] In addition, the techniques described in this specification are not limited to particular machine learning applications - a system implementing the presently described techniques can learn customized neural network architectures for any particular machine learning task and dataset. The presently described techniques are also suitable for one-shot resource constrained neural architecture searches.

[0027] The details of one or more embodiments of the subject matter of this specification are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the subject matter will become apparent from the description, the drawings, and the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

[0028] FIG. 1 shows an example neural network architecture search system

[0029] FIG. 2 is a flow diagram of an example process for generating a neural network for performing a machine learning task

[0030] FIG. 3 is a flow diagram of an example process for performing an iterative projection method.

[0031] FIG. 4 is an example conceptual visualization of learning a discrete computational cell architecture

[0032] Like reference numbers and designations in the vanous drawings indicate like elements.

DETAILED DESCRIPTION

[0033] Designing and implementing neural network architectures for performing machine learning tasks such as image recognition, speech recognition or language modelling can be a time-consuming and costly process that requires expert knowledge and experience in the field [0034] One example technique for automating the design of neural network architectures is Neural Architecture Search (NAS). NAS techniques can be categorized into two main groups The first group of NAS techniques use black-box optimization approaches, e.g., reinforcement learning or genetic algorithms to optimize a reward function. Such techniques typically require the training of thousands of deep learning models to learn a neural network architecture, and therefore incur large computational costs. In addition, NAS techniques that use black-box optimization are computationally too expensive for one-shot NAS One-shot NAS is important for resource constrained applications because different tasks require different neural network architectures. For example, for a simple problem such as classifying image color, a simple neural network architecture, e g., a two-layer neural network. On the other hand, classifying cats and dogs from images requires a complex neural network

[0035] The second group of NAS techniques formulate the neural architecture search task as a differentiable optimization problem and utilize gradient descent to find an optimal solution. NAS techniques in the second group are typically more computationally efficient compared to NAS techniques in the first group.

[0036] This specification describes end-to-end resource constrained differentiable architecture search framework for one-shot NAS. Differentiable architecture search tasks are formulated as constrained optimization tasks by including resource constraints, where the search space for the resource constrained optimization task is mapped to a continuous search space to enable the application of gradient descent methods. An iterative projection algorithm is applied to solve the constrained optimization task and learn neural network architectures in a feasible set defined by the constraints. A multi-level search strategy can be applied to learn difforem architectures for neural network layers at different depths.

[0037] The neural network architectures learned by the presently described techniques can be configured to receive any kind of digital data input and to generate any kind of score, classification, or regression output based on the input.

[0038] For example, if the inputs to a neural network defined by the neural network architecture are images or features that have been extracted from images, the output generated by the neural network for a given Image may be scores for each of a set of object categories, with each score representing an estimated likelihood that the image contains an image of an object belonging to tire category.

[0039] As another example, if the inpu ts to a neural network defined by the neural network architecture are Internet resources (e.g., web pages), documents, or portions of documents or features extracted from Internet resources, documents, or portions of documents, the output generated by the neural network for a given internet resource, document, or portion of a document may be a score for each of a set of topics, with each score representing an estimated likelihood that the Internet resource, document, or document portion is about the topic

[0040] As another example, if the inputs to a neural network defined by the neural network architecture are features of an impression context for a particular advertisement, the output generated by the neural network may be a score that represents an estimated likelihood that the particular advertisement will be clicked on.

[0041] As another example, if the inputs to a neural network defined by the neural network architecture are features of a personalized recommendation for a user, e.g., features characterizing the context for the recommendation, e.g. features characterizing previous actions taken by the user, the output generated by the neural network may be a score for each of a set of content items, with each score representing an estimated likelihood that the user will respond favorably to being recommended the content item.

[0042] As another example, if the input to a neural network defined by the neural network architecture is a sequence of text in one language, the output generated by the neural network may be a score for each of a set of pieces of text in another language, with each score representing an estimated likelihood that the piece of text in the other language is a proper translation of the input text into the other language.

[0043] As another example, if the input to a neural network defined by the neural network architecture is a sequence representing a spoken utterance, the output generated by the neural network may be a score for each of a set of pi eces of text, each score representing an estimated likelihood that the piece of text is the correct transcript for the utterance.

Example hardware

[0042] FIG. 1 shows an example neural architecture search system 100. The neural architecture search system 100 is an example of a system implemented as computer programs on one or more computers in one or more locations, in which the systems, components, and techniques described below can be implemented.

[0043] The neural architecture search system 100 is a system that receives training data 102 for training a neural network to perform a particular machine learning task, a validation set 104 for evaluating the performance of the neural network on the particular machine learning task, and data specifying resource constraints 106 of a computational device implementing the neural network when performing the particular machine learning task.

[0044] The neural architecture search system 100 uses the training data 102 and the validation set 104 to determine a neural network architecture for a neural network that is configured to perform the particular task. The architecture defines the number of layers In the neural network, the operations performed by each of the layers, and the connectivity between the layers In the neural network, i.e., which layers receive inputs from which other layers in the neural network Generally, the training data 102 and the validation set 104 both include a set of neural network Inputs and, for each network Input, a respective target output that should be generated by the neural network to perform the particular task. For example, a larger set of training data may have been randomly partiboned to generate the training data 102 and the validation set 104.

[0045] The neural architecture search system 100 uses the resource constraints when determining a neural network architecture for a neural network that is configured to perform the particular task. That is, the neural architecture search system 100 learns a neural network architecture under the resource constraints Example resource constraints include but are not limited to amount of available memory, number of float point operations, inference speed, or model size. Learning a neural network under resource constraints is particularly useful for mobile platforms and real time applications.

[0046] The system 100 can receive the training data 102, the validation set 104. and the computational resource constraints in any of a variety of ways. For example, the system 100 can receive training data as an upload irons a remote user of the system over a data communication network, e.g., using an application programming interface (API) made available by the system 100, and randomly divide the uploaded data into the training data 102 and the validation set 104. The system 100 can also receive user defined computational resource constraints as an upload from a remote user of the system over a data communication network, e.g., using an application programming interface (API) made available by the system 100

[0047] As another example, the system 100 can receive an input from a user specifying which data that Is already maintained by the system 100 should be used for training the neural network, and then divide the specified data into the training data 102 and the validation set 104. Similarly, the system 100 can receive an input from a user specifying which of multiple resource constraints maintained by the system 100 should be used for determining the neural network architecture.

[0048] The neural architecture search system 100 includes a computational cell generator 110, a computational cell parameter adjustment engine 120, and a neural network architecture generator 130. [0049] The computational cell generator 110 is configured to define computational cells of the neural network whose neural network architecture is being determined by the system 100. Computational cells defined by the computational cell generator 110 are architectural building blocks e.g., a sub networks, of the neural network whose neural network architecture is being determined by the system 100. For example, multiple instances of defined computational cells with respective learned architectures and independently learned weights can be stacked to generate a deeper neural network.

[0050] Computational cells defined by the computational cell generator 110 can each be represented as a respective directed acyclic graph G = (V, E) of a predetermined number of nodes V and edges if. Each node x i Î V in a computational cell represents a latent representation e.g., a feature map in convolutional networks Each directed edge (ij) is associated with an operation O i,j The operation O i,j transforms node x i , e.g , the operation takes the latent representation x i as input and outputs the latent representation x j . Each node can be computed based on all of its predecessors ' transformed outputs, e.g. where represents the set of predecessors of x j . An example computational cell is illustrated and described below with reference to FIG. 4.

[0051] The computational cell generator 110 can be configured to define computational cells based on the received inputs 102-106. For example, the number of nodes and edges included in a defined computational cell can depend on the machine learning task to be performed by the neural network whose neural network architecture is being determined by the system 100 and the computational resources available for implementing the neural network.

[0052] The computational cell parameter updating engine 120 is configured to receive data representing defined computational cells 122 from the computational cell generator 110 The computational cell parameter adjustment engine 120 is configured to iteratively adjust values of computational cell hyper parameters and computational cell weights to optimize a validation loss function subject to the resource constraints 106. Adjusting values of the computational cell hyper parameters and computational cell weights to optimize a validation loss function subject to the resource constraints 106 includes implementing a continuous relaxation strategy to map the architecture search space from a discrete search space defined by a predefined discrete set of candidate operatio O i,j to a continuous search space, so that the architecture can be determined using gradient descent A constrained optimization problem on the continuous search space is then performed to determine the adjusted values of computational cell hyper parameters and computational cell weights that optimize the validation loss function. Operations performed by the computational cell parameter updating engine 120 are described in more detail below with reference to FIGS. 2 and 3

(0053J The neural network architecture generator 130 is configured to receive data representing adjusted computational cell parameter values 132, e.g , hyper parameters 132a and weights 132b, from the computational cell parameter adjustment engine 120. The neural network architecture generator 130 is configured to determine a neural network architecture 150 using the adjusted computational cell parameter values (and the defined computational cell 122). For example, the neural network architecture generator 130 can determine a neural network architecture 150 as being equal to a stack of multiple copies of the defined computational cells, where the architecture of each copy of a computational cell has a cell architecture defined by the adjusted computational cell parameter values 132. In some cases the neural network architecture generator 130 can include additional layers, e.g., one or more filter layers, between stacks of computational cells in the determined neural network architecture. Determining a neural network architecture using defined computational cells and learned computational cell parameters is described in more detail below with reference to FIG. 2.

[0054J The neural network search system 100 can output architecture data 150 that specifies the architecture of the neural network i.e., data specifying the layers that are part of the neural network, the connectivity between the layers, and the operations performed by the layers. For example, the neural network search system 100 can output the architecture data 150 to the user that submitted the training data and the resource constraints. The user can then use a resource constrained device to train an instance of the neural network having the determined architecture and use die trained neural network to process neural network inputs.

[0055] In some implementations, instead of or in addition to outputting the architecture data 150, the system 100 trains an instance of the neural network having the determined architecture, eg., either from scratch or to fine-tune the parameter values generated as a result of training the neural network having the architecture, and then uses the trained neural network to process requests received by users, e.g., through the API provided by the system That is, the system 100 can receive inputs to be processed, use the trained neural network to process the inputs, and provide the outputs generated by the trained neural network or data derived from the generated outputs in response to the received inputs.

Programming the hardware

[0056] FIG. 2 is a flow diagram of an example method 200 for generating a neural network 152 for performing a machine learning task. For convenience, the method 200 will be described as being performed by a system of one or more computers located in one or more locations. For example, a neural architecture search system, e g., the neural architecture search system 100 of FIG. 1, appropriately programmed in accordance with this specification, can perform the method 200.

[0057] The system defines a computational cell for die neural network (step 202). The computational cell can be viewed as an architectural building block, e.g., a sub network, of the neural network generated by example method 200. For example, as described in more detail below with reference to step 206, multiple Instances of the defined computational cell with a same learned architecture and independently learned weights can be stacked to generate a deeper neural network.

[0058] The defined computational cell can be represented as a directed acyclic grap =

(V, E ) of a predetermined number of nodes V and edges E Each node x i Î V in the computational cell represents an latent representation, e.g , a feature map in convolutional networks. Each directed edge (i j) is associated with an operation O i,j . The operation O i,j transforms node x i , e.g., the operation takes the latent representation x i as input and outputs the latent representation x j . Each node can be computed based on all of its predecessors ' transformed outputs, e.g., where represents the set of predecessors of x j .

[0059] The number of nodes and edges included in the defined computational cell can depend on the machine learning task to be performed by the final generated neural network and the computational resources available for searching for the architecture of the neural network.

For example, since it can be computationally expensive to search for the architecture of a whole neural network or a large sub network of a neural network on a large-scale dataset, the size of the defined computational cell can be chosen to reduce the computational costs whilst maintaining final accuracy of the neural network. (0060} In some implementations the computational cell can include one or more input nodes and one or more output nodes, e.g., two input nodes and a single output node. Input nodes can be defined as nodes that transform outputs of previous computational cells. For example, in cases where the neural network architecture is a convolutional neural network architecture, the computational cell can be a convolutional cell and the input nodes can be defined as the cell outputs from the previous two layers, e.g., the input nodes represent input images. In cases where the neural network architecture is a recurrent neural network architecture, the computational cell is a recurrent cell and the Input nodes include the input at the current step and the state carried from the previous step Output nodes can be defined as nodes that provide an output of a computational cell The output of a computational cell can be obtained by applying a reduction operation, e.g., concatenation, to all the nodes, e.g., where N represents the total number of nodes in the computational cell.

[0061] The operations associated with the directed edges are part of a discrete architecture search space O that includes a predefined set of operations that the neural network architecture can perform. For example, the pre-deftned set of operations can include pooling operations, e.g., max pooling or average pooling, convolution operations with varying kernel sizes, e.g., separable convolutions or dilated separable convolutions, or connections, e.g , zero connections or identity connections.

[0062] The architecture search space can be transformed to a continuous search space by replacing each candidate operation in the predefined set of operations with a respective linear combination of candidate operations from the predefined set of candidate operations - also referred to herein as a mixing operatio Ô i , . Eac ndidate operation in a respective linear combination has a respective mixing weight that is parameterized by one or more computational cell hyper parameters In some implementations each mixing operatio Ô i,j outputs a softmax weighted sum of all possible operations in An example mixing operation is given by Equation (1) below. In Equation (1), where the operation mixing weights for a pair of nodes ,j) are parameterized by a vector

[0063] After the architecture search space is transformed to a continuous search space the task of generating the neural network for performing the machine learning task includes learning the set of continuous variables q = {q (i,j) }· Once the set of continuous variables have been learned, a corresponding discrete computational cell architecture can be obtained by first determining a number of strongest predecessors for node X j based on a strength of the corresponding edge, where the strength of an edge (i,j) is defined in Equation (2) below.

[0064] For example, the system can determine a number equal to the size of the set of predecessors of x j of strongest predecessors for node x j . Then, the mixing operation for edge (i,j) is replaced with a single operation with the largest mixing weight, as defined in Equation (3) below.

[0065] The system learns i) computational cell hyper-parameters that define the computational cell architecture, and ii) computational cell weights by optimizing a validation loss function (step 204).

[0066] The validation loss function represents a measure of error obtained after running a set of validation data through the trained neural network. The validation loss depends on the computational cell hyper-parameters q and neural network weights w, i.e., and optimizing the validation loss function Includes determining optimal computational cell hyper-parameters that minimize the validation loss represents computational cell weights obtained by optimizing a training loss function that represents a measure of error obtained on training data (training data specific to the machine learning task to be performed by the neural network), i.e., That is, the system performs a bi-level optimization where the computational cell hyper-parameters q are the upper level parameters and the computational cell weights w are the lower level parameters. [0067] The system optimizes the validation loss function subject to one or more resource constraints. The one or more resource constraints can be defined by a user based on the computational resources available when implementing the neural network generated using example method 200. For example, the system may receive as input data representing target values of different resource costs, e.g., available memory, FLOPs, or inference speed, etc. [0068] The system can associate each user-defined resource constraint with a corresponding cost function that maps the computational cell hyper-parameters to a respective resource cost. For example the system can create a discretized network architecture from the computational cell hyper-parameters q according to Equation (3) and compute the cost for the discretized network to determine an exact cost of a computational cell architecture. Since the objective function of a discretized network architecture is not continuous, it is challenging to optimize the objective function using gradient descent. Therefore, the system implements a continuous relaxation strategy on the user defined resource constraints, where a cost of edge (i,j) in the defined computational cell Is calculated as the softmax over all possible operations’ costs, as given by Equation (4) below.

[0069] in Equation (4), represents the resource costs of all operations in , F represents the softmax function, represents the indicator function and represents the set of predecessor nodes for the node j.

[0070] Equation (4) uses the expectation of resource costs in a cell as an approximation to the actual cost of the discrete architecture derived from q. There are multiple advantages to using the function form in Equation (4). For example, since Equation (4) is differentiable w.r.t. q, it enables the use of gradient descent to optimize the validation loss function. As another example, Equation (4) is straightforward to implement because the resource cost of each candidate operation for the edge (i,j) is independent of the values of q (i,j) her re, u can be fixed and computed before training. If a more complicated resource constraint is to be implemented, such as inference speed on a particular platform, a neural network that maps architecture hyper-parameters to a resource cost can be learned

[0071] The system can set lower bound and higher bound constraints for each cost function to prevent the model from learning oversimplified architectures. The lower bound constraints can be set to ensure that the model has sufficient representation capabilities.

[0072] To summarize, the system performs the constrained optimization given by Equation (5) below.

[0073] In Equation (5), represents the training loss, Φ(θ) = [Φ 0 (q), ... ,Φ M-1 (q)] T with represents a set of M cost functions, and represent user-defined lower and upper bounds of cost constraints, respectively. That is, the cost Φ m (θ) is constrained to be in the range of . To optimize the validation loss function the system performs an iterative projection method. The system performs an iterative projection method because the cost function with respect to q is non- convex because of the softmax function in Equation (4), and there is no closed-form solution to the objective function.

[0074] The iterative projection method optimizes tire validation loss function in two alternating phases - an unconstrained training phase that searches improved architectures by performing an unconstrained optimization of the validation loss function to learn the computational cell hyper parameters q in a larger parameter space without constraints, and an architecture projection phase that projects tire computational cell hyper parameters q output by the unconstrained training phase to its nearest point in the feasible set defined by the constraints in Equation (5). The unconstrained training phase and architecture projection phase are described in more detail below with reference to FIG. 3. [0075] The system generates the neural network for performing the machine learning task using the defined computational cell and learned computational cell hyper-parameters and computational cell weights (step 206).

[0076] In some implementations generating the neural network using the defined computational cell and learned computational cell hyper-parameters and computational cell weights can include stacking multiple copies of the computational cell For example, the system can generate multiple copies of the computational cell, where each copy of the computational cell has a same cell architecture defined by the learned computational cell hyper parameters. The system can train each copy of the computational cell on a respective set of training data (specific to the machine learning task to be performed by foe neural network). In this manner, the multiple copies of the computational cell have independently learned computational cell weights. The system can then stack the trained multiple copies of the computational cell to create a deeper neural network for performing the machine learning task.

[0077] In cases where the defined computational cell includes input and output nodes, stacking the trained multiple copies of the computational cell can include removing the output node in a first copy of the computational cell, removing the input nodes and output nodes of intermediate copies of the computational cell, and removing the input nodes of the last copy of the computational cell before stacking. In cases where the defined computational cell does not include input and output nodes, stacking the trained multiple copies of foe computational cell can include adding one or more input nodes and an output node to the stack. In either case, the system can further add additional nodes and/or layers to the stacked trained copies of the computational cell, e.g., one or more filter layers.

[0078] In some implementations the system can implement a multi-level search strategy when performing example method 200 for generating a neural network. To implement the multi- level search strategy the system can define multiple computational cells at step 202, where each of foe defined computational cells can be represented as a respective directed acyclic graph of a predetermined number of nodes and edges. That is, the defined multiple computational cells can have different architectures. The system can then perform step 204 for each of the defined computational cells, and combine learned computational cells and/or copies of learned computational cells to generate the neural network, as described with reference to step 206 [0079] implementing a multi -level search strategy can be advantageous for multiple reasons. For example, cells at different network depths can exhibit a large variation on the resource cost, e.g number of parameters and number of FLOPs, because the number of channels of filters is increased wherever the resolution of input is reduced. This design is widely used in deep networks to avoid the bottleneck of information flow, where the low-level layers, i.e layers near input, have larger FLOPs than the high-level layers while the high-level layers have larger number of parameters than low-level layers. In order to make the learned architectures satisfy given resource constraints, it can be advantageous to make the architecture of cells vary with the depths of layers. As another example, cells at different depths can have different effects on a network’s overall performance, e g., low-level layers (near input) can be more insensitive to reducing the number of parameters.

[0080] in addition, to obtain more lightweight architectures, the system can apply steps 202- 204 to learn connection cells or layers between stacks of computational cells instead of predefining the connections, e g , to be 1x1 corns A connection cell can be formulated as described above with reference to step 202. In some implementations connection cells may include one input node and one node inside the connection cell

[0081] FIG. 3 is a flow diagram of an example process 300 for performing the iterative projective method described above with reference to FIG. 2 For convenience, the process 300 will he described as being performed by a system of one or more computers located in one or more locations. For example, a neural architecture search system, e.g., the neural architecture search system 100 of FIG. 1, appropriately programmed in accordance with this specification, can perform the process 300.

[0082] The system randomly initializes the values of the computational cell hyper parameters and the computational cell weights (step 302).

[0083] The system iteratively performs an unconstrained training process (i e., an unconstrained optimization of the validation loss function, as described below) and an architecture projection process for a predetermined number of iterations or until predefined convergence criteria are met (step 304). For example, each iteration can include an implementation of the unconstrained training process directly followed by an implementation of the architecture projection process. [0084] For each iteration, the system obtains computational cell hyper parameters q t and computational cell weights w t tor the iteration (step 304a). in cases where the iteration is a first iteration of the iterative projection method, the system can obtain the randomly initialized computational cell hyper parameters q t = q 0 and the randomly initialized computational cell weights w t = w 0 . In cases where the iteration is a subsequent iteration of the iterative prelection method, the system can receive computational cell hyper parameters q t- and computational cell weigh s t -1 om the previous iteration t - 1 of the iterative projection method.

[0085] The system performs the unconstrained training process by determining adjusted computational cell hyper-parameters that optimize (minimize) the validation loss defined above with reference to FIG 3 (step 304b). As described above ω * = ω * (θ) represents computational cell weights obtained by optimizing the training loss function That is, the system solves the optimization problem given below in Equation (6).

[0086] Since il ls difficult to obtain an exact solution to Equation (6) for both the computational cell weights w and the computational cell hyper-parameters θ in parallel, the system implements a coordinate gradient descent technique to iteratively and alternatively update the weights w t and the hyper parameters θ while fixing the value of the other [0087] For example, in a first step the system can fix the values of the received computational cell hyper parameters q t and obtain updated computational cell weig t1 by descending along In a second step the system fixes the values of the computational cell weights t1 obtained during the first step and obtains updated computational cell hyper parameters q t+1 by descending along The system can iteratively perform the first step and second step for a predetermined number of iterations or until predefined convergence criteria are met. During the second step it can be assumed that m and θ ate independent for increased computational efficiency and satisfactory performance. [0088] The system performs the architecture projection process using the adjusted computational cell hyper parameters q t+1 (step 304c). The system projects the updated computational cell hyper parameters q t 1 to a nearest point q p in the feasible set defined by the resource constraints given in Equation (5) The objective of the projection can be described by Equation (7) below.

Because Φ(q p ) are nomconvex functions of q p , there is no closed-form solution to Equation (7). Therefore, the system transforms Equation (7) to its Lagrangian given by Equation (8) below.

[0089] The system performs gradient descent to optimize Equation (8). At time step t = 0, the system sets At a subsequent time step t, the system obtains by descending in the direction of The system performs the updates iteratively until all constraints are satisfied or until a predetermined maximum iteration number e p is reached.

[0090] In some implementations the system sets the weighting terms l and λ 2 to be identical l = λ 2 = λ for all constraints. To facilitate convergence, λ can be set to diminish exponentially during training. At the end of training, λ → 0 and q p =0. Since It Is fast to compute for simple resource constraints, the architecture iterative projection phase (step 404c) is faster than the unconstrained training phase (step 404b).

[0091] The system provides the computational cell parameters q p obtained by optimizing the Lagrangian given by Equation (8) as input for the next iteration of the unconstrained training process and architecture projection process. If the iteration is the final iteration the system provides the hyper parameters q p for denying the discrete architecture described above with reference to FIG. 3 (step 306). [0092] Performing example process 400 provides several advantages. For example, by jointly optimizing computational cell weights and computational cell hyper parameters, the system can learn an unproved starting point for the architecture projection process. As another example, after the architecture projection phase is performed, the unconstrained training phase is performed to learn a computational cell architecture in a larger, unconstrained parameter space Therefore, even if an architecture projection phase results in a sub-optimal computational cell architecture, the unconstrained training phase can still learn an Improved computational cell architecture. In addition since neural networks can be sensitive to perturbations on weights in an initial training phase, in some implementations the system can implement a warm-start strategy where the unconstrained training phase for the first iteration of the iterative projection method has a larger number of iterations of the first step and the second step compared to later iterations of the iterative projection method This can reduce the likelihood that the model gets stuck in a bad local optimum in the architecture projection phase.

[0093] FIG 4 is an example conceptual visualization of learning a discrete computational cell architecture.

[0094] Stage (a) corresponds to step 202 of example method 200. At stage (a) an initial computational cell 400 is defined. The initial computational cell 400 includes four intermediate nodes, e.g , node 402 The initial computational cell 400 can further Include one or more input nodes and an output node, but for clarity the input nodes and output nodes are omitted in FIG. 4. The Initial computational cell 400 further includes six directed edges between the intermediate nodes, e g., edge 404

[0095] As described above with reference to Equation (1), at stage (b) the operations on each of the six edges are replaced by a mixture of all candidate operations in the predefined set of candidate operations. In the example visualization shown in FIG. 4 there are three candidate operations, however in some implementations there may be fewer or more candidate operations. [0096] Stage (c) corresponds to step 204 of example method 200. At stage (c) the iterative projection method described above with reference to FIG. 3 is applied to solve the constrained optimization problem given by Equation (5), where the architecture parameters as well as the weights in the cell are jointly optimized to satisfy the resource constraints. (0097} At stage (d) a final computational cell architecture 406 is derived from the learned weights in mixed operations The computational cell can then be used to generate a neural network, as described above with reference to step 206 of example method 200.

[0098] Embodiments of the subject matter and the functional operations described in this specification can be implemented in digital electronic circuitry, in tangibly-embodied computer software or firmware, in computer hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the subject matter described in this specification can be Implemented as one or more computer programs, he., one or more modules of computer program instructions encoded on a tangible non transitory program carrier for execution by, or to control the operation of data processing apparatus. Alternatively or in addition, the program instructions can be encoded on an artificially generated propagated signal, e.g., a machine-generated electrical, optical or electromagnetic signal, that is generated to encode information for transmission to suitable receiver apparatus for execution by a data processing apparatus The computer storage medium can be a machine-readable storage device, a machine-readable storage substrate, a random or serial access memory device, or a combination of one or more of them. The computer storage medium is not, however, a propagated signal

[0099] The term “data processing apparatus” encompasses all kinds of apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers The apparatus can include special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). The apparatus can also include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g , code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them

[00100] A computer program (which may also be referred to or described as a program, software, a software application, a module, a software module, a script, or code) can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and it can be deployed in any form, including as a stand- alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program may, but need not, correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data, e.g., one or more scripts stored in a markup language document, in a single file dedicated to the program in question, or in multiple coordinated files, e.g , files that store one or more modules, sub programs, or portions of code. A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network

[00101] As used In this specification, an “engine ” or “software engine,” refers to a software implemented input/output system that provides an output that is different from the input. An engine can be an encoded block of functionality, such as a library, a platform, a software development kit (“SDK”), or an object Each engine can be implemented on any appropriate type of computing device, e g., servers, mobile phones, tablet computers, notebook computers, music players, e-book readers, laptop or desktop computers, PDAs, smart phones, or other stationary or portable devices, that includes one or more processors and computer readable media Additionally, two or more of the engines may be implemented on the same computing device, or on different computing devices.

[00102] The processes and logic flows described in this specification can be performed by one or more programmable computers executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g , an FPGA (field programmable gate array ) or an ASIC (application specific integrated circuit).

[00103] Computers suitable for the execution of a computer program include, by way of example, can be based on general or special purpose microprocessors or both, or any other kind of central processing unit. Generally, a central processing unit will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a central processing unit tor performing or executing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks However, a computer need not have such devices. Moreover, a computer can be embedded in another device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio or video player, a game console a Global Positioning System (GPS) receiver, or a portable storage device, e.g., a universal serial bus (USB ) flash drive, to name just a few.

[00104] Computer readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.

[00105] To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on a computer having a display device, e g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide tor interaction with a user as well, for example, feedback provided to the user can be any form of sensory feedback, e.g , visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user’s client device in response to requests received from the web browser.

[00106] Embodiments of the subject matter described in this specification can be implemented in a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e g., a client computer having a graphical user interface or a Web browser through which a user can Interact with an implementation of the subject matter described in tins specification, or any combination of one or more such back end, middleware, or front end components The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (‘"WAN”), e.g , the Internet

[00107] The computing system can include clients and sewers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.

[00108] While this specification contains many specific implementation details, these should not be construed as limitations on the scope of any invention or of what may be claimed, but rather as descriptions of features that may be specific to particular embodiments of particular inventions Certain features that are described in this specification in the context of separate embodiments cart also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable sub combination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a sub combination or variation of a sub combination.

[00109] Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system modules and components in the embodiments described above should not be understood as requiring such separation in ail embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products. [00110] Particular embodiments of the subject matter have been described. Other embodiments are within the scope of the following claims For example, the actions recited in the claims can be performed in a different order and still achieve desirable results. As one example, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In certain implementations, multitasking and parallel processing may be advantageous.