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

AirNN: A Featherweight Framework for Dynamic Input-Dependent approximation of CNNs

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2021年第10期40卷 2090-2103页

作者： Hemmat, Maedeh San Miguel, Joshua Davoodi, Azadeh Univ Wisconsin Dept Elect & Comp Engn 1415 Johnson Dr Madison WI 53706 USA

In this work, we propose AirNN, a novel framework which enables dynamic approximation of an already-trained convolutional neural network (CNN) in hardware during inference. AirNN enables input-dependent approximation of the CNN to achieve energy saving without much degradation in its classification accuracy at runtime. For each input, AirNN uses only a fraction of the CNN's weights based on that input (with the rest remaining 0) to conduct the inference. Consequently, energy saving is possible due to fewer number of fetches from off-chip memory as well as fewer multiplications for majority of the inputs. To achieve per-input approximation, we propose a clustering algorithm that groups similar weights in the CNN based on their importance, and design an iterative framework that decides dynamically how many clusters of weights should be fetched from off-chip memory for each individual input. We also propose new hardware structures to implement our framework on top of a recently proposed FPGA-based CNN accelerator. In our experiments with popular CNNs, we, on average, show 49% energy saving with less than 3% degradation in classification accuracy due to doing inference with only a fraction of the weights for the majority of the inputs. We also propose a greedy interleaving scheme, implemented in hardware, in order to improve the performance of the iterative procedure and compensate for its latency overhead.

关键词： Hardware Clustering algorithms approximation algorithms Neurons Degradation Neural networks Inference algorithms Approximate computation early termination input-dependent approximation low-energy design neural network accelerators

来源：评论

学校读者我要写书评

暂无评论

approximation of the Constrained Joint Spectral Radius via Algebraic Lifting

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2021年第7期66卷 3386-3392页

作者： Xu, Xiangru Ackmese, Behcet Univ Wisconsin Dept Mech Engn Madison WI 53706 USA Univ Washington Dept Aeronaut & Astronaut Seattle WA 98195 USA

This article studies the constrained switching (linear) system which is a discrete-time switched linear system whose switching sequences are constrained by a deterministic finite automaton. The stability of a constrained switching system is characterized by its constrained joint spectral radius that is known to be difficult to compute or approximate. Using the semitensor product of matrices, the matrix-form expression of a constrained switching system is shown to be equivalent to that of a lifted arbitrary switching system. Then, the constrained joint/generalized spectral radius of a constrained switching system is proven to be equal to the joint/generalized spectral radius of its lifted arbitrary switching system which can be approximated by off-the-shelf algorithms.

关键词： Switches Switching systems Linear systems Automata approximation algorithms Eigenvalues and eigenfunctions Electronic mail Constrained joint spectral radius constrained switching systems semitensor product switched systems

来源：评论

学校读者我要写书评

暂无评论

Network-Level Optimization for Unbalanced Power Distribution System: approximation and Relaxation

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2021年第5期36卷 4126-4139页

作者： Jha, Rahul Ranjan Dubey, Anamika Washington State Univ Sch Elect Engn & Comp Sci Pullman WA 99164 USA

The nonlinear programming (NLP) problem to solve distribution-level optimal power flow (D-OPF) poses convergence issues and does not scale well for unbalanced distribution systems. The existing scalable D-OPF algorithms either use approximations that are not valid for an unbalanced power distribution system, or apply relaxation techniques to the nonlinear power flow equations that do not guarantee a feasible power flow solution. In this paper, we propose scalable D-OPF algorithms that simultaneously achieve optimal and feasible solutions by solving multiple iterations of approximate, or relaxed, D-OPF subproblems of low complexity. The first algorithm is based on a successive linear approximation of the nonlinear power flow equations around the current operating point, where the D-OPF solution is obtained by solving multiple iterations of a linear programming (LP) problem. The second algorithm is based on the relaxation of the nonlinear power flow equations as conic constraints together with directional constraints, which achieves optimal and feasible solutions over multiple iterations of a second-order cone programming (SOCP) problem. It is demonstrated that the proposed algorithms are able to reach an optimal and feasible solution while significantly reducing the computation time as compared to an equivalent NLP D-OPF model for the same distribution system.

关键词： Mathematical model approximation algorithms Computational modeling Programming Power distribution Optimization Linear programming Iterative second order cone programming successive linear programming three-phase optimal power flow

来源：评论

学校读者我要写书评

暂无评论

Fast Greedy Subset Selection From Large Candidate Solution Sets in Evolutionary Multiobjective Optimization

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2022年第4期26卷 750-764页

作者： Chen, Weiyu Ishibuchi, Hisao Shang, Ke Southern Univ Sci & Technol Dept Comp Sci & Engn Guangdong Prov Key Lab Brain Inspired Intelligent Shenzhen 518055 Peoples R China

