检索结果-南通市图书馆

Learning to sample initial solution for solving 0-1 discrete optimization problem by local search

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China Mathematics 2024年第6期67卷 1317-1340页

作者： Xin Liu Jianyong Sun Zongben Xu School of Mathematics and Statistics Xi’an Jiaotong UniversityXi’an710049China

Local search methods are convenient alternatives for solving discrete optimization problems(DOPs).These easy-to-implement methods are able to find approximate optimal solutions within a tolerable time limit.It is known that the quality of the initial solution greatly affects the quality of the approximated solution found by a local search method.In this paper,we propose to take the initial solution as a random variable and learn its preferable probability distribution.The aim is to sample a good initial solution from the learned distribution so that the local search can find a high-quality solution.We develop two different deep network models to deal with DOPs established on set(the knapsack problem)and graph(the maximum clique problem),respectively.The deep neural network learns the representation of an optimization problem instance and transforms the representation to its probability vector.Experimental results show that given the initial solution sampled from the learned probability distribution,a local search method can acquire much better approximate solutions than the randomly-sampled initial solution on the synthesized knapsack instances and the Erd?s-Rényi random graph instances.Furthermore,with sampled initial solutions,a classical genetic algorithm can achieve better solutions than a random initialized population in solving the maximum clique problems on DIMACS instances.Particularly,we emphasize that the developed models can generalize in dimensions and across graphs with various densities,which is an important advantage on generalizing deep-learning-based optimization algorithms.

关键词： discrete optimization deep learning graph convolutional network local search

维普期刊数据库

Learning to select the recombination operator for derivative-free optimization

在线全文

学校读者我要写书评

暂无评论

Science China Mathematics 2024年第6期67卷 1457-1480页

作者： Haotian Zhang Jianyong Sun Thomas Back Zongben Xu School of Mathematics and Statistics Xi’an Jiaotong UniversityXi’an710049China Leiden Institute of Advanced Computer Science Leiden UniversityLeiden2333 CANetherlands

Extensive studies on selecting recombination operators adaptively,namely,adaptive operator selection(AOS),during the search process of an evolutionary algorithm(EA),have shown that AOS is promising for improving EA's performance.A variety of heuristic mechanisms for AOS have been proposed in recent decades,which usually contain two main components:the feature extraction and the policy setting.The feature extraction refers to as extracting relevant features from the information collected during the search process.The policy setting means to set a strategy(or policy)on how to select an operator from a pool of operators based on the extracted feature.Both components are designed by hand in existing studies,which may not be efficient for adapting optimization problems.In this paper,a generalized framework is proposed for learning the components of AOS for one of the main streams of EAs,namely,differential evolution(DE).In the framework,the feature extraction is parameterized as a deep neural network(DNN),while a Dirichlet distribution is considered to be the policy.A reinforcement learning method,named policy gradient,is used to train the DNN.As case studies,the proposed framework is applied to two DEs including the classic DE and a recently-proposed DE,which result in two new algorithms named PG-DE and PG-MPEDE,respectively.Experiments on the Congress of Evolutionary Computation(CEC)2018 test suite show that the proposed new algorithms perform significantly better than their counterparts.Finally,we prove theoretically that the considered classic methods are the special cases of the proposed framework.

关键词： evolutionary algorithm differential evolution adaptive operator selection reinforcement learning deep learning

维普期刊数据库

Unlabeled data driven cost-sensitive inverse projection sparse representation-based classification with 1/2 regularization

在线全文

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2022年第8期65卷 39-56页

作者： Xiaohui YANG Zheng WANG Jian SUN Zongben Xu Henan Engineering Research Center for Artificial Intelligence Theory and Algorithms School of Mathematics and StatisticsHenan University National Engineering Laboratory for Big Data Analytics School of Mathematics and StatisticsXi'an Jiaotong University

