Label prediction in neural networks (NNs) has O(n) complexity proportional to the number of classes. This holds true for classification using fully connected layers and cosine similarity with some set of class prototypes. In this paper we show that if NN latent space (LS) geometry is known and possesses specific properties, label prediction complexity can be significantly reduced. This is achieved by associating label prediction with the O(1) complexity closest cluster center search in a vector system used as target for latent space configuration (LSC). The proposed method only requires finding indexes of several largest and lowest values in the embedding vector making it extremely computationally efficient. We show that the proposed method does not change NN training accuracy computational results. We also measure the time required by different computational stages of NN inference and label prediction on multiple datasets. The experiments show that the proposed method allows to achieve up to 11.6 times overall acceleration over conventional methods. Furthermore, the proposed method has unique properties which allow to predict the existence of new classes.
Figures & tables
exp.
n dim
n classes
Dataset size
Acc. cossim, %
Acc. new, %
10
1000
1281k
94.5
94.5
23
50k
50k
98.3
98.3
48
300k
300k
96.2
96.2
Table 1: The comparison of training accuracy calculation results with cossim and the proposed method.
exp.
n classes
n dim
Batch size
t d , s
t f , s
t c , s
t n , s
K s
K t
1
1m
47
3584
4536
6
20
1.6
12
1.003
2
5m
69
2560
4439
4
175
2.3
76
1.04
3
10m
82
1024
4325
8.6
805
3.4
238
1.18
4
20m
97
256
4444
33
7350
4
1836
2.64
5
30m
107
64
4334
126
47244
8.2
6050
11.57
Table 2: The time required by different computational stages of model inference on 1m images with cossim and the proposed method with maximum possible batch size for 40GB GPU memory.
exp.
n classes
n dim
Batch size
t d , s
t f , s
t c , s
t n , s
K s
K t
1
1m
47
256
4411
33
97
3.1
31
1.02
2
5m
69
256
4235
33
1258
3.1
403
1.29
3
10m
82
256
4232
33
1825
3.7
485
1.43
4
20m
97
256
4444
33
7350
4
1836
2.64
5
30m
107
256
4421
33
-
3.7
-
-
6
50m
121
256
4290
31
-
3.6
-
-
Table 3: The time required by different computational stages of model inference on 1m images with cossim and the proposed method with fixed batch size of 256. Dash symbol indicates that cossim can no longer be used.
Figure 1: (a) The total time required to obtain labels for 1m images depending on n classes with cossim and the proposed method (dashed line indicates where batch size becomes too small for cossim to be applicable), and (b) the total acceleration coefficient K t as function of n classes (see Table 2 ).
Figure 2: A “toy” example of the dog-only detection system receiving cat queries: red arrows represent labeled centers, black arrow represents the unlabeled center, red digits represent data labels, black roman numerals represent center indexes, dog images are example classes 1-3, cat images correspond to example queries q 1 - q 3 . Blue lines correspond to decision boundaries, or angles where closest centers change.
Finding K most similar elements for a query in a large gallery of neural network (NN) embeddings is essential in various areas of computer science and industrial applications of artificial intelligence. This paper proposes search algorithms for structured latent spaces (LS) of NNs which allow to speed up top K item retrieval owing to O(1) complexity small candidate gallery subset search. ArcFace-pretrained IResNet50 models are finetuned using Latent Space Configuration (LSC) methodology to obtain new distribution of embeddings with desired geometric properties. Applying the proposed algorithms to embeddings obtained from finetuned models leads to several times speed-up over baseline exhaustive search. Specifically, we report up to 3 times speed-up on GPU and 40% speed-up on CPU compared to the baseline method GPU speed. These results are obtained for the original and reduced numbers of LS dimensions. The results show that LS dimensionality reduction allows to further accelerate the search and even improve rank-N metrics.
Nikita Gabdullin, Anton Raskovalov
Joint Stock "Research and production company "Kryptonite"
Neurosymbolic AI combines neural networks with symbolic programs to create robust and explainable predictions. One such framework is NeurASP, which trains a neural network to predict concepts and reasons over them using rules written in answer set programming (ASP) to solve downstream tasks. Crucially, labels are only provided for the downstream prediction produced by the symbolic rules, not for the latent concepts themselves. Backpropagation through the non-differentiable ASP component requires expensive probability and gradient calculations, which has hindered scalability to more sophisticated tasks. In this paper, we address the current limitations of NeurASP by improving its computational performance through vectorization, batch processing and caching of intermediate computations during training. We compare computation speeds between the original and our new implementation of NeurASP and report speedups of multiple orders of magnitude for larger tasks. To this end, we propose a new dataset of difficult tasks involving playing cards, which we use to test the capabilities of NeurASP's enhanced learning function.
Evaluating candidate architectures in neural architecture search (NAS) faces an inherent trade-off: on the one hand, reliable performance labels are limited because training and evaluating architectures is costly; on the other hand, zero-cost proxies (ZCPs) are cheap to compute at large scale but can be noisy. Yet, how to effectively combine these two sources of supervision remains unclear. In this paper, we propose PPNAS, a novel prediction-powered inference (PPI) approach for NAS. PPNAS fuses (1) a small set of architectures with observed performance labels and (2) a large set of architectures with ZCP information. To combine these two sources of supervision, PPNAS exploits the ordinal information provided by ZCPs to construct additional pairwise ranking supervision, while PPI debiases systematic discrepancies between ZCP-based and true performance rankings. We evaluate PPNAS in end-to-end predictor-based NAS, where it achieves state-of-the-art under limited evaluation budgets. To the best of our knowledge, PPNAS is the first prediction-powered approach for label-efficient NAS.
Pascal Janetzky, Yuxin Wang, Michael Klar +1
Bosch Center for Artificial Intelligence · LMU Munich Munich Center for Machine Learning(MCML)