Convolutional Embedding for Edit Distance

• URL: http://arxiv.org/abs/2001.11692v3
• Date: Fri, 22 May 2020 06:27:37 GMT
• Title: Convolutional Embedding for Edit Distance
• Authors: Xinyan Dai, Xiao Yan, Kaiwen Zhou, Yuxuan Wang, Han Yang, James Cheng
• Abstract summary: CNN-ED embeds edit distance into Euclidean distance for fast approximate similarity search. CNN-ED outperforms data-independent CGK embedding and RNN-based GRU embedding in terms of both accuracy and efficiency.
• Score: 24.65097766064397
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Edit-distance-based string similarity search has many applications such as spell correction, data de-duplication, and sequence alignment. However, computing edit distance is known to have high complexity, which makes string similarity search challenging for large datasets. In this paper, we propose a deep learning pipeline (called CNN-ED) that embeds edit distance into Euclidean distance for fast approximate similarity search. A convolutional neural network (CNN) is used to generate fixed-length vector embeddings for a dataset of strings and the loss function is a combination of the triplet loss and the approximation error. To justify our choice of using CNN instead of other structures (e.g., RNN) as the model, theoretical analysis is conducted to show that some basic operations in our CNN model preserve edit distance. Experimental results show that CNN-ED outperforms data-independent CGK embedding and RNN-based GRU embedding in terms of both accuracy and efficiency by a large margin. We also show that string similarity search can be significantly accelerated using CNN-based embeddings, sometimes by orders of magnitude.

Related papers

• Revisiting CNNs for Trajectory Similarity Learning [20.311950784166388]
  We introduce ConvTraj, incorporating both 1D and 2D convolutions to capture sequential and geo-distribution features of trajectories. We show that ConvTraj achieves state-of-the-art accuracy in trajectory similarity search.
  arXiv  Detail & Related papers  (2024-05-30T07:16:03Z)
• Dynamic Semantic Compression for CNN Inference in Multi-access Edge Computing: A Graph Reinforcement Learning-based Autoencoder [82.8833476520429]
  We propose a novel semantic compression method, autoencoder-based CNN architecture (AECNN) for effective semantic extraction and compression in partial offloading. In the semantic encoder, we introduce a feature compression module based on the channel attention mechanism in CNNs, to compress intermediate data by selecting the most informative features. In the semantic decoder, we design a lightweight decoder to reconstruct the intermediate data through learning from the received compressed data to improve accuracy.
  arXiv  Detail & Related papers  (2024-01-19T15:19:47Z)
• Do deep neural networks have an inbuilt Occam's razor? [1.1470070927586016]
  We show that structured data combined with an intrinsic Occam's razor-like inductive bias towards simple functions counteracts the exponential growth of functions with complexity. This analysis reveals that structured data, combined with an intrinsic Occam's razor-like inductive bias towards (Kolmogorov) simple functions that is strong enough to counteract the exponential growth of functions with complexity, is a key to the success of DNNs.
  arXiv  Detail & Related papers  (2023-04-13T16:58:21Z)
• Model-based inexact graph matching on top of CNNs for semantic scene understanding [6.106023882846558]
  Deep learning pipelines for semantic segmentation often ignore structural information available on annotated images used for training. We propose a novel post-processing module enforcing structural knowledge about the objects of interest to improve segmentation results. Our approach is shown to be resilient to small training datasets that often limit the performance of deep learning methods.
  arXiv  Detail & Related papers  (2023-01-18T12:23:10Z)
• Attention-based Feature Compression for CNN Inference Offloading in Edge Computing [93.67044879636093]
  This paper studies the computational offloading of CNN inference in device-edge co-inference systems. We propose a novel autoencoder-based CNN architecture (AECNN) for effective feature extraction at end-device. Experiments show that AECNN can compress the intermediate data by more than 256x with only about 4% accuracy loss.
  arXiv  Detail & Related papers  (2022-11-24T18:10:01Z)
• What Can Be Learnt With Wide Convolutional Neural Networks? [69.55323565255631]
  We study infinitely-wide deep CNNs in the kernel regime. We prove that deep CNNs adapt to the spatial scale of the target function. We conclude by computing the generalisation error of a deep CNN trained on the output of another deep CNN.
  arXiv  Detail & Related papers  (2022-08-01T17:19:32Z)
• Large-Margin Representation Learning for Texture Classification [67.94823375350433]
  This paper presents a novel approach combining convolutional layers (CLs) and large-margin metric learning for training supervised models on small datasets for texture classification. The experimental results on texture and histopathologic image datasets have shown that the proposed approach achieves competitive accuracy with lower computational cost and faster convergence when compared to equivalent CNNs.
  arXiv  Detail & Related papers  (2022-06-17T04:07:45Z)
• ACDC: Weight Sharing in Atom-Coefficient Decomposed Convolution [57.635467829558664]
  We introduce a structural regularization across convolutional kernels in a CNN. We show that CNNs now maintain performance with dramatic reduction in parameters and computations.
  arXiv  Detail & Related papers  (2020-09-04T20:41:47Z)
• Approximation and Non-parametric Estimation of ResNet-type Convolutional Neural Networks [52.972605601174955]
  We show a ResNet-type CNN can attain the minimax optimal error rates in important function classes. We derive approximation and estimation error rates of the aformentioned type of CNNs for the Barron and H"older classes.
  arXiv  Detail & Related papers  (2019-03-24T19:42:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.