Sparse representation-based classification(SRC) has been widely used because it just relies on simple linear regression ideas to do classification, and it does not need learning. However, the performance of SRC is limited by needing sufficient labeled samples per class and the sensitivity to class imbalance. For tackling these problems, an improved SRC model is constructed in this paper. For alleviating the problem of insufficient labeled samples, an unlabeled data-driven inverse projection sparse representation-based classification model is constructed to achieve effective and stable representation and recognition results. The L1/2 and S1/2 regularizations are introduced to capture the sparsity of 1-D and 2-D, and to make the model have good statistical properties. Moreover, the cost-sensitive strategy is integrated into the model’s classification criteria to improve the imbalance of class distribution adaptively, especially for multiclass imbalanced data.A solver utilizing the mixed Gauss-Seidel and Jacobian ADMM algorithm is developed to obtain the approximate solution. Experiments on common public test databases show that the proposed model achieves competitive results compared with the latest published results and some deep-learning algorithms.

关键词： unlabeled-data driven 1/2 regularization cost-sensitive inverse projection sparse representation-based classification

Learning capability of the truncated greedy algorithm

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2016年第5期59卷 49-63页

作者： Lin xu Shaobo LIN Zongben Xu Institute for Information and System Sciences Xi'an Jiaotong University College of Mathematics and Information Science Wenzhou University

Pure greedy algorithm(PGA), orthogonal greedy algorithm(OGA) and relaxed greedy algorithm(RGA) are three widely used greedy type algorithms in both nonlinear approximation and supervised learning.In this paper, we apply another variant of greedy-type algorithm, called the truncated greedy algorithm(TGA)in the realm of supervised learning and study its learning performance. We rigorously prove that TGA is better than PGA in the sense that TGA possesses the faster learning rate than PGA. Furthermore, in some special cases, we also prove that TGA outperforms OGA and RGA. All these theoretical assertions are verified by both toy simulations and real data experiments.

关键词： supervised learning learning theory generalization capability greedy algorithm truncated greedy algorithm

Color and direction-invariant nonlocal self-similarity prior and its application to color image denoising

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2020年第12期63卷 87-103页

作者： Qi XIE Qian ZHAO Zongben Xu Deyu MENG School of Mathematics and Statistics Xi'an Jiaotong University Macau Institute of Systems Engineering Macau University of Science and Technology

Nonlocal self-similarity(NSS) is one of the most commonly used priors in computer vision and image processing. It aims to make use of the fact that a natural image often possesses many repetitive local patterns, and thus a local image patch always has many similar patches across the image. Through compensatively integrating these similar image patches, their insightful patterns hiding under corrupted noises can be intrinsically extracted. However, for using this prior knowledge, current methods search the similar patches by using simple block matching strategy with Euclidean distance, which largely ignores those patches containing similar local patterns but with different texture-directions and colors. To more sufficiently explore similar patches over an image, in this paper, we propose two new representations for image patches, which facilitate an easy NSS prior for measuring direction-invariant and color-invariant nonlocal selfsimilarity possessed by image patches. Specifically, based on this prior term, we formulate the color image denoising problem as a concise Bayesian posterior estimation framework, and design an efficient expectationmaximization(EM) algorithm to solve it. A series of experiments implemented on simulated and real noisy color images demonstrate the superiority of the proposed method as compared with the state-of-the-arts both visually and quantitatively, verifying the potential usefulness of this new NSS prior.

关键词： color image denoising nonlocal self-similarity Gaussian mixture model maximum a posterior (MAP) model EM algorithm

Adversarial data splitting for domain generalization

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2023年

作者： Xiang GU Jian SUN Zongben Xu School of Mathematics and Statistics Xi’an Jiaotong University

Domain generalization aims to learn a model that is generalizable to an unseen target domain,which is a fundamental and challenging task in machine learning for out-of-distribution generalization. This paper proposes a novel domain generalization approach that enforces the learned model to be able to generalize well over the train/val subset splitting of the training dataset. This idea is modeled herein as an adversarial data splitting framework, formulated as a min-max optimization problem inspired by the metalearning approach. The min-max optimization problem is solved by iteratively splitting the training dataset into the training and val subsets to maximize the domain shift measured by the objective function and updating the model parameters to enable the model to generalize well from the training subset to the val subset by minimizing the objective function. This adversarial training approach does not assume the known domain labels of the training data; instead, it automatically investigates the “hard” splitting of the train/val subsets to learn the generalizable model. Extensive experimental results using three benchmark datasets demonstrate the superiority of this approach. In addition, we derive a generalization error bound for the theoretical understanding of our proposed approach.

