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

randomised block-coordinate Frank-Wolfe algorithm for distributed online learning over networks

COGNITIVE COMPUTATION AND SYSTEMS 2020年第2期2卷 72-79页

作者： Li, Jingchao Wu, Qingtao Zheng, Ruijuan Zhu, Junlong Ge, Quanbo Zhang, Mingchuan Henan Univ Sci & Technol Sch Informat Engn Luoyang 471023 Peoples R China Tongji Univ Sch Elect & Informat Engn Shanghai 200092 Peoples R China

The distributed online algorithms which are based on the Frank-Wolfe method can effectively deal with constrained optimisation problems. However, the calculation of the full (sub)gradient vector in those algorithms leads to a huge computational cost at each iteration. To reduce the computational cost of the algorithms mentioned above, the authors present a distributed online randomised block-coordinate Frank-Wolfe algorithm over networks. Each agent in the networks only needs to calculate a subset of the coordinates of its (sub)gradient vector in this algorithm. Furthermore, they make a detailed theoretical analysis of the regret bound of this algorithm. When all local objective functions satisfy the conditions of strongly convex functions, the authors' algorithm attains the regret bound of O(root T), where T is the total number of iterations. Furthermore, the theorem results are verified via simulation experiments, which show that the algorithm is effective and efficient.

关键词： convex programming learning (artificial intelligence) gradient methods randomised algorithms computational complexity distributed online algorithms Frank-Wolfe method constrained optimisation problems distributed online learning randomised block-coordinate Frank-Wolfe algorithm full gradient vector subgradient vector convex functions

来源：评论

学校读者我要写书评

暂无评论

randomised scheduling algorithm for virtual output queuing switch at the presence of non-uniform traffic

引用

IET NETWORKS 2019年第2期8卷 138-142页

作者： Jamali, Majid Ghiasian, Ali Aghigh Univ Esfahan Iran Shahrekord Univ Fac Engn Shahrekord Iran

Virtual Output Queuing (VOQ) is a well-known queuing discipline in data switch architecture that eliminates Head of Line (HOL) blocking issue. In VOQ scheme, for each output port, a separate FIFO is maintained by each input port. Consequently, a scheduling algorithm is required to determine the order of service to virtual queues at each time slot. Maximum Weight Matching (MWM) is a well-known scheduling algorithm that achieves the entire throughput region. Despite of outstanding attainable throughput, high complexity of MWM makes it an impractical algorithm for implementation in high-speed switches. To overcome this challenge, a number of randomised algorithms have been proposed in the literature. They commonly perform poorly when input traffic does not uniformly select output ports. Here, the authors propose two randomised algorithms that outperform the well-known formerly proposed solutions. They exploit a method to keep a parametric number of heavy edges from the last time matching and mix it by randomly generated matching to produce a new schedule. Simulation results confirm the superior performance of the proposed algorithms.

关键词： queueing theory packet switching telecommunication traffic scheduling telecommunication switching randomised algorithms nonuniform traffic virtual output queuing switch randomised scheduling algorithm input traffic randomised algorithms high-speed switches impractical algorithm outstanding attainable throughput MWM Maximum Weight Matching time slot virtual queues input port separate FIFO output port VOQ scheme Line blocking issue

来源：评论

学校读者我要写书评

暂无评论

A randomised Lattice Rule Algorithm with Pre-determined Generating Vector and Random Number of Points for Korobov Spaces with 0 < α ≤ 1/2 15th

A Randomised Lattice Rule Algorithm with Pre-determined Gene...

引用

15th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC)

作者： Nuyens, Dirk Wilkes, Laurence Katholieke Univ Leuven Dept Comp Sci Celestijnenlaan 200A B-3001 Leuven Belgium

ISBN: (纸本)9783031597640;9783031597626;9783031597619

