Source-linked AI summary
Building Program Vector Representations for Deep Learning
Lili Mou, Ge Li, Yuxuan Liu, Hao Peng, Zhi Jin, Yan Xu, Lu Zhang
TL;DR
Program analysis lacked suitable representations for training deep networks because program symbols and structures differ from natural-language inputs. The paper proposes AST-based coding-criterion vectors, evaluates them qualitatively and quantitatively, and uses them in program classification. The representations are reported successful, and the deep classifier outperforms shallow baselines.
Problem
Program analysis needs representations that make deep learning applicable despite the structural and discrete nature of programs.
Method
The paper learns distributed vector representations for AST nodes using a coding criterion, then feeds them to a deep neural network for program classification.
Results
The learned representations successfully capture AST-node relationships, and TCNN improves program-classification accuracy by more than 4% over the SVM baseline.
Takeaways & Limitations
The experiments provide primary evidence that deep learning is feasible for program analysis.
Abstract
from arXiv · showhide
Deep learning has made significant breakthroughs in various fields of artificial intelligence. Advantages of deep learning include the ability to capture highly complicated features, weak involvement of human engineering, etc. However, it is still virtually impossible to use deep learning to analyze programs since deep architectures cannot be trained effectively with pure back propagation. In this pioneering paper, we propose the "coding criterion" to build program vector representations, which are the premise of deep learning for program analysis. Our representation learning approach directly makes deep learning a reality in this new field. We evaluate the learned vector representations both qualitatively and quantitatively. We conclude, based on the experiments, the coding criterion is successful in building program representations. To evaluate whether deep learning is beneficial for program analysis, we feed the representations to deep neural networks, and achieve higher accuracy in the program classification task than "shallow" methods, such as logistic regression and the support vector machine. This result confirms the feasibility of deep learning to analyze programs. It also gives primary evidence of its success in this new field. We believe deep learning will become an outstanding technique for program analysis in the near future.
I. INTRODUCTION
Deep learning offers powerful feature learning with little human engineering, but program analysis lacked suitable representations and effective pretraining. The paper introduces AST-based coding criterion representations and evaluates deep neural networks for program classification.
- Deep learning captures complicated features with little human engineering, motivating its application to program analysis.
- Pure back propagation cannot effectively train deep networks for programs because gradients may vanish or explode, yielding poor features and performance.
- The coding criterion builds program vector representations from ASTs, providing a representation-based pretraining method for deep architectures.
- A deep neural network using learned representations achieved higher program-classification accuracy than shallow methods.
- The paper contributes deep and representation learning techniques, program-analysis infrastructure, and released source codes, datasets, and learned representations.
B. Barriers of Deep Learning for Program Analysis
Program symbols are discrete and structurally organized, so direct neural-network input and generic NLP representations are inadequate. The paper therefore argues that new program-specific vector representations are needed.
- Deep learning remains difficult for program analysis despite its capacity to capture complicated features.
- Program symbols cannot be fed directly into neural networks, motivating real-valued distributed vectors whose dimensions encode symbol features.
- Randomly initialized representations can produce poor optimization and generalization in deep networks, whereas unsupervised pretraining offers an alternative.
- Programming languages contain indentation, branches, loops, and nested structures unlike the one-dimensional organization assumed by natural-language methods.
- The paper identifies an unmet need for new approaches to build program vector representations.
A. Deep Neural Networks
Deep neural networks stack nonlinear layers to learn hierarchical features, but their training difficulty prompted pretraining methods. These methods cannot be applied directly when inputs are discrete program symbols.
- A single neural layer maps an input vector to an output vector using model parameters, an activation function, and gradient-descent training.
- Multiple nonlinear layers provide greater modeling power and can represent complex functions, although shallow architectures may require exponentially many hidden units.
- Deep architectures organize local features at lower layers and abstract features at higher layers, but are difficult to train.
- RBMs and autoencoders introduced layer-wise pretraining that learns data features before supervised fine-tuning.
- Neural networks and standard pretraining approaches work with continuous data but cannot be applied directly to discrete words and program symbols.
B. Existing Representation Learning Approaches in NLP
NLP representation learning maps words to vectors using sequential or local-context objectives, but programming languages contain richer structure and variable identifiers. The paper selects AST nodes as a feasible granularity for program representations.
- B. Existing Representation Learning Approaches in NLP: NLP methods learn word vectors from language-modeling, neighboring-word, or related context objectives.
- B. Existing Representation Learning Approaches in NLP: Markovian approaches capture local context, while recurrent networks target long-term dependencies but can suffer vanishing or exploding gradients.
- B. Existing Representation Learning Approaches in NLP: Programming languages require new representation-learning algorithms because they contain richer and more explicit structural information than natural languages.
- A. The Granularity: Character-level representations can confuse related strings such as double and doubles, which have different programming meanings.
- A. The Granularity: Token-level representations face severe problems because programmers can declare effectively unbounded identifiers.
- A. The Granularity: AST-node representations are finite and compressed, preserve structural information, and support learning, although they treat all identifiers as the same symbol.
B. Formalization
The coding criterion learns AST-node vectors by reconstructing parent representations from children, while a continuous binary tree preserves child-position information with two shared weight matrices.
- Coding criterion: The coding criterion represents each AST node through its children’s representations in a single neural layer.
- Node representations: Each node vector has 30 feature dimensions in the reported experimental setting.
- Node representations: Child contributions use weight matrices scaled by the number of leaves beneath each child.
- Continuous binary tree: The continuous binary tree uses two matrices, Wl and Wr, and expresses every child weight as their linear combination regardless of child count.
- Continuous binary tree: The model retains relative child-position information that dynamic pooling would discard.
- Training objective: Negative sampling prevents trivial zero representations by requiring corrupted samples to have larger coding distance.
C. Training
Training uses stochastic gradient descent with momentum, negative samples, backpropagation, and repeated parameter updates until convergence to learn useful AST-node features.
- Optimization: Parameters are randomly initialized, then updated with backpropagation for each positive and negative training sample.
- Optimization: The training process repeats cost computation, derivative calculation, and parameter updates until convergence.
- Representation learning: The shallow coding-criterion pretraining stage learns useful features for AST nodes through backpropagation.
- Optimization: Algorithm 1 summarizes the stochastic-gradient-descent-with-momentum training procedure.
- Optimization: Momentum adds decayed derivatives from the previous iteration to the current derivatives to speed training.
V. EXPERIMENTS
The experiments evaluate learned representations qualitatively and use them as inputs to deep neural networks for supervised program classification.
- Experimental design: Nearest-neighbor queries and k-means clustering provide qualitative evaluations of the learned representations.
- Supervised evaluation: The learned representations are fed forward to deep neural networks for program classification.
- Supervised evaluation: The deep tree-based convolutional neural network achieves higher accuracy than baseline methods.
- Supervised evaluation: Meaningful pretrained representations make deep architectures much easier to train.
A. Qualitative Evaluation: Nearest Neighbor Queries and k-means Clustering
Nearest-neighbor and k-means analyses show that learned vectors organize AST symbols according to functional relationships, while distributed representations support more than similarity alone.
- Nearest-neighbor queries: Nearest-neighbor queries find ID and Constant as mutual nearest neighbors, alongside groups associated with data manipulation, control flow, and declarations.
- k-means clustering: With k=3, clustering separates symbols mainly into data-related, declaration, and control-flow groups.
- Evaluation interpretation: The qualitative results characterize symbol relationships effectively and are consistent with human understanding of programs.
- Representation learning: Representation learning is intended to capture distributed, multidimensional features rather than produce similarity as its only outcome.
B. Quantitative Evaluation: Improvement for Supervised Learning
The evaluation tests whether learned program representations improve supervised program classification and finds benefits for both training optimization and generalization. Using TCNN, the representations outperform shallow baselines and support the feasibility of deep learning for program analysis.
- Evaluation setup: The study feeds learned representations to a Tree-based Convolutional Neural Network (TCNN) for program classification.The dataset uses source code from four programming problems and a 3:1:1 training, cross-validation, and testing split.
- Optimization and generalization: Random initialization leaves deep TCNN training ineffective, whereas representation-based initialization sharply reduces training and cross-validation errors after about 15 epochs.The comparison attributes the difference to pretraining that supplies meaningful parameter initialization.
- Classification accuracy: 81.16% accuracy is achieved by logistic regression, SVM improves the result by 10%, and TCNN further improves accuracy by more than 4%.These results compare bag-of-words baselines with the deep model in program classification.
- Overall findings: Nearest-neighbor querying and k-means clustering provide qualitative evaluation, while program classification shows the learned representations benefit supervised learning.The authors conclude that the AST-based coding criterion is a successful program representation learning algorithm.
- Overall findings: The program classification experiment provides primary evidence that deep learning can analyze programs.The conclusion is limited to the reported experimental setting.
VI. LOOKING FORWARD TO THE FUTURE
The paper identifies multiple ways to model programs beyond ASTs, including statement sequences and two-dimensional source-code signals. These perspectives trade structural information against neighboring or visual features and broaden possible deep-learning approaches.
- Future directions: The authors present these alternative program representations as promising research directions for deep learning in program analysis.The discussion frames deep learning as a prospective method for future program-analysis tasks.
- AST perspective: The authors hypothesize that structural information is important and use ASTs as one perspective for modeling programs.They explicitly note that ASTs are not the only possible representation.
- Sequence perspective: A sequence-of-statements perspective captures neighboring information and local patterns, although it may lose some structural information.The paper connects this perspective to traditional program-analysis tasks such as API usage pattern mining.
- Two-dimensional perspective: A two-dimensional source-code perspective treats programs as signals whose indentation and linefeeds may provide useful semantic features.The paper proposes applying computer-vision techniques such as convolutional neural networks to this representation.
B. Integrating Prior about Programs to Network Architectures
The paper considers how program-specific priors can be integrated into neural architectures, including AST locality and formal-methods knowledge. It identifies combining neural and formal methods as difficult but potentially beneficial, while motivating further program-analysis applications.
- AST priors: Tree-based convolutional neural networks are proposed to capture local features of abstract syntax trees.The paper reports primary results for this approach in Section V-B.
- Formal-methods priors: Formal methods offer mathematical deductions that can guarantee either no false positives or no false negatives for some program-analysis properties.The passage frames formal methods as an approximation because non-trivial program properties are undecidable.
- Formal-methods priors: Combining formal methods with neural networks is currently difficult, although the paper states that doing so could benefit both techniques.
- Applications: The paper identifies code clone detection, bug detection, and code retrieval as promising applications of deep learning for program analysis.
- Open questions: The study addresses open questions about program modeling, integrating human priors, and applying deep learning in this new field.
- Future direction: The authors expect deep learning to become an outstanding approach to program analysis and call for additional studies.