Embeddings and labeling schemes for A*
A* is a classic and popular method for graphs search and path finding. It assumes the existence of a heuristic function $h(u,t)$ that estimates the shortest distance from any input node $u$ to the destination $t$. Traditionally, heuristics have been handcrafted by domain experts. However, over the last few years, there has been a growing interest in learning heuristic functions. Such learned heuristics estimate the distance between given nodes based on "features" of those nodes. In this paper we formalize and initiate the study of such feature-based heuristics. In particular, we consider heuristics induced by norm embeddings and distance labeling schemes, and provide lower bounds for the tradeoffs between the number of dimensions or bits used to represent each graph node, and the running time of the A* algorithm. We also show that, under natural assumptions, our lower bounds are almost optimal.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Permutation Invariant Representations with Applications to Graph Deep Learning
This paper presents primarily two Euclidean embeddings of the quotient space generated by matrices that are identified modulo arbitrary row permutations. The original application is in deep learning on graphs where the l…
Deep LearningDisentangling Sampling and Labeling Bias for Learning in Large-Output Spaces
Negative sampling schemes enable efficient training given a large number of classes, by offering a means to approximate a computationally expensive loss function that takes all labels into account. In this paper, we pres…
RetrievalCoding for Crowdsourced Classification with XOR Queries
This paper models the crowdsourced labeling/classification problem as a sparsely encoded source coding problem, where each query answer, regarded as a code bit, is the XOR of a small number of labels, as source informati…
ClassificationGeneral ClassificationTowards Assessing Argumentation Annotation - A First Step
This paper presents a first attempt at using Walton{'}s argumentation schemes for annotating arguments in Swedish political text and assessing the feasibility of using this particular set of schemes with two linguistical…
Locally-Contextual Nonlinear CRFs for Sequence Labeling
Linear chain conditional random fields (CRFs) combined with contextual word embeddings have achieved state of the art performance on sequence labeling tasks. In many of these tasks, the identity of the neighboring words …
Chunkingnamed-entity-recognitionNamed Entity RecognitionNamed Entity Recognition (NER)+1