Subset selection plays an important role in the field of evolutionary multiobjective optimization (EMO). Especially, in an EMO algorithm with an unbounded external archive (UEA), subset selection is an essential post-processing procedure to select a prespecified number of solutions as the final result. In this article, we discuss the efficiency of greedy subset selection for the hypervolume, inverted generational distance (IGD), and IGD plus (IGD+) indicators. Greedy algorithms usually efficiently handle the subset selection. However, when a large number of solutions are given (e.g., subset selection from tens of thousands of solutions in a UEA), they often become time consuming. Our idea is to use the submodular property, which is known for the hypervolume indicator, to improve their efficiency. First, we prove that the IGD and IGD+ indicators are also submodular. Next, based on the submodular property, we propose an efficient greedy inclusion algorithm for each indicator. We demonstrate through computational experiments that the proposed algorithms are much faster than the standard greedy subset selection algorithms. The proposed algorithms also help the research on performance indicators.

关键词： Optimization Greedy algorithms Statistics Sociology approximation algorithms Evolutionary computation Clustering algorithms Evolutionary many-objective optimization evolutionary multiobjective optimization (EMO) performance indicators submodularity subset selection

来源：评论

学校读者我要写书评

暂无评论

Query-Efficient Black-Box Adversarial Attacks Guided by a Transfer-Based Prior

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2022年第12期44卷 9536-9548页

作者： Dong, Yinpeng Cheng, Shuyu Pang, Tianyu Su, Hang Zhu, Jun Tsinghua Univ Beijing Natl Res Ctr Informat Sci & Technol Tsinghua Bosch Joint Ctr Machine Learning Inst Artificial IntelligenceDept Comp Sci & Tech Beijing 100084 Peoples R China Pazhou Lab Guangzhou 510330 Peoples R China

Adversarial attacks have been extensively studied in recent years since they can identify the vulnerability of deep learning models before deployed. In this paper, we consider the black-box adversarial setting, where the adversary needs to craft adversarial examples without access to the gradients of a target model. Previous methods attempted to approximate the true gradient either by using the transfer gradient of a surrogate white-box model or based on the feedback of model queries. However, the existing methods inevitably suffer from low attack success rates or poor query efficiency since it is difficult to estimate the gradient in a high-dimensional input space with limited information. To address these problems and improve black-box attacks, we propose two prior-guided random gradient-free (PRGF) algorithms based on biased sampling and gradient averaging, respectively. Our methods can take the advantage of a transfer-based prior given by the gradient of a surrogate model and the query information simultaneously. Through theoretical analyses, the transfer-based prior is appropriately integrated with model queries by an optimal coefficient in each method. Extensive experiments demonstrate that, in comparison with the alternative state-of-the-arts, both of our methods require much fewer queries to attack black-box models with higher success rates.

关键词： Estimation Optimization Analytical models Numerical models Deep learning approximation algorithms Weight measurement Adversarial examples black-box attacks zeroth-order optimization query efficiency transferability

来源：评论

学校读者我要写书评

暂无评论

approximation Results for Makespan Minimization with Budgeted Uncertainty

引用

THEORY OF COMPUTING SYSTEMS 2021年第6期65卷 903-915页

作者： Bougeret, Marin Jansen, Klaus Poss, Michael Rohwedder, Lars Univ Montpellier CNRS LIRMM Montpellier France Univ Kiel Dept Comp Sci D-24098 Kiel Germany

We study approximation algorithms for the problem of minimizing the makespan on a set of machines with uncertainty on the processing times of jobs. In the model we consider, which goes back to Bertsimas et al. (Math. Program. 98(1-3), 49-71 2003), once the schedule is defined an adversary can pick a scenario where deviation is added to some of the jobs' processing times. Given only the maximal cardinality of these jobs, and the magnitude of potential deviation for each job, the goal is to optimize the worst-case scenario. We consider both the cases of identical and unrelated machines. Our main result is an EPTAS for the case of identical machines. We also provide a 3-approximation algorithm and an inapproximability ratio of 2 - epsilon for the case of unrelated machines.

关键词： Makespan minimization Robust optimization approximation algorithms EPTAS Parallel machines Unrelated machines

来源：评论

学校读者我要写书评

暂无评论

Charging Path Optimization in Mobile Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2022年第5期30卷 2262-2273页

作者： Chen, Lin Li, Shan Huang, Hua Yang, Weihua Sun Yat Sen Univ Sch Comp Sci & Engn Guangzhou 510275 Guangdong Peoples R China SUNY Stony Brook Dept Elect & Comp Engn Stony Brook NY 11794 USA Univ Calif Merced Dept Comp Sci & Engn Merced CA 95343 USA Taiyuan Univ Technol Coll Math Taiyuan 030024 Peoples R China

