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

31st Annual European Symposium on algorithms, ESA 2023

作者： Carlson, Charlie Jafarov, Jafar Makarychev, Konstantin Makarychev, Yury Shan, Liren University of Colorado BoulderCO United States Toyota Technological Institute ChicagoIL United States Northwestern University EvanstonIL United States

ISBN: (纸本)9783959772952

We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph G into k parts so as to separate k given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced p-norm Multiway Cut, a generalization of the problem, in which the goal is to minimize the p norm of the edge boundaries of k parts. We provide an O(log1/2 n log1/2+1/p k) approximation algorithm for this problem, improving upon the approximation guarantee of O(log3/2 n log1/2 k) due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an O(log1/2 nlog7/2 k) approximation algorithm with a weaker oracle and an O(log1/2 nlog5/2 k) approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no n1/4−Ε approximation algorithm for every Ε > 0 assuming the Hypergraph Dense-vs-Random Conjecture. © Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, and Liren Shan.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Policy-Iteration-Based Finite-Horizon Approximate Dynamic Programming for Continuous-Time Nonlinear Optimal Control

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2023年第9期34卷 5255-5267页

作者： Lin, Ziyu Duan, Jingliang Li, Shengbo Eben Ma, Haitong Li, Jie Chen, Jianyu Cheng, Bo Ma, Jun Tsinghua Univ Sch Vehicle & Mobil Beijing 100084 Peoples R China Univ Sci & Technol Beijing Sch Mech Engn Beijing 100083 Peoples R China Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China Hong Kong Univ Sci & Technol Guangzhou Robot & Autonomous Syst Thrust Guangzhou Peoples R China Hong Kong Univ Sci & Technol Dept Elect & Comp Engn Hong Kong Peoples R China

The Hamilton-Jacobi-Bellman (HJB) equation serves as the necessary and sufficient condition for the optimal solution to the continuous-time (CT) optimal control problem (OCP). Compared with the infinite-horizon HJB equation, the solving of the finite-horizon (FH) HJB equation has been a long-standing challenge, because the partial time derivative of the value function is involved as an additional unknown term. To address this problem, this study first-time bridges the link between the partial time derivative and the terminal-time utility function, and thus it facilitates the use of the policy iteration (PI) technique to solve the CT FH OCPs. Based on this key finding, the FH approximate dynamic programming (ADP) algorithm is proposed leveraging an actor-critic framework. It is shown that the algorithm exhibits important properties in terms of convergence and optimality. Rather importantly, with the use of multilayer neural networks (NNs) in the actor-critic architecture, the algorithm is suitable for CT FH OCPs toward more general nonlinear and complex systems. Finally, the effectiveness of the proposed algorithm is demonstrated by conducting a series of simulations on both a linear quadratic regulator (LQR) problem and a nonlinear vehicle tracking problem.

关键词： Mathematical models Heuristic algorithms Optimal control Artificial neural networks approximation algorithms Dynamic programming Nonlinear dynamical systems Actor critic approximate dynamic programming (ADP) finite-horizon (FH) Hamilton-Jacobi-Bellman (HJB) equation optimal control policy iteration (PI)

来源：评论

学校读者我要写书评

暂无评论

Understanding How Pretraining Regularizes Deep Learning algorithms

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2023年第9期34卷 5828-5840页

作者： Yao, Yu Yu, Baosheng Gong, Chen Liu, Tongliang Univ Sydney Sch Comp Sci Camperdown NSW 2006 Australia Nanjing Univ Sci & Technol Sch Comp Sci & Engn Minist Educ PCA Lab Nanjing 210094 Peoples R China Nanjing Univ Sci & Technol Sch Comp Sci & Engn Minist Educ Key Lab Intelligent Percept & Syst High Dimens In Nanjing 210094 Peoples R China

Deep learning algorithms have led to a series of breakthroughs in computer vision, acoustical signal processing, and others. However, they have only been popularized recently due to the groundbreaking techniques developed for training deep architectures. Understanding the training techniques is important if we want to further improve them. Through extensive experimentation, Erhan et al. (2010) empirically illustrated that unsupervised pretraining has an effect of regularization for deep learning algorithms. However, theoretical justifications for the observation remain elusive. In this article, we provide theoretical supports by analyzing how unsupervised pretraining regularizes deep learning algorithms. Specifically, we interpret deep learning algorithms as the traditional Tikhonov-regularized batch learning algorithms that simultaneously learn predictors in the input feature spaces and the parameters of the neural networks to produce the Tikhonov matrices. We prove that unsupervised pretraining helps in learning meaningful Tikhonov matrices, which will make the deep learning algorithms uniformly stable and the learned predictor will generalize fast w.r.t. the sample size. Unsupervised pretraining, therefore, can be interpreted as to have the function of regularization.

