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

Proving divide and conquer Complexities in Isabelle/HOL

JOURNAL OF AUTOMATED REASONING 2017年第4期58卷 483-508页

作者： Eberl, Manuel Tech Univ Munich Fak Informat Garching Germany

The Akra-Bazzi method (Akra and Bazzi in Comput Optim Appl 10(2): 195210, 1998. doi: 10.1023A: 1018373005182), a generalisation of the well-known Master Theorem, is a useful tool for analysing the complexity of divide and conquer algorithms. This work describes a formalisation of the Akra-Bazzi method (as generalised by Leighton in Notes on better Master theorems for divide-and-conquer recurrences, 1996. http: courses. csail. mit. edu 6.046 spring04 handouts akrabazzi. pdf) in the interactive theorem prover Isabelle HOL and the derivation of a generalised version of the Master Theorem from it. We also provide some automated proof methods that facilitate the application of this Master Theorem and allow mostly automatic verification of T-bounds for these divide and conquer recurrences. To our knowledge, this is the first formalisation of theorems for the analysis of such recurrences.

关键词： Isabelle/HOL Master Theorem Akra-Bazzi divide and conquer algorithms Recurrences Complexity Landau symbols

来源：评论

学校读者我要写书评

暂无评论

The supervised network self-organizing map for classification of large data sets

引用

APPLIED INTELLIGENCE 2002年第3期16卷 185-203页

作者： Papadimitriou, S Mavroudi, S Vladutu, L Pavlides, G Bezerianos, A Univ Patras Sch Med Dept Phys Med Patras 26500 Greece Univ Patras Dept Comp Engn & Informat Patras 26500 Greece

Complex application domains involve difficult pattern classification problems. The state space of these problems consists of regions that lie near class separation boundaries and require the construction of complex discriminants while for the rest regions the classification task is significantly simpler. The motivation for developing the Supervised Network Self-Organizing Map (SNet-SOM) model is to exploit this fact for designing computationally effective solutions. Specifically, the SNet-SOM utilizes unsupervised learning for classifying, at the simple regions and supervised learning for the difficult ones in a two stage learning process. The unsupervised learning approach is based on the Self-Organizing Map (SOM) of Kohonen. The basic SOM is modified with a dynamic node insertion/deletion process controlled with an entropy based criterion that allows an adaptive extension of the SOM. This extension proceeds until the total number of training patterns that are mapped to neurons with high entropy (and therefore with ambiguous classification) reduces to a size manageable numerically with a capable supervised model. The second learning phase (the supervised training) has the objective of constructing better decision boundaries at the ambiguous regions. At this phase, a special supervised network is trained for the computationally reduced task of performing the classification at the ambiguous regions only. The performance of the SNet-SOM has been evaluated on both synthetic data and on an ischemia detection application with data extracted from the European ST-T database, In all cases, the utilization of SNet-SOM with supervised learning based on both Radial Basis Functions and Support Vector Machines has improved the results significantly related to those obtained with the unsupervised SOM and has enhanced the scalability of the supervised learning schemes. The highly disciplined design of the generalization performance of the Support Vector Machine allows to design th

关键词： neural networks data mining self-organizing maps learning vector quantization divide and conquer algorithms radial basis functions support vector machines computational complexity ischemia detection

来源：评论

学校读者我要写书评

暂无评论

A probabilistic analysis of some tree algorithms

引用

ANNALS OF APPLIED PROBABILITY 2005年第4期15卷 2445-2471页

作者： Mohamed, H Robert, P INRIA F-78153 Le Chesnay France

In this paper a general class of tree algorithms is analyzed. It is shown that, by using an appropriate probabilistic representation of the quantities of interest, the asymptotic behavior of these algorithms can be obtained quite easily without resorting to the usual complex analysis techniques. This approach gives a unified probabilistic treatment of these questions. It simplifies and extends some of the results known in this domain.

关键词： splitting algorithms divide and conquer algorithms unusual laws of large numbers asymptotic oscillating behavior data structures tries renewal theorem

来源：评论

学校读者我要写书评

暂无评论

Regularity of the Euclid Algorithm;application to the analysis of fast GCD algorithms

引用

JOURNAL OF SYMBOLIC COMPUTATION 2009年第7期44卷 726-767页

作者： Cesaratto, Eda Clement, Julien Daireaux, Benoit Lhote, Loick Maume-Deschamps, Veronique Vallee, Brigitte Univ Caen CNRS GREYC UMR 6072 F-14032 Caen France ENSICAEN Caen France Consejo Nacl Invest Cient & Tecn RA-1033 Buenos Aires DF Argentina Univ Nacl Gral Sarmiento Inst Desarrollo Humano Buenos Aires DF Argentina IrisRes Ctr Stavanger Norway Univ Lyon 1 ISFA F-69365 Lyon France

