Learning Geolocations for Cold-Start and Hard-to-Resolve Addresses via Deep Metric Learning

Govind, Saurabh SohoneyEMNLP 2022

TL;DR

This paper tackles the challenge of geolocating addresses in emerging geographies where data is sparse and addresses are often unstructured or incomplete. They introduce a novel deep metric learning approach that learns to embed addresses in a way that captures their geospatial relationships, significantly improving geocoding accuracy for these difficult cases.

What Problem Does This Paper Address?

Delivering packages to customers' doorsteps is a core function of modern logistics. However, in many emerging economies, addresses are not standardized, often contain errors, or lack detailed information like building numbers. This makes it incredibly difficult for delivery systems to accurately pinpoint a customer's location. Existing methods often rely on historical delivery data or matching to known landmarks, which fail for "cold-start" addresses (those with little to no delivery history) or "hard-to-resolve" addresses (those with missing or inaccurate information). The paper aims to solve this by learning to geolocate these challenging addresses, even when they are encountered for the first time.

Methods

The core of the proposed solution is a deep metric learning framework. Instead of directly predicting coordinates, the model learns to embed address text into a vector space where the distance between embeddings reflects the actual geospatial distance between the addresses.

Here's a breakdown of their approach:

  • Weak Supervision with Triplet Loss: Since manually labeling address pairs for training is infeasible, they use historical delivery data to create "weakly labeled" training examples. They employ a triplet loss function, which aims to pull "positive" (geospatially close) address embeddings together and push "negative" (geospatially distant) address embeddings apart.
  • RoBERTa as the Base Model: They leverage the RoBERTa transformer model, pre-trained on a large corpus of address data, as the foundation for their embeddings. This allows the model to understand the nuances of address text.
  • H3 Geospatial Indexing for Neighbor Sampling: To efficiently sample positive and negative neighbors for triplet loss, they use the H3 hexagonal grid system. This hierarchical structure helps them identify addresses that are likely to be close or far from an anchor address.
  • Neighborhood-Based Geocoding: For inference, the model retrieves the nearest neighbors of a given address based on its learned embedding. A Kernel Density Estimation (KDE) is then used over the geocodes of these neighbors to predict a final geocode, often representing a neighborhood rather than a precise building.

Datasets

The paper uses real-world address data from India (IN) and the United Arab Emirates (UAE).

  • Training Data: They utilize historical delivery scan data, which includes millions of shipments and unique addresses, to generate weakly supervised training pairs for their metric learning model.
  • Evaluation Data: For evaluation, they consider a subset of "hard-to-resolve" addresses from recent shipments, specifically those for which the existing production system could not provide a confident geocode.

Key Insights and Ideas

  • Geospatial Semantics in Embeddings: The most significant insight is that by framing geocoding as a metric learning problem, address embeddings can be trained to implicitly capture geospatial relationships. This is crucial for understanding addresses that lack explicit geographical cues.
  • Weak Supervision is Sufficient: The success of their approach demonstrates that high-quality geocoding for challenging addresses can be achieved with weakly supervised learning, avoiding the need for expensive manual annotation.
  • H3 for Efficient Neighbor Discovery: The use of H3 indexing is a clever way to scale the neighbor sampling process, making the training of metric learning models feasible for large datasets.
  • Neighborhood-Level Geocoding as a Practical Solution: For hard-to-resolve addresses, predicting a neighborhood rather than a precise building is a pragmatic and effective approach that still significantly improves delivery efficiency.

Key Results

The proposed deep metric learning model, RoBERTa-Triplet-H3, significantly outperforms the existing production baseline and other baseline models on hard-to-resolve addresses:

  • Delivery Defects Reduction:
    • India: 22% reduction in DPMO (Defects Per Million Opportunities) where the predicted geocode is more than Y meters away from the actual location.
  • UAE: 54% reduction in DPMO.
  • Distance Reduction:
    • India: 43% reduction in the 50th percentile (p50) distance between learned and actual delivery locations.
  • UAE: 90% reduction in p50 distance.
  • Embedding Quality: Cosine similarity between positive address pairs is significantly higher, and triplet accuracy is substantially improved compared to baseline models like FastText and general RoBERTa. Qualitative analysis shows that the embeddings lead to smoother, more meaningful clusters of addresses.

Limitations and Future Work

  • Limitations:
    • The paper focuses on the geocoding task and does not extensively explore the use of neighborhood polygons for delivery planning.
  • While the model is trained without manual labels, it does rely on historical delivery scans, which might introduce biases if certain areas are underrepresented in past data.
  • The current work is primarily for English addresses; extending to multi-lingual addresses is a future direction.
  • Future Work:
    • Online Experiments: Conducting real-world online experiments to validate the offline results.
  • Multi-lingual Addresses: Adapting the model to handle code-switching and different languages.
  • Enhanced Neighbor Filtering: Exploring pairwise cross-encoders to further refine the retrieved neighbors.
  • Geospatial Constraints: Incorporating natural obstacles (water bodies, highways) into neighborhood learning.
  • Downstream Applications: Leveraging the learned embeddings for other tasks like address correction, package sorting, and delivery station assignment optimization.

Summary updated

BibTeX
@inproceedings{govind2022learning,
  author = {Govind and Saurabh Sohoney},
  title = {{Learning Geolocations for Cold-Start and Hard-to-Resolve Addresses via Deep Metric Learning}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2022},
}
Figure