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

Maximizing Submodular or Monotone Approximately Submodular Functions by Multi-objective Evolutionary Algorithms

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Qian, Chao Yu, Yang Tang, Ke Yao, Xin Zhou, Zhi-Hua National Key Laboratory for Novel Software Technology Nanjing University Nanjing210023 China Shenzhen Key Laboratory of Computational Intelligence Department of Computer Science and Engineering Southern University of Science and Technology Shenzhen518055 China

Evolutionary algorithms (EAs) are a kind of nature-inspired general-purpose optimization algorithm, and have shown empirically good performance in solving various real-word optimization problems. During the past two decades, promising results on the running time analysis (one essential theoretical aspect) of EAs have been obtained, while most of them focused on isolated combinatorial optimization problems, which do not reflect the general-purpose nature of EAs. To provide a general theoretical explanation of the behavior of EAs, it is desirable to study their performance on general classes of combinatorial optimization problems. To the best of our knowledge, the only result towards this direction is the provably good approximation guarantees of EAs for the problem class of maximizing monotone submodular functions with matroid constraints. The aim of this work is to contribute to this line of research. Considering that many combinatorial optimization problems involve non-monotone or non-submodular objective functions, we study the general problem classes, maximizing submodular functions with/without a size constraint and maximizing monotone approximately submodular functions with a size constraint. We prove that a simple multi-objective EA called GSEMO-C can generally achieve good approximation guarantees in polynomial expected running time. Copyright © 2017, The Authors. All rights reserved.

关键词： Computational complexity

Parallelized Mobility-Aware Complex Event Processing

学校读者我要写书评

暂无评论

Parallelized Mobility-Aware Complex Event Processing

IEEE International Conference on Web Services (ICWS)

作者： Yuhao Gong Hongyu Kuang Xinchen Cai Hao Hu Wei Song Jian Lü State Key Lab for Novel Software Technology Nanjing University Nanjing Jiangsu China School of Computer Science and Engineering Nanjing University of Science and Technology Nanjing Jiangsu China

The concept of complex event processing (CEP) and complex-event-aware service have been extensively studied to retrieve relevant information from massive amount of realtime streaming events. In mobile environment, the Mobilityaware CEP (MCEP) system was proposed to address the issue of synchronization problem between different query ranges and MCEP operators. We noticed that MCEP systems lack the ability to process event in parallel and scale out when system load is high. In this paper, we proposed a parallel architecture for MCEP. The architecture can handle the synchronization problem and guarantee the correctness of event processing result. We also proposed a scaling strategy that can automatically scale out operators while ensures semantic transparency. An empirical evaluation based on up to 10 ViMs demonstrated that our approach is able to achieve higher throughput while keeping the MCEP synchronization mechanism valid.

关键词： Parallel architectures Throughput Synchronization Automobiles Accidents Parallel processing

VR-SGD: A simple stochastic variance reduction method for machine learning

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Shang, Fanhua Zhou, Kaiwen Liu, Hongying Cheng, James Tsang, Ivor W. Zhang, Lijun Tao, Dacheng Jiao, Licheng Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education School of Artificial Intelligence Xidian University China Department of Computer Science and Engineering Chinese University of Hong Kong Hong Kong Centre for Artificial Intelligence University of Technology Sydney UltimoNSW2007 Australia National Key Laboratory for Novel Software Technology Nanjing University Nanjing210023 China UBTECH Sydney Artificial Intelligence Centre School of Information Technologies Faculty of Engineering and Information Technologies University of Sydney 6 Cleveland St DarlingtonNSW2008 Australia

In this paper, we propose a simple variant of the original SVRG, called variance reduced stochastic gradient descent (VR-SGD). Unlike the choices of snapshot and starting points in SVRG and its proximal variant, Prox-SVRG, the two vectors of VR-SGD are set to the average and last iterate of the previous epoch, respectively. The settings allow us to use much larger learning rates, and also make our convergence analysis more challenging. We also design two different update rules for smooth and non-smooth objective functions, respectively, which means that VR-SGD can tackle non-smooth and/or non-strongly convex problems directly without any reduction techniques. Moreover, we analyze the convergence properties of VR-SGD for strongly convex problems, which show that VR-SGD attains linear convergence. Different from most algorithms that have no convergence guarantees for non-strongly convex problems, we also provide the convergence guarantees of VR-SGD for this case, and empirically verify that VR-SGD with varying learning rates achieves similar performance to its momentum accelerated variant that has the optimal convergence rate O(1/T2). Finally, we apply VR-SGD to solve various machine learning problems, such as convex and non-convex empirical risk minimization, and leading eigenvalue computation. Experimental results show that VR-SGD converges significantly faster than SVRG and Prox-SVRG, and usually outperforms state-of-the-art accelerated methods, e.g., Katyusha. Copyright © 2018, The Authors. All rights reserved.

