检索结果-内蒙古大学图书馆

QUANTUM LOVÁSZ LOCAL LEMMA: SHEARER’S BOUND IS TIGHT

学校读者我要写书评

暂无评论

arXiv 2018年

作者： He, Kun Li, Qian Sun, Xiaoming Zhang, Jiapeng The Key Lab of Data Engineering and Knowledge Engineering MOE Renmin University of China Beijing China Institute of Computing Technology Chinese Academy of Sciences University of Chinese Academy of Sciences Beijing China University of Southern California United States

The Lovász Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all bad events under some weakly dependent conditions. In a seminal paper, Ambainis, Kempe, and Sattath (JACM 2012) introduced a quantum version LLL (QLLL) which shows the possibility of avoiding all "bad" Hamiltonians under some weakly dependent condition, and applied QLLL to the random k-QSAT problem. Sattath, Morampudi, Laumann, and moessner (PNAS 2015) extended Ambainis, Kempe, and Sattath’s result and showed that Shearer’s bound is a sufficient condition for QLLL, and conjectured that Shearer’s bound is indeed the tight condition for QLLL. In this paper, we affirm this conjecture. Precisely, we prove that Shearer’s bound is tight for QLLL, i.e., the relative dimension of the smallest satisfying subspace is completely characterized by the independent set polynomial. Our result implies the tightness of Gilyén and Sattath’s algorithm (FOCS 2017), and also implies that the lattice gas partition function fully characterizes quantum satisfiability for almost all Hamiltonians with large enough qudits (Sattath, Morampudi, Laumann and moessner, PNAS 2015). The commuting LLL (CLLL), which focuses on commuting local Hamiltonians, is also investigated here. We prove that the tight regions of CLLL and QLLL are different in general. This result indicates that it is possible to design an algorithm for CLLL which is still efficient beyond Shearer’s bound. Copyright © 2018, The Authors. All rights reserved.

关键词： Hamiltonians

SALI: A Scalable Adaptive Learned Index Framework based on Probability Models

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Ge, Jiake Zhang, Huanchen Shi, Boyu Luo, Yuanhui Guo, Yunda Chai, Yunpeng Chen, Yuxing Pan, Anqun Key Laboratory of Data Engineering and Knowledge Engineering MOE China Engineering Research Center of Database and Business Intelligence MOE China School of Information Renmin University of China China China and Shanghai Qi Zhi Institute China Tsinghua University China Tencent Inc China

The growth in data storage capacity and the increasing demands for high performance have created several challenges for concurrent indexing structures. One promising solution is learned indexes, which use a learning-based approach to fit the distribution of stored data and predictively locate target keys, significantly improving lookup performance. Despite their advantages, prevailing learned indexes exhibit constraints and encounter issues of scalability on multi-core data storage. This paper introduces SALI, the Scalable Adaptive Learned Index framework, which incorporates two strategies aimed at achieving high scalability, improving efficiency, and enhancing the robustness of the learned index. Firstly, a set of node-evolving strategies is defined to enable the learned index to adapt to various workload skews and enhance its concurrency performance in such scenarios. Secondly, a lightweight strategy is proposed to maintain statistical information within the learned index, with the goal of further improving the scalability of the index. Furthermore, to validate their effectiveness, SALI applied the two strategies mentioned above to the learned index structure that utilizes fine-grained write locks, known as LIPP. The experimental results have demonstrated that SALI significantly enhances the insertion throughput with 64 threads by an average of 2.04× compared to the second-best learned index. Furthermore, SALI accomplishes a lookup throughput similar to that of LIPP+. © 2023, CC BY-NC-ND.

关键词： Scalability

Deep knn for medical image classification 23rd

学校读者我要写书评

暂无评论

Deep knn for medical image classification

23rd International Conference on Medical Image Computing and Computer-Assisted Intervention, MICCAI 2020

作者： Zhuang, Jiaxin Cai, Jiabin Wang, Ruixuan Zhang, Jianguo Zheng, Wei-Shi School of Data and Computer Science Sun Yat-sen University Guangzhou China Department of Computer Science and Engineering Southern University of Science and Technology Shenzhen China Key Laboratory of Machine Intelligence and Advanced Computing MOE Guangzhou China Pazhou Lab Guangzhou China

ISBN: (纸本)9783030597092

Human-level diagnostic performance from intelligent systems often depends on large set of training data. However, the amount of available data for model training may be limited for part of diseases, which would cause the widely adopted deep learning models not generalizing well. One alternative simple approach to small class prediction is the traditional k-nearest neighbor (kNN). However, due to the non-parametric characteristics of kNN, it is difficult to combine the kNN classification into the learning of feature extractor. This paper proposes an end-to-end learning strategy to unify the kNN classification and the feature extraction procedure. The basic idea is to enforce that each training sample and its K nearest neighbors belong to the same class during learning the feature extractor. Experiments on multiple small-class and class-imbalanced medical image datasets showed that the proposed deep kNN outperforms both kNN and other strong classifiers. © Springer Nature Switzerland AG 2020.