关键词： Deep learning Training Neural networks Prediction algorithms Signal processing algorithms Decoding approximation algorithms Classification deep learning regularization representation learning unsupervised pretrain

来源：评论

学校读者我要写书评

暂无评论

Curve Fitting Algorithm of Functional Radiation-Response Data Using Bayesian Hierarchical Gaussian Process Regression Model

引用

IEEE ACCESS 2023年 11卷 7109-7116页

作者： Jung, Kwang-Woo Kim, Jaeoh Jung, Ho-Jin Seo, Seung-Won Hong, Ji-Man Bai, Hyoung-Woo Jo, Seongil Korea Atom Energy Res Inst Adv Radiat Technol Inst Radiat Res Div Jeongeup 56212 South Korea Inha Univ Dept Data Sci Incheon 22212 South Korea Insilicogen Inc Yongin 16954 South Korea Inha Univ Dept Stat Incheon 22212 South Korea

We present a nonparametric Bayesian hierarchical (NBH) model and develop a variational approximation (VA) algorithm for the curve fitting of the functional radiation response data. The NBH model is based on a Bayesian hierarchical (BH) model with a Gaussian-Inverse Wishart process (G-IWP) prior, which simultaneously smooths multiple functional observations and estimates mean-covariance functions. We use the automatic differentiation variational inference (ADVI) algorithm with a Gaussian distribution as the variational distribution for approximating the posterior distribution of parameters of interest, which is applicable to a wide class of probabilistic models and can also be implemented in Stan (a probabilistic programming system). Using the NBH model and the Gaussian ADVI algorithm, we fit a dataset for the semiconductor obtained from the radiation response map (RRM) of South Korea.

关键词： Bayes methods Data models Computational modeling Semiconductor device modeling approximation algorithms Analytical models Inference algorithms Bayesian hierarchical model curve fitting functional radiation data Gaussian-inverse Wishart process Gaussian variational approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

SAFE: Service Availability via Failure Elimination Through VNF Scaling

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2023年第5期31卷 2042-2057页

作者： Xia, Rui Dai, Haipeng Zheng, Jiaqi Gu, Rong Wang, Xiaoyu Wang, Weijun Chen, Guihai Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China Soochow Univ Sch Comp Sci & Technol Suzhou 215006 Peoples R China

Virtualized network functions (VNFs) enable software applications to replace traditional middleboxes, which are more flexible and scalable in the network service provision. This paper focuses on ensuring Service Availability via Failure Elimination (SAFE) using VNF scaling, that is, given the resource requirements of VNF instances, finding an optimal and robust instance consolidation strategy, which can recover from one instance failure quickly. To address the above problem, we present a framework based on rounding and dynamic programming. First, we discretize the range of resource requirements into several sub-ranges, and thus the number of instance types becomes a constant. Second, we further reduce the number of instance types by gathering several small instances into a bigger one. Third, we propose an algorithm built on dynamic programming to solve the instance consolidation problem with a limited number of instance types. Finally, we set up a testbed to profile the functional relationship between the resource and the throughput for different types of VNFs, and conduct simulations to validate our theoretical results according to profiling results. The simulation results show that our algorithm outperforms the standby deployment model by 27.33% on average in terms of the number of servers required. Furthermore, SAFE has marginal overheads, around 7.22%, compared to the instance consolidation strategy without VNF backup consideration.

关键词： Network function virtualization (NFV) approximation algorithms dynamic programming

来源：评论

学校读者我要写书评

暂无评论

AoI-Aware Wireless Resource Allocation of Energy-Harvesting-Powered MEC Systems

引用

IEEE INTERNET OF THINGS JOURNAL 2023年第9期10卷 7835-7849页

作者： Zhao, Chengyu Xu, Shaoyi Ren, Jieying Beijing Jiaotong Univ Sch Elect & Informat Engn Beijing 100044 Peoples R China Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Peoples R China

Mobile-edge computing (MEC) has been deployed to enhance the data analysis performance of Internet of Things (IoT) and alleviate the shortage of computing resources for IoT devices. At the same time, energy harvesting (EH) is considered as a potential technology to prolong the network lifetime of the energy-limited IoT devices. In this article, we investigate the data analysis scenario in IoT architecture, where data are generated by wireless devices (WDs) and uploaded to the MEC server for centralized data processing. WDs, powered by the EH technology, upload the collected data in a frequency-division multiple access (FDMA) manner. Our goal is to maximize the long-term average system utility under the constraint of the Age of Information (AoI) and the limited system resources, by jointly optimizing the communication resource allocation, the data generating and discarding strategies, and the computing resource allocation. In order to solve the time-related AoI constraint, a series of virtual queues are applied to rewrite the optimization problem. To deal with the time-varying channel and the randomly data arrival, we propose a Lyapunov-based algorithm, decoupling the optimizing problem into several subproblems which can be fixed by traditional optimization algorithms and successive convex approximation (SCA) algorithm. With rigorous analysis, the proposed algorithm is proved to be an asymptotically optimal. Numerical results verify the theoretical analysis and reveal the effectiveness of the Lyapunov-based algorithm.

关键词： Internet of Things Wireless communication Resource management Throughput Optimization approximation algorithms Servers Age of Information (AoI) energy harvesting (EH) Lyapunov optimization mobile-edge computing (MEC)

来源：评论

学校读者我要写书评

暂无评论

Regularized impurity reduction: accurate decision trees with complexity guarantees

引用

DATA MINING AND KNOWLEDGE DISCOVERY 2023年第1期37卷 434-475页

作者： Zhang, Guangyi Gionis, Aristides KTH Royal Inst Technol Div Theoret Comp Sci Stockholm Sweden

Decision trees are popular classification models, providing high accuracy and intuitive explanations. However, as the tree size grows the model interpretability deteriorates. Traditional tree-induction algorithms, such as C4.5 and CART, rely on impurity-reduction functions that promote the discriminative power of each split. Thus, although these traditional methods are accurate in practice, there has been no theoretical guarantee that they will produce small trees. In this paper, we justify the use of a general family of impurity functions, including the popular functions of entropy and Gini-index, in scenarios where small trees are desirable, by showing that a simple enhancement can equip them with complexity guarantees. We consider a general setting, where objects to be classified are drawn from an arbitrary probability distribution, classification can be binary or multi-class, and splitting tests are associated with non-uniform costs. As a measure of tree complexity, we adopt the expected cost to classify an object drawn from the input distribution, which, in the uniform-cost case, is the expected number of tests. We propose a tree-induction algorithm that gives a logarithmic approximation guarantee on the tree complexity. This approximation factor is tight up to a constant factor under mild assumptions. The algorithm recursively selects a test that maximizes a greedy criterion defined as a weighted sum of three components. The first two components encourage the selection of tests that improve the balance and the cost-efficiency of the tree, respectively, while the third impurity-reduction component encourages the selection of more discriminative tests. As shown in our empirical evaluation, compared to the original heuristics, the enhanced algorithms strike an excellent balance between predictive accuracy and tree complexity.

关键词： Decision trees Impurity functions Submodularity Tree complexity approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximating the discrete time-cost tradeoff problem with bounded depth

引用

MATHEMATICAL PROGRAMMING 2023年第2期197卷 529-547页

作者： Daboul, Siad Held, Stephan Vygen, Jens Univ Bonn Res Inst Discrete Math Bonn Germany Univ Bonn Hausdorff Ctr Math Bonn Germany