关键词： Optimization

Cross-lingual Entity Alignment via Joint Attribute-Preserving Embedding

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Sun, Zequn Hu, Wei Li, Chengkai State Key Laboratory for Novel Software Technology Nanjing University China Department of Computer Science and Engineering University of Texas Arlington United States

Entity alignment is the task of finding entities in two knowledge bases (KBs) that represent the same real-world object. When facing KBs in different natural languages, conventional cross-lingual entity alignment methods rely on machine translation to eliminate the language barriers. These approaches often suffer from the uneven quality of translations between languages. While recent embedding-based techniques encode entities and relationships in KBs and do not need machine translation for cross-lingual entity alignment, a significant number of attributes remain largely unexplored. In this paper, we propose a joint attribute-preserving embedding model for cross-lingual entity alignment. It jointly embeds the structures of two KBs into a unified vector space and further refines it by leveraging attribute correlations in the KBs. Our experimental results on real-world datasets show that this approach significantly outperforms the state-of-the-art embedding approaches for cross-lingual entity alignment and could be complemented with methods based on machine translation. Copyright © 2017, The Authors. All rights reserved.

关键词： Knowledge based systems

Robust frequent directions with application in online learning

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Luo, Luo Chen, Cheng Zhang, Zhihua Li, Wu-Jun Zhang, Tong Department of Computer Science and Engineering Shanghai Jiao Tong University 800 Dongchuan Road Shanghai200240 China National Engineering Lab for Big Data Analysis and Applications School of Mathematical Sciences Peking University 5 Yiheyuan Road Beijing100871 China National Key Laboratory for Novel Software Technology Collaborative Innovation Center of Novel Software Technology and Industrialization Department of Computer Science and Technology Nanjing University 163 Xianlin Avenue Nanjing210023 China Computer Science & Mathematics Hong Kong University of Science and Technology Hong Kong

The frequent directions (FD) technique is a deterministic approach for online sketching that has many applications in machine learning. The conventional FD is a heuristic procedure that often outputs rank deficient matrices. To overcome the rank deficiency problem, we propose a new sketching strategy called robust frequent directions (RFD) by introducing a regularization term. RFD can be derived from an optimization problem. It updates the sketch matrix and the regularization term adaptively and jointly. RFD reduces the approximation error of FD without increasing the computational cost. We also apply RFD to online learning and propose an effective hyperparameter-free online Newton algorithm. We derive a regret bound for our online Newton algorithm based on RFD, which guarantees the robustness of the algorithm. The experimental studies demonstrate that the proposed method outperforms state-of-the-art second order online learning algorithms. Copyright © 2017, The Authors. All rights reserved.

关键词： Heuristic methods

Two-phase locality-sensitive hashing for privacy-preserving distributed service recommendation 1

学校读者我要写书评

暂无评论

9th International Symposium on Cyberspace Safety and Security, CSS 2017

作者： Qi, Lianyong Dou, Wanchun Zhang, Xuyun School of Information Science and Engineering Qufu Normal University Jining China Chinese Academy of Education Big Data Qufu Normal University Jining China State Key Laboratory for Novel Software Technology Nanjing University Nanjing China Department of Electrical and Computer Engineering University of Auckland Auckland New Zealand

ISBN: (数字)9783319694719

ISBN: (纸本)9783319694702

With the ever-increasing volume of services registered in various web communities, it becomes a challenging task to find the web services that a target user is really interested in from the massive candidates. In this situation, Collaborative Filtering (i.e., CF) technique is introduced to alleviate the heavy burden on the service selection decisions of target users. However, present CF-based recommendation approaches often assume that the recommendation bases, i.e., historical service quality data are centralized, without considering the distributed service recommendation scenarios where data are multi-sourced. Furthermore, distributed service recommendation calls for the collaborations among multiple involved parties, during which the private information of users may be exposed. In view of these challenges, we propose a novel privacy-preserving distributed service recommendation approach based on two-phase Locality-Sensitive Hashing (LSH), named SerRectwo-LSH, in this paper. Concretely, in SerRectwo-LSH, we first look for the "similar friends" of a target user through a privacy-preserving two-phase LSH process;afterwards, we determine the services preferred by the "similar friends" of the target user, and then recommend them to the target user. Finally, through a set of experiments conducted on a real distributed service quality dataset WS-DREAM, we validate the feasibility of our proposal in terms of recommendation accuracy and efficiency while guaranteeing privacy-preservation. © 2017, Springer International Publishing AG.