关键词： Nearest neighbor search

Mitigating label-Noise for Facial Expression Recognition in the Wild

学校读者我要写书评

暂无评论

Mitigating Label-Noise for Facial Expression Recognition in ...

2022 IEEE International Conference on Multimedia and Expo, ICME 2022

作者： Yan, Huan Gu, Yu Zhang, Xiang Wang, Yantong Ji, Yusheng Ren, Fuji School of Computer and Information Hefei University of Technology S2AC Lab China Hefei University of Technology Key Laboratory of Knowledge Engineering with Big Data China Anhui Province Key Laboratory of Cyberspace Security Situation Awareness and Evaluation China National Institute of Informatics Tokushima University Japan

ISBN: (数字)9781665485630

ISBN: (纸本)9781665485630

label-noise constitutes a major challenge for facial expression recognition in the wild due to the ambiguity of facial expressions worsened by low-quality images. To deal with this problem, we propose a simple but effective label-noise Robust Network (LRN) which explores the inter-class correlations for mitigating ambiguity that usually happens between morphologically similar classes. Specifically, LRN leverages a multivariate normal distribution to model such correlations at the final hidden layer of the neural network to suppress the heteroscedastic uncertainty caused by inter-class label noise. Furthermore, LRN utilizes a confidence-based label-free loss to extract compact intra-class feature representations under label noise while preserving the intrinsic inter-class relationships. Experiments on three in-the-wild facial expression datasets demonstrates the superiority of our method. © 2022 IEEE.

关键词： Face recognition

Group based personalized search by integrating search behaviour and friend network

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Zhou, Yujia Dou, Zhicheng Wei, Bingzheng Xie, Ruobing Wen, Ji-Rong Gaoling School of Artificial Intelligence Renmin University of China School of Information Renmin University of China WeChat Search Application Department Tencent China Beijing Key Laboratory of Big Data Management and Analysis Methods Key Laboratory of Data Engineering and Knowledge Engineering MOE

The key to personalized search is to build the user profile based on historical behaviour. To deal with the users who lack historical data, group based personalized models were proposed to incorporate the profiles of similar users when re-ranking the results. However, similar users are mostly found based on simple lexical or topical similarity in search behaviours. In this paper, we propose a neural network enhanced method to highlight similar users in semantic space. Furthermore, we argue that the behaviour-based similar users are still insufficient to understand a new query when user's historical activities are limited. To tackle this issue, we introduce the friend network into personalized search to determine the closeness between users in another way. Since the friendship is often formed based on similar background or interest, there are plenty of personalized signals hidden in the friend network naturally. Specifically, we propose a friend network enhanced personalized search model, which groups the user into multiple friend circles based on search behaviours and friend relations respectively. These two types of friend circles are complementary to construct a more comprehensive group profile for refining the personalization. Experimental results show the significant improvement of our model over existing personalized search models. Copyright © 2021, The Authors. All rights reserved.

关键词： User profile

SAMPLING LOVÁSZ LOCAL LEMMA FOR GENERAL CONSTRAINT SATISFACTION SOLUTIONS IN NEAR-LINEAR TIME

学校读者我要写书评

暂无评论

arXiv 2022年

作者： He, Kun Wang, Chunyang Yin, Yitong The Key Lab of Data Engineering and Knowledge Engineering MOE Renmin University of China No. 59 Zhongguancun Street Haidian District Beijing China State Key Laboratory for Novel Software Technology Nanjing University 163 Xianlin Avenue Jiangsu Province Nanjing China

We give a fast algorithm for sampling uniform solutions of general constraint satisfaction problems (CSPs) in a local lemma regime. Suppose that the CSP has n variables with domain size at most q, each constraint contains at most k variables, shares variables with at most Δ constraints, and is violated with probability at most p by a uniform random assignment. The algorithm returns an almost uniform satisfying assignment in expected poly(q,k, Δ) ·(n) time, as long as a local lemma condition is satisfied: k · p · q2 · Δ5 ≤ C0 for a suitably small absolute constant C0. Previously, under similar local lemma conditions, sampling algorithms with running time polynomial in both nand Δ were only known for the almost atomic case, where each constraint is violated by a small number of forbidden local configurations. The key term Δ5 in our local lemma condition also improves the previously best known Δ7 for general CSPs [JPV21b] and Δ5.714 for atomic CSPs, including the special case of k-CNF [JPV21a, HSW21]. Our sampling approach departs from previous fast algorithms for sampling LLL, which were based on Markov chains. A crucial step of our algorithm is a recursive marginal sampler that is of independent interests. Within a local lemma regime, this marginal sampler can draw a random value for a variable according to its marginal distribution, at a cost independent of the size of the CSP. Copyright © 2022, The Authors. All rights reserved.

