TL;DR
This paper introduces "einspace," a novel and highly expressive search space for neural architecture search (NAS) built from fundamental operations using a probabilistic context-free grammar. This allows NAS to discover a wider range of architectures, including shifts between different paradigms like CNNs and Transformers, moving beyond the limitations of current NAS methods.
What Problem Does This Paper Address?
Neural Architecture Search (NAS) aims to automate the design of high-performing neural networks. However, existing NAS methods often rely on search spaces that are too restrictive, limiting their ability to discover fundamentally new architectures. These spaces are typically designed around specific building blocks (e.g., convolutions) and struggle to represent diverse architectural families like transformers or to facilitate significant design shifts. This has led to a situation where manually designed architectures still dominate, despite the promise of NAS. The authors argue that to unlock the full potential of NAS for transformative design, we need more expressive search spaces built from more fundamental operations.
Methods
The core contribution is einspace, a search space defined by a parameterized probabilistic context-free grammar (PCFG). This approach allows for:
- Fundamental Operations: Architectures are built from a set of basic operations (branching, aggregation, routing, computation) rather than high-level blocks.
- Expressive Grammar: The PCFG allows for unbounded derivations, enabling the representation of diverse network sizes, depths, and macro/micro structures.
- Parameterization: Rules are parameterized to ensure valid architecture generation and to incorporate priors (e.g., feature modes like "Im" for CNNs and "Col" for Transformers).
- Probabilistic Nature: Probabilities are assigned to production rules to balance search space complexity and guide the sampling process.
- Derivation Trees: Architectures are represented as derivation trees, facilitating mutations that can alter both macro structure and individual components.
The authors also explore simple search strategies like random sampling, random search, and regularized evolution, finding that in such an expressive space, the choice of strategy is crucial. They highlight the benefit of initializing search with existing state-of-the-art architectures as priors.
Datasets
The paper evaluates einspace on the Unseen NAS datasets, which comprise eight diverse classification tasks across vision, language, audio, and chess. They also conduct experiments on the NASBench360 benchmark.
Key Insights and Ideas
- Expressivity is Key: The paper strongly advocates for the importance of search space expressivity in enabling NAS to discover novel and transformative architectures, rather than just incremental improvements within existing paradigms.
- Fundamental Operations Unlock Diversity: Building architectures from basic operations, rather than pre-defined blocks, is crucial for representing a wide range of existing and potentially new architectural families (CNNs, Transformers, MLPs) within a single search space.
- Priors Still Matter: While einspace is highly expressive, initializing the search with strong, human-designed architectures significantly boosts performance, demonstrating the value of incorporating prior knowledge.
- Search Strategy is Crucial: In a large and expressive search space like einspace, simple search strategies like random search perform poorly, underscoring the need for more sophisticated search algorithms to effectively navigate the space.
Key Results
- Competitive Performance: Using simple search strategies (random search, regularized evolution), einspace achieves competitive results across a diverse set of tasks, often outperforming baseline NAS methods.
- Architectural Improvements: When initializing search with existing architectures (ResNet18, WideResNet-16-4, ViT, MLP-Mixer), einspace consistently finds improved versions of these architectures, and in some cases, surpasses existing state-of-the-art results. For example, on the Language dataset, RE(Mix) found an architecture with a 5.76% improvement over ResNet18.
- Flexibility Demonstrated: The paper shows that einspace can represent diverse architectures like ResNets, Transformers, and MLP-Mixer within a single framework.
- Runtime Trade-offs: While gradient-based NAS methods are faster, einspace's evolutionary search, though longer, can find more diverse and potentially better architectures.
Limitations and Future Work
- Search Space Size: The immense size and unbounded nature of einspace make one-shot NAS methods challenging.
- Efficiency of Search: The evolutionary search strategy used is computationally expensive. Future work could focus on developing more efficient search algorithms.
- Ambiguity in Derivations: Multiple derivation trees can lead to the same architecture, posing a challenge for search space size reduction.
- Limited Operation Set: The current einspace does not support recurrent computations (RNNs) or state-space models like Mamba. Integrating these would further enhance its expressivity.
- Parameterization Complexity: While parameterization helps ensure valid architectures, managing these parameters during sampling can be complex.
The authors suggest future work on developing intelligent search strategies, exploring recurrent modules, and further refining the parameterization and probabilistic aspects of the grammar.
Summary updated