关键词： Efficiency

Bayesian multi-hypothesis Wyner-Ziv video coding

学校读者我要写书评

暂无评论

Journal of Information Hiding and Multimedia Signal Processing 2017年第2期8卷 478-485页

作者： Meng, Li Li Zong, Jing Xiu Sun, Gui Na Cheng, Jie Zhang, Jia Zhao, Meng Chen Department of Information Science and Engineering Shandong Provincial Key Laboratory for Novel Distributed Computer Software Technology Shandong Normal University No.88 Wenhua East Road Jinan250014 China

The performance of distributed video coding (DVC) relies heavily on the quality of the side information (SI), and better performance can be expected if multiple SIs are employed. In this paper, we consider the scenario with two SIs, which are obtained by forward and backward predictions respectively. In this case, a couple of ad hoc approaches have been proposed to approximate the conditional probability density function (pdf) of a Wyner-Ziv-coded frame given the two SIs. However, the optimal conditional pdf and the relative performances of these ad hoc approaches with respect to the optimal solution have not been studied. In this paper, using Bayes’ formula, we derive the closed-form expression of the conditional pdf. Experimental results show that the Bayesian solution has similar performance to previous methods. Moreover, simulation results reveal that when better SIs are available, the Bayesian solution could outperform other methods. This analysis sheds some lights on developing future DVC schemes. © 2017 ISSN.

关键词： Probability density function

Connecting software metrics across versions to predict defects

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Liu, Yibin Li, Yanhui Guo, Jianbo Zhou, Yuming Xu, Baowen State Key Laboratory for Novel Software Technology Nanjing University China Department of Computer Science and Technology Nanjing University China Institute for Interdisciplinary Information Sciences Tsinghua University Beijing China

Accurate software defect prediction could help software practitioners allocate test resources to defect-prone modules effectively and efficiently. In the last decades, much effort has been devoted to build accurate defect prediction models, including developing quality defect predictors and modeling techniques. However, current widely used defect predictors such as code metrics and process metrics could not well describe how software modules change over the project evolution, which we believe is important for defect prediction. In order to deal with this problem, in this paper, we propose to use the Historical Version Sequence of Metrics (HVSM) in continuous software versions as defect predictors. Furthermore, we leverage Recurrent Neural Network (RNN), a popular modeling technique, to take HVSM as the input to build software prediction models. The experimental results show that, in most cases, the proposed HVSM-based RNN model has a significantly better effort-aware ranking effectiveness than the commonly used baseline models. Copyright © 2017, The Authors. All rights reserved.

关键词： Defects

Using class imbalance learning for cross-company defect prediction 29

学校读者我要写书评

暂无评论

Using class imbalance learning for cross-company defect pred...

29th International Conference on software Engineering and Knowledge Engineering, SEKE 2017

作者： Yu, Xiao Zhou, Mingsong Chen, Xu Deng, Lijun Wang, Lu State Key Lab. of Software Engineering Computer School Wuhan University Wuhan China Department of Information Science and Technology Beijing Normal University Beijing China College of Business City University of Hong Kong Kowloon Tong Hong Kong School of Computer Science and Information Engineering HuBei University Wuhan China

ISBN: (纸本)1891706411

Cross-company defect prediction (CCDP) is a practical way that trains a prediction model by exploiting one or multiple projects of a source company and then applies the model to target company. Unfortunately, the performance of such CCDP models is susceptible to the high imbalanced nature between the defect-prone and non-defect classes of CC data. Class imbalance learning is applied to alleviate this issue. Because many class imbalance learning methods have been proposed, there is an imperative need to analyze and compare the performance of these methods for CCDP. Although prior empirical studies have proven *** algorithm achieves the best performance for defect prediction. This observation leads us to conduct a careful empirical study the issues of if and how class imbalance learning methods can benefit cross-company defect prediction. We investigate different types of class imbalance learning methods, including under-sampling technique, over-sampling technique and over sampling followed by under-sampling technique on the cross-company defect prediction performance over 15 publicly available datasets. Experimental results show that under-sampling technique achieves the best overall performance in terms of the gmeasure among those methods we studied.1.

关键词： Forecasting