关键词： Constraint satisfaction problems

BADet: Boundary-Aware 3D Object Detection from Point Clouds

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Qian, Rui Lai, Xin Li, Xirong Key Lab of Data Engineering and Knowledge Engineering Renmin University of China Beijing100872 China School of Mathematics Renmin University of China Beijing100872 China

Currently, existing state-of-the-art 3D object detectors are in two-stage paradigm. These methods typically comprise two steps: 1) Utilize a region proposal network to propose a handful of high-quality proposals in a bottom-up fashion. 2) Resize and pool the semantic features from the proposed regions to summarize RoI-wise representations for further refinement. Note that these RoI-wise representations in step 2) are considered individually as uncorrelated entries when fed to following detection headers. Nevertheless, we observe these proposals generated by step 1) offset from ground truth somehow, emerging in local neighborhood densely with an underlying probability. Challenges arise in the case where a proposal largely forsakes its boundary information due to coordinate offset while existing networks lack corresponding information compensation mechanism. In this paper, we propose BADet for 3D object detection from point clouds. Specifically, instead of refining each proposal independently as previous works do, we represent each proposal as a node for graph construction within a given cut-off threshold, associating proposals in the form of local neighborhood graph, with boundary correlations of an object being explicitly exploited. Besides, we devise a lightweight Region Feature Aggregation Module to fully exploit voxel-wise, pixel-wise, and point-wise features with expanding receptive fields for more informative RoI-wise representations. We validate BADet both on widely used KITTI dataset and highly challenging nuScenes dataset. As of Apr. 17th, 2021, our BADet achieves on par performance on KITTI 3D detection leaderboard and ranks 1st on Moderate difficulty of Car category on KITTI BEV detection leaderboard. The source code is available at https://***/rui-qian/BADet. © 2021, CC BY.

关键词： Object detection

3D Object Detection for Autonomous Driving: A Survey

学校读者我要写书评

暂无评论

arXiv 2021年

Autonomous driving is regarded as one of the most promising remedies to shield human beings from severe crashes. To this end, 3D object detection serves as the core basis of perception stack especially for the sake of path planning, motion prediction, and collision avoidance etc. Taking a quick glance at the progress we have made, we attribute challenges to visual appearance recovery in the absence of depth information from images, representation learning from partially occluded unstructured point clouds, and semantic alignments over heterogeneous features from cross modalities. Despite existing efforts, 3D object detection for autonomous driving is still in its infancy. Recently, a large body of literature have been investigated to address this 3D vision task. Nevertheless, few investigations have looked into collecting and structuring this growing knowledge. We therefore aim to fill this gap in a comprehensive survey, encompassing all the main concerns including sensors, datasets, performance metrics and the recent state-of-the-art detection methods, together with their pros and cons. Furthermore, we provide quantitative comparisons with the state of the art. A case study on fifteen selected representative methods is presented, involved with runtime analysis, error analysis, and robustness analysis. Finally, we provide concluding remarks after an in-depth analysis of the surveyed works and identify promising directions for future work. © 2021, CC BY.

关键词： Object recognition

Injecting Numerical Reasoning Skills into knowledge Base Question Answering Models

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Feng, Yu Zhang, Jing Zhang, Xiaokang Liu, Lemao Li, Cuiping Chen, Hong Key Laboratory of Data Engineering and Knowledge Engineering Ministry of Education China School of Information Renmin University of China China Tencent AI Lab United States

Embedding-based methods are popular for knowledge Base Question Answering (KBQA), but few current models have numerical reasoning skills and thus struggle to answer ordinal constrained questions. This paper proposes a new embedding-based KBQA framework which particularly takes numerical reasoning into account. We present NumericalTransformer on top of NSM, a state-of-the-art embedding-based KBQA model, to create NT-NSM. To enable better training, we propose two pre-training tasks with explicit numerical-oriented loss functions on two generated training datasets and a template-based data augmentation method for enriching ordinal constrained QA dataset. Extensive experiments on KBQA benchmarks demonstrate that with the help of our training algorithm, NT-NSM is empowered with numerical reasoning skills and substantially outperforms the baselines in answering ordinal constrained questions. Copyright © 2021, The Authors. All rights reserved.

关键词： Embeddings