There exist fast variants of the gcd algorithm which are all based on principles due to Knuth and Schonhage. On inputs of size n, these algorithms use a divide and conquer approach, perform FFT multiplications with complexity mu(n) and stop the recursion at a depth slightly smaller than lg n. A rough estimate of the worst-case complexity of these fast versions provides the bound O(mu(n) log n). Even the worst-case estimate is partly based on heuristics and is not actually proven. Here, we provide a precise probabilistic analysis of some of these fast variants, and we prove that their average bit-complexity on random inputs of size n is (sic) (mu(n) log n), with a precise remainder term, and estimates of the constant in the (sic)-term. Our analysis applies to any cases when the cost mu(n) is of order Omega(n log n), and is valid both for the FFT multiplication algorithm of Schonhage-Strassen, but also for the new algorithm introduced quite recently by Furer [Furer, M., 2007. Faster integer Multiplication. In: Proceedings of STOC'07, pp. 57-66]. We view such a fast algorithm as a sequence of what we call interrupted algorithms, and we obtain two main results about the (plain) Euclid Algorithm, which are of independent interest. We precisely describe the evolution of the distribution of numbers during the execution of the (plain) Euclid Algorithm, and we exhibit an (unexpected) density psi which plays a central role since it always appears at the beginning of each recursive call. This strong regularity phenomenon proves that the interrupted algorithms are locally "similar" to the total algorithm. This ultimately leads to the precise evaluation of the average bit-complexity of these fast algorithms. This work uses various tools, and is based on a precise study of generalised transfer operators related to the dynamical system underlying the Euclid Algorithm. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： Euclid algorithm divide and conquer algorithms Fast multiplication Analysis of algorithms Transfer operators Perron formula

来源：评论

学校读者我要写书评

暂无评论

Ischemia detection using supervised learning for hierarchical neural networks based on Kohonen-maps

Ischemia detection using supervised learning for hierarchica...

引用

23rd Annual International Conference of the IEEE-Engineering-in-Medicine-and-Biology-Society

作者： Vladutu, L Papadimitriou, S Mavroudi, S Bezerianos, A Univ Patras Sch Med Dept Phys Med GR-26110 Patras Greece

ISBN: (纸本)0780372115

The detection of ischemic episodes is a difficult pattern classification problem. The motivation for developing the Supervising Network - Self Organizing Map (sNet-SOM) model is to design computationally effective solutions for the particular problem of ischemia detection and other similar applications. The sNet-SOM uses unsupervised learning for the regions where the classification is not ambiguous and supervised for the "difficult" ones in a two-stage learning process. The unsupervised learning approach extends and adapts the Self-Organizing Map (SOM) algorithm of Kohonen. The basic SOM is modified with a dynamic expansion process controlled with an entropy based criterion that allows the adaptive formation of the proper SOM structure. This extension proceeds until the total number of training patterns that are mapped to neurons with high entropy (therefore with ambiguous classification) reduces to a size manageable numerically with a proper supervised model. The second learning phase (supervised training) has the objective of constructing better decision boundaries of the ambiguous regions. In this phase, a special supervised network is trained for the task of reduced computationally complexity- to perform the classification only of the ambiguous regions. After we tried with different classes of supervised networks, we obtained the best results with the Support Vector Machines (SVM) as local experts.

关键词： self-organizing maps ischemia entropy principal component analysis divide and conquer algorithms radial basis functions Vapnik-Chervonenkis dimension support vector machines computational complexity

来源：评论

学校读者我要写书评

暂无评论

Ischemia detection with a self-organizing map supplemented by supervised learning

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS 2001年第3期12卷 503-515页

作者： Papadimitriou, S Mavroudi, S Vladutu, L Bezerianos, A Univ Patras Sch Med Dept Med Phys GR-26110 Patras Greece

The problem of maximizing the performance of the detection of ischemia episodes is a difficult pattern classification problem. The state space for this problem consists of regions that lie near class separation boundaries and require the construction of complex discriminants while for the rest regions the classification task is significantly simpler. The motivation for developing the supervising network self-organizing map (sNet-SOM) model is to exploit this fact for designing computationally effective solutions both for the particular ischemic detection problem and for other applications that share similar characteristics. Specifically( the sNet-SOM utilizes unsupervised learning for the "simple" regions and supervised for the "difficult" ones in a two stage learning process. The unsupervised learning approach extends and adapts the self-organizing map (SOM) algorithm of Kohonen, The basic SOM is modified with a dynamic expansion process controlled with an entropy based criterion that allows the adaptive formation of the proper SOM structure. This extension proceeds until the total number of training patterns that are mapped to neurons with high entropy land therefore with ambiguous classification) reduces to a size manageable numerically with a capable supervised model, The second learning phase (the supervised training) has the objective of constructing better decision boundaries at the ambiguous regions. At this phase, a special supervised network is trained for the computationally reduced task of performing the classification at the ambiguous regions only. The utilization of sNet-SOM with supervised learning based on the radial basis functions and support vector machines has resulted in an improved accuracy of ischemia detection especially in the last case. The highly disciplined design of the generalization performance of the support vector mai chine allows designing the proper model for the number of patterns transferred to the supervised expert.

关键词： computational complexity divide and conquer algorithms entropy ischemia principal component analysis radial basis functions self-organizing maps support vector machines Vapnik-Chervonenkis dimension

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：