In previous work [12], we showed that a lattice rule with a pre-determined generating vector but random number of points can achieve the near optimal convergence of O(n(-alpha-1/2+epsilon)), epsilon > 0, for the worst case expected error, commonly referred to as the randomised error, for numerical integration of high-dimensional functions in the Korobov space with smoothness alpha > 1/2. Compared to the optimal deterministic rate of O(n(-alpha+epsilon)), epsilon > 0, such a randomised algorithm is capable of an extra half in the rate of convergence. In this paper, we show that a pre-determined generating vector also exists in the case of 0 < alpha <= 1/2. Also here we obtain the near optimal convergence of O(n(-alpha-1/2+epsilon)), epsilon > 0;or in more detail, we obtain O(root r n(-alpha-1/2+1/(2r)+epsilon ')) which holds for any choices of epsilon ' > 0 and r is an element of N with r > 1/(2 alpha).

关键词： randomised algorithms Numerical integration Lattice rules Tractability Quasi-monte carlo Korobov space

来源：评论

学校读者我要写书评

暂无评论

Using Depth to Extend randomised Hough Forests for Object Detection and Localisation

Using Depth to Extend Randomised Hough Forests for Object De...

引用

International Conference on Digital Image Computing - Techniques and Applications (DICTA)

作者： Palmer, Richard West, Geoff Tan, Tele Curtin Univ Dept Spatial Sci Perth WA 6845 Australia Curtin Univ Dept Mech Eng Perth WA 6845 Australia

ISBN: (纸本)9781479921263

Implicit Shape Models (ISM) have been developed for object detection and localisation in 2-D (RGB) imagery and, to a lesser extent, full 3-D point clouds. Research is ongoing to extend the approach to 2-D imagery having co-registered depth (RGBD) e. g. from stereoscopy, laser scanning, time-of-flight cameras etc. A popular implementation of the ISM is as a randomised Forest of classifier trees representing codebooks for use in a Hough Transform voting framework. We present three extensions to the Class-Specific Hough Forest (CSHF) that utilises RGB and co-registered depth imagery acquired via stereoscopic mobile imaging. We demonstrate how depth and RGB information can be combined during training and at detection time. Rather than encoding depth as a new dimension of Hough space (which can increase vote sparsity), depth is used to modify the resulting placement and strength of votes in the original 2-D Hough space. We compare the effect of these depth-based extensions to the unmodified CSHF detection framework evaluated against a challenging new real-world dataset of urban street scenes.

关键词： Hough transforms image colour analysis object detection random processes randomised algorithms tree searching

来源：评论

学校读者我要写书评

暂无评论

On applications of the ray-shooting method for structured and structured-sparse static-output-feedbacks

引用

INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE 2017年第9期48卷 1902-1913页

作者： Peretz, Y. Jerusalem Coll Technol Comp Sci Dept Lev Acad Ctr Jerusalem Israel

A randomised optimisation method, called the ray-shooting method that efficiently solves the minimisation problem of continuous functions over compact non-convex unconnected regions, was introduced recently. Based on the ray-shooting method, an algorithm is suggested for solving the problems of structured and structured-sparse stabilising static-output-feedbacks. The algorithm presented here is a randomised algorithm, with a proof of convergence in probability. Its practical implementation has a good performance, in terms of quality of controllers, percent of success and run-time.

关键词： Continuous-time linear systems state-space representation static-output-feedbacks structured controllers sparse controllers randomised algorithms approximation algorithms convergence in probability

来源：评论

学校读者我要写书评

暂无评论

Balls into non-uniform bins

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2014年第2期74卷 2065-2076页

作者： Berenbrink, Petra Brinkmann, Andre Friedetzky, Tom Nagel, Lars Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Johannes Gutenberg Univ Mainz Zentrum Datenverarbeitung D-55099 Mainz Germany Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England

Balls-into-bins games for uniform bins are widely used to model randomised load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks. In this paper we consider scenarios in which non-uniform selection probabilities help to balance the load among the bins. While previous evaluations try to find strategies for identical bins, we investigate heterogeneous bins where the "capacities" of the bins might differ significantly. We look at the allocation of m balls into n bins of total capacity C where each ball has d random bin choices. For such heterogeneous environments we show that the maximum load remains bounded by In In(n)/In(d)+O(1) w.h.p. if the number of balls m equals the total capacity C. Further analytical and simulative results show better bounds and values for the maximum loads in special cases. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Load balancing randomised algorithms Balls-into-bins games

来源：评论

学校读者我要写书评

暂无评论

Automatic track filter tuning by randomized algorithms

引用

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS 2002年第4期38卷 1444-1449页

作者： Boers, Y Driessen, H Laclé, N Thales Nederland NL-7554 RR Hengelo Netherlands

Tuning or fine tuning of a tracker system turns out to be a hard job in practice. The main reason for this is that in a practical (surveillance) tracker system there are a lot of design parameters and a lot of competing requirements to be met. An algorithm to tune a tracker system automatically and at the same time obtain quantitative results in terms of the optimality of the solution is provided here. The theory of randomized algorithms is used to obtain probabilistic statements on the quality of the output of the tuning process. A simplified example illustrates how the developed theory is to be used.

关键词： tracking filters probability randomised algorithms tuning filtering theory automatic track filter tuning randomized algorithms fine tuning surveillance tracker system tuning Quantitative Result randomized algorithms filtering theory tracking filters fine tuning

来源：评论

学校读者我要写书评

暂无评论

Verified Analysis of Random Binary Tree Structures

引用

JOURNAL OF AUTOMATED REASONING 2020年第5期64卷 879-910页

作者： Eberl, Manuel Haslbeck, Max W. Nipkow, Tobias Tech Univ Monchen D-85748 Garching Germany Univ Innsbruck A-6020 Innsbruck Austria

This work is a case study of the formal verification and complexity analysis of some famous probabilistic algorithms and data structures in the proof assistant Isabelle/HOL. In particular, we consider the expected number of comparisons in randomised quicksort, the relationship between randomised quicksort and average-case deterministic quicksort, the expected shape of an unbalanced random Binary Search Tree, the randomised binary search trees described by Martinez and Roura, and the expected shape of a randomised treap. The last three have, to our knowledge, not been analysed using a theorem prover before and the last one is of particular interest because it involves continuous distributions.

关键词： Binary search trees randomised data structures randomised algorithms Quicksort Isabelle Interactive theorem proving

来源：评论

学校读者我要写书评

暂无评论

Longest Common Substring with Approximately k Mismatches (vol 81, pg 2633, 2019)

引用

ALGORITHMICA 2019年第7期81卷 3074-3074页

作者： Kociumaka, Tomasz Radoszewski, Jakub Starikovskaya, Tatiana Univ Warsaw Inst Informat Warsaw Poland PSL Univ Ecole Normale Super DIENS Paris France

In the longest common substring problem, we are given two strings of length n and must find a substring of maximal length that occurs in both strings. It is well known that the problem can be solved in linear time, but the solution is not robust and can vary greatly when the input strings are changed even by one character. To circumvent this, Leimeister and Morgenstern introduced the problem of the longest common substring with k mismatches. Lately, this problem has received a lot of attention in the literature. In this paper, we first show a conditional lower bound based on the SETH hypothesis implying that there is little hope to improve existing solutions. We then introduce a new but closely related problem of the longest common substring with approximately k mismatches and use locality-sensitive hashing to show that it admits a solution with strongly subquadratic running time. We also apply these results to obtain a strongly subquadratic-time 2-approximation algorithm for the longest common substring with k mismatches problem and show conditional hardness of improving its approximation ratio.

关键词： randomised algorithms String similarity measures Longest common substring Sketching Locality-sensitive hashing Binary jumbled indexing

来源：评论

学校读者我要写书评

暂无评论

Cooperative hybrid self-healing scheme for secure and data reliability in unattended wireless sensor networks

引用

IET INFORMATION SECURITY 2015年第4期9卷 223-233页

作者： Elsafrawey, Amir S. Hassan, Emad S. Dessouky, Moawad I. Menoufia Univ Dept Elect & Elect Commun Fac Elect Engn Menoufia 32952 Egypt

Unattended wireless sensor networks (UWSNs) are operated in hostile environments without constant supervision by a trusted sink;so it faces the risk of compromising by adversaries (ADVs). In this study, proposed is a cooperative hybrid self-healing randomised distributed (CHSHRD) scheme, a new mechanism to enhance the confidentiality of the data collected by UWSNs. The proposed scheme employs both proactive and reactive peers to ensure both backward secrecy and data reliability. It helps the unattended sensors to self-heal and restore their backward secrecy by asking for help from the best qualified neighbours to generate a new secret key to regain their secrecy. The sick sensors also use the best qualified neighbours to distribute the data parts among them to protect the data from eavesdropping and this will enhance the data reliability. In this study, they also present a powerful, realistic and agile ADV model and show how CHSHRD scheme can result in sensor regaining secrecy and achieving high data reliability, despite the adversary efforts to the contrary. The evaluation of the proposed scheme relies on both theoretical probabilistic results and simulation results that compare the proposed scheme to other protection schemes. The results show that this hybrid scheme provides better protection than other schemes that use either proactive or reactive peers.

关键词： data protection distributed algorithms private key cryptography probability randomised algorithms telecommunication network reliability telecommunication security wireless sensor networks ADV model CHSHRD scheme UWSN Yi Ren scheme adversaries backward secrecy compromised probability cooperative hybrid self-healing randomised distributed scheme data confidentiality enhancement data protection data reliability enhancement data security eavesdropping hostile environment naive scheme proactive scheme secret key generation standalone reactive scheme unattended wireless sensor network

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：