关键词：

On the uniqueness of virtual substrate for metasurface in a dielectric half-space

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2022年第1期65卷 207-217页

作者： Xiaobo LIU Wei xuE Xiaoming CHEN Anxue ZHANG Qiang CHENG Zongben Xu School of Information and Communications Engineering Xi'an Jiaotong University School of Mathematics and Statistics Xi'an Jiaotong University State Key Laboratory of Millimeter Waves and School of Electrical Engineering Southeast University

In this paper, we study the uniqueness of a virtual substrate for periodic metallic elements in a dielectric half-space. When the periodic metallic elements are placed at the interface of different substrates,they can be regarded to be embedded into a virtual substrate whose thickness approaches zero. However,the process of the mathematical limit of the thickness seems to be independent of the choice of the virtual substrate. Thereby, it is necessary to verify whether the arbitrary virtual substrate holds for the case. It is theoretically verified that the permittivity of the virtual substrate should be unique in order to satisfy the physical boundary condition of the periodic metallic elements. The root of the phenomenon is that the mathematical limit gives the alternative means to approach the actual physical situation, but the actual physical situation determines the way how the mathematical limit approaches zero. Finally, for comparison,two different virtual substrates are designed to validate the theory, for alternative substrate, incidence angle,and metallic elements. Besides, the finding can also be used to simplify the analysis and design of the metasurface by converting the periodic metallic elements in a dielectric half-space to the same periodic metallic elements in a uniform substrate.

关键词： virtual substrate periodic metallic elements mathematical limit relative permittivity boundary condition

Convergence of multi-block Bregman ADMM for nonconvex composite problems

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2018年第12期61卷 53-64页

作者： Fenghui WANG Wenfei CAO Zongben Xu School of Mathematics and Statistics Xi'an Jiaotong University Department of Mathematics Luoyang Normal University School of Mathematics and Information Science Shaanxi Normal University

The alternating direction method with multipliers(ADMM) is one of the most powerful and successful methods for solving various composite problems. The convergence of the conventional ADMM(i.e.,2-block) for convex objective functions has been stated for a long time, and its convergence for nonconvex objective functions has, however, been established very recently. The multi-block ADMM, a natural extension of ADMM, is a widely used scheme and has also been found very useful in solving various nonconvex optimization problems. It is thus expected to establish the convergence of the multi-block ADMM under nonconvex frameworks. In this paper, we first justify the convergence of 3-block Bregman ADMM. We next extend these results to the N-block case(N≥3), which underlines the feasibility of multi-block ADMM applications in nonconvex settings. Finally, we present a simulation study and a real-world application to support the correctness of the obtained theoretical assertions.

关键词： nonconvex regularization alternating direction method subanalytic function K-L inequality Bregman distance

Robust channel estimation based on the maximum entropy principle

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2023年第12期66卷 209-221页

作者： Zhengyang HU Jiang xuE Feng LI Qian ZHAO Deyu MENG Zongben Xu School of Mathematics and Statistics Xi’an Jiaotong University

Channel estimation(CE) is one of the crucial and fundamental elements of signal processing,especially considering the requirement of high accuracy in future wireless communication systems. Most traditional CE algorithms are explored under the assumption of Gaussian white noise, which limits the algorithms performance in real wireless communication situations. In this work, a novel self-adaptive CE algorithm based on the maximum entropy principle(MEP) was studied, which analyzes the statistical components of an arbitrary noise environment. In addition, an MEP channel-based signal estimation algorithm was studied. Furthermore, the statistical characteristics of channels were considered the regularization terms in the objective function for providing prior information and further increasing the accuracy. It was found that the proposed algorithm not only provides accurate CE but also reduces pilot consumption by using estimated signal data as pseudo pilots. The superior features of the proposed method concerning CE accuracy,pilot consumption, and robustness were confirmed through Monte Carlo simulations.

关键词： channel estimation maximum entropy principle pseudo pilot channel statistic characteristic colorful noise