We revisit the deadline version of the discrete time-cost tradeoff problem for the special case of bounded depth. Such instances occur for example in VLSI design. The depth of an instance is the number of jobs in a longest chain and is denoted by d. We prove new upper and lower bounds on the approximability. First we observe that the problem can be regarded as a special case of finding aminimum-weight vertex cover in a d-partite hypergraph. Next, we study the natural LP relaxation, which can be solved in polynomial time for fixed d and-for time-cost tradeoff instances-up to an arbitrarily small error in general. Improving on priorwork ofLovasz and of Aharoni, Holzman and Krivelevich, we describe a deterministic algorithm with approximation ratio slightly less than d/2 for minimum-weight vertex cover in d-partite hypergraphs for fixed d and given d-partition. This is tight and yields also a d 2 -approximation algorithm for general time-cost tradeoff instances, even if d is not fixed. We also study the inapproximability and show that no better approximation ratio than d+2/4 is possible, assuming the Unique Games Conjecture and P not equal NP. This strengthens a result of Svensson [21], who showed that under the same assumptions no constant-factor approximation algorithm exists for general time-cost tradeoff instances (of unbounded depth). Previously, only APX-hardness was known for bounded depth.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Truthful User Recruitment for Cooperative Crowdsensing Task: A Combinatorial Multi-Armed Bandit Approach

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2023年第7期22卷 4314-4331页

作者： Wang, Hengzhi Yang, Yongjian Wang, En Liu, Wenbin Xu, Yuanbo Wu, Jie Jilin Univ Dept Comp Sci & Technol Changchun 130012 Jilin Peoples R China Jilin Univ Key Lab Symbol Computat & Knowledge Engn Minist Educ Changchun 130012 Jilin Peoples R China Temple Univ Dept Comp & Informat Sci Philadelphia PA 19122 USA

Mobile Crowdsensing (MCS) is a promising paradigm that recruits users to cooperatively perform a sensing task. When recruiting users, existing works mainly focus on selecting a group of users with the best objective ability, e.g., the user's probability or frequency of covering the task locations. However, we argue that the task completion effect depends not only on the user's objective ability, but also on their subjective collaboration likelihood with each other. Furthermore, even though we can find a well-behaved group of users in the single-round scenario, while in the multi-round scenario without enough prior knowledge, we still face the problem of recruiting previously well-behaved user groups (exploitation) or recruiting uncertain user groups (exploration). Additionally, we consider that each user has a different cost, and the platform recruits users under a cost budget;thus, the problem becomes more challenging: users may report fake costs to gain more profits. To address these problems, assuming that the user's information is known, we first convert the single-round user recruitment problem into the min-cut problem and propose a graph theory based algorithm to find the approximate solution. Then, in the multi-round scenario where the user's information is estimated from the previous rounds, to balance the trade-off between exploration and exploitation, we propose the multi-round User Recruitment strategy under the budget constraint based on the combinatorial Multi-armed Bandit model (URMB), which is proven to achieve a tight regret bound. Next, we propose a graph-based payment strategy to achieve truthfulness and individual rationality of users. Finally, extensive experiments on three real-world datasets show that URMB always outperforms the state-of-th-art strategies.

关键词： Task analysis Recruitment Costs Collaboration Sensors approximation algorithms Target tracking Mobile crowdsensing collaboration likelihood combinatorial multi-armed bandit min-cut truthful

来源：评论

学校读者我要写书评

暂无评论

Learning Feature-Sparse Principal Subspace

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2023年第4期45卷 4858-4869页

作者： Nie, Feiping Tian, Lai Wang, Rong Li, Xuelong Northwestern Polytech Univ Sch Artificial Intelligence OPt & Elect iOPEN Xian 710072 Peoples R China

The principal subspace estimation is directly connected to dimension reduction and is important when there is more than one principal component of interest. In this article, we introduce two new algorithms to solve the feature-sparsity constrained PCA problem (FSPCA) for the principal subspace estimation task, which performs feature selection and PCA simultaneously. Existing optimization methods for FSPCA require data distribution assumptions and are lack of global convergence guarantee. Though the general FSPCA problem is NP-hard, we show that, for a low-rank covariance, FSPCA can be solved globally (Algorithm 1). Then, we propose another strategy (Algorithm 2) to solve FSPCA for the general covariance by iteratively building a carefully designed proxy. We prove (data-dependent) approximation bound and regular stationary convergence guarantees for the new algorithms. For the spectrum of covariance with exponential/Zipf's distribution, we provide exponential/posynomial approximation bounds. Constructive examples and numerical results are provided to demonstrate the tightness of our results. Experimental results show the promising performance and efficiency of the new algorithms compared with the state-of-the-arts on both synthetic and real-world datasets.

关键词： Principal component analysis approximation algorithms Optimization Sparse matrices Convergence Estimation Covariance matrices Feature selection sparse PCA nonconvex optimization nonsmooth optimization approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：