We study a class of generic charging path optimization problems arising from emerging networking applications, where mobile chargers are dispatched to deliver energy to mobile agents (e.g., robots, drones, vehicles), which have specified tasks and mobility patterns. We instantiate our work by focusing on finding the charging path maximizing the number of nodes charged within a fixed time horizon. We show that this problem is APX-hard. By recursively decomposing the problem into sub-problems of searching sub-paths, we design quasi-polynomial-time algorithms achieving logarithmic approximation to the optimum charging path. Our approximation algorithms can be further adapted and extended to solve a variety of charging path optimization and scheduling problems with realistic constraints, such as limited time and energy budget.

关键词： Optimization approximation algorithms Sensors Scheduling Heuristic algorithms Trajectory Task analysis Charging path optimization mobile charger scheduling mobile networks approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Electromagnetic Transient Analysis of Transmission Line Based on Rational Krylov approximation

引用

IEEE TRANSACTIONS ON POWER DELIVERY 2021年第5期36卷 2913-2920页

作者： Mouhaidali, Amjad Tromeur-Dervout, Damien Chadebec, Olivier Guichon, Jean-Michel Silvant, Sebastien SuperGrid Inst F-69628 Villeurbanne France Univ Claude Bernard Lyon 1 Univ Lyon Inst Camille Jordan CNRSUMR 5208 F-69622 Villeurbanne France Univ Grenoble Alpes G2Elab Grenoble INP CNRS F-38000 Grenoble France

This paper shows a comparison between Vector fitting and rational Krylov fitting techniques for the determination of rational models concerning the fitting accuracy, the computational performances and the model order. Primarily, the mathematics behind the second technique are presented. It should be noted that rational Krylov fitting have never been used in transmission line modeling. A new procedure is proposed to use rational Krylov fitting instead of vector fitting in the universal line model (ULM). Furthermore, it is demonstrated that this procedure has several advantages over the traditional one. Two illustrative examples involving a transmission system are presented for validation of the new procedure.

关键词： Computational modeling Transmission line matrix methods Admittance Power transmission lines Convergence Mathematical model approximation algorithms Electromagnetic transient frequency depend- ency rational krylov approximation vector fitting transmission line model passivity

来源：评论

学校读者我要写书评

暂无评论

Visual Complexity of Point Set Mappings 50th

Visual Complexity of Point Set Mappings

引用

50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025

作者： Meulemans, Wouter Simons, Arjen Verbeek, Kevin TU Eindhoven Eindhoven Netherlands

ISBN: (纸本)9783031826962

We study the visual complexity of animated transitions between point sets. Although there exist many metrics for point set similarity, these metrics are not adequate for this purpose, as they typically treat each point separately. Instead, we propose to look at translations of entire subsets/groups of points to measure the visual complexity of a transition between two point sets. Specifically, given two labeled point sets A and B in Rd, the goal is to compute the cheapest transformation that maps all points in A to their corresponding point in B, where the translation of a group of points counts as a single operation in terms of complexity. In this paper we identify several problem dimensions involving group translations that may be relevant to various applications, and study the algorithmic complexity of the resulting problems. Specifically, we consider different restrictions on the groups that can be translated, and different optimization functions. For most of the resulting problem variants we are able to provide polynomial time algorithms, or establish that they are NP-hard. For the remaining open problems we either provide an approximation algorithm or establish the NP-hardness of a restricted version of the problem. Furthermore, our problem classification can easily be extended with additional problem dimensions giving rise to new problem variants that can be studied in future work. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Massively Parallel Maximum Coverage Revisited 50th

Massively Parallel Maximum Coverage Revisited

引用

50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025

作者： Bui, Thai Vu, Hoa T. San Diego State University San DiegoCA92182 United States

ISBN: (纸本)9783031826696

We study the maximum set coverage problem in the massively parallel model. In this setting, m sets that are subsets of a universe of n elements are distributed among m machines. In each round, these machines can communicate with each other, subject to the memory constraint that no machine may use more than O~n memory. The objective is to find the k sets whose coverage is maximized. We consider the regime where k=Ω(m) (i.e., k=m/100), m=O(n), and each machine has O~n memory1. Maximum coverage is a special case of the submodular maximization problem subject to a cardinality constraint. This problem can be approximated to within a 1-1/e factor using the greedy algorithm, but this approach is not directly applicable to parallel and distributed models. When k=Ω(m), to obtain a 1-1/e-ϵ approximation, previous work either requires O~mn memory per machine which is not interesting compared to the trivial algorithm that sends the entire input to a single machine, or requires 2O(1/ϵ)n memory per machine which is prohibitively expensive even for a moderately small value ϵ. Our result is a randomized (1-1/e-ϵ)-approximation algorithm that uses O(1/ϵ3·logm·(log(1/ϵ)+logm))rounds. Our algorithm involves solving a slightly transformed linear program of the maximum coverage problem using the multiplicative weights update method, classic techniques in parallel computing such as parallel prefix, and various combinatorial arguments. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：