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

String Transformation Based Morphology Learning

INFORMATICA-JOURNAL OF COMPUTING AND INFORMATICS 2019年第4期43卷 467-476页

作者： Kovacs, Laszlo Szabo, Gabor Univ Miskolc Inst Informat Technol H-3515 Miskolc Hungary

There are several morphological methods that can solve the morphological rule induction problem. For different languages this task represents different difficulty levels. In this paper we propose a novel method that can learn prefix, infix and suffix transformations as well. The test language is Hungarian (which is a morphologically complex Uralic language containing a high number of affix types and complex inflection rules), and we chose a previously generated word pair set of accusative case for evaluating the method, comparing its training time, memory requirements, average inflection time and correctness ratio with some of the most popular models like dictionaries, finite state transducers, the tree of aligned suffix rules and a lattice based method. We also provide multiple training and searching strategies, introducing parallelism and the concept of prefix trees to optimize the number of rules that need to be processed for each input word. This newly created novel method can be applied not only for morphology, but also for any problems in the field of bioinformatics and data mining that can benefit from string transformations learning.

关键词： machine learning natural language processing inflection rule induction agglutination dictionaries finite state transducers tree of aligned suffix rules lattice algorithms string transformations

来源：评论

学校读者我要写书评

暂无评论

lattice Sparsification and the Approximate Closest Vector Problem

引用

THEORY OF COMPUTING 2016年 12卷

作者： Dadush, Daniel Kun, Gabor CWI Amsterdam Netherlands Hungarian Acad Sci Alfred Renyi Inst Math 13-15 Realtanoda U H-1053 Budapest Hungary

We give a deterministic algorithm for solving the (1 + epsilon)-approximate Closest Vector Problem (CVP) on any n-dimensional lattice and in any near-symmetric norm in 2(O(n))(1 + 1/epsilon)(n) time and 2(n) poly(n) space. Our algorithm builds on the lattice point enumeration techniques of Micciancio and Voulgaris (STOC 2010, SICOMP 2013) and Dadush, Peikert and Vempala (FOCS 2011), and gives an elegant, deterministic alternative to the "AKS Sieve"-based algorithms for (1 + epsilon)-CVP (Ajtai, Kumar, and Sivakumar;STOC 2001 and CCC 2002). Furthermore, assuming the existence of a poly(n)-space and 2(O(n))-time algorithm for exact CVP in the l(2) norm, the space complexity of our algorithm can be reduced to polynomial. Our main technical contribution is a method for "sparsifying" any input lattice while approximately maintaining its metric structure. To this end, we employ the idea of random sublattice restrictions, which was first employed by Khot (FOCS 2003, J. Comp. Syst. Sci. 2006) for the purpose of proving hardness for the Shortest Vector Problem (SVP) under l(p) norms.

关键词： approximation algorithms high dimensional geometry lattice algorithms closest vector problem

来源：评论

学校读者我要写书评

暂无评论

Fast Fourier Orthogonalization 16

Fast Fourier Orthogonalization

引用

41st ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Ducas, Leo Prest, Thomas CWI Cryptol Grp Amsterdam Netherlands Thales Commun & Secur Gennevilliers France

ISBN: (纸本)9781450343800

The classical fast Fourier transform (FFT) allows to compute in quasi -linear time the product of two polynomials, in the circular convolution ring R[x]I(x(d) - 1) - a task that naively requires quadratic time. Equivalently, it allows to accelerate matrix -vector products when the matrix is circulant. In this work, we discover that the ideas of the FFT can be applied to speed up the orthogonalization process of matrices with circulant blocks of size d x d. We show that, when d is composite, it is possible to proceed to the orthogonalization in an inductive way up to an appropriate re-indexation of rows and columns. This leads to a structured Gram -Schmidt decomposition. In turn, this structured Gram-Schmidt decomposition accelerates a cornerstone lattice algorithm: the nearest plane algorithm. The complexity of both algorithms may be brought down to circle minus(d log d). Our results easily extend to cyclotomic rings, and can be adapted to Gaussian samplers. This finds applications in lattice-based cryptography, improving the performances of trapdoor functions.

关键词： Fast Fourier transform Gram-Schmidt orthogonalization nearest plane algorithm lattice algorithms lattice trapdoor functions

来源：评论

学校读者我要写书评

暂无评论

A DETERMINISTIC SINGLE EXPONENTIAL TIME ALGORITHM FOR MOST lattice PROBLEMS BASED ON VORONOI CELL COMPUTATIONS

引用

SIAM JOURNAL ON COMPUTING 2013年第3期42卷 1364-1391页

作者： Micciancio, Daniele Voulgaris, Panagiotis Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA Google Inc Mountain View CA 94043 USA

We give deterministic (O) over tilde (2(2n))-time (O) over tilde (2(n))-space algorithms to solve all the most important computational problems on point lattices in NP, including the shortest vector problem (SVP), closest vector problem (CVP), and shortest independent vectors problem (SIVP). This improves the n(O(n)) running time of the best previously known algorithms for CVP [R. Kannan, Math. Oper. Res., 12 (1987), pp. 415-440] and SIVP [D. Micciancio, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete algorithms, 2008, pp. 84-93] and gives a deterministic and asymptotically faster alternative to the 2(O(n))-time (and space) randomized algorithm for SVP of Ajtai, Kumar, and Sivakumar [Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 266-275]. The core of our algorithm is a new method to solve the closest vector problem with preprocessing (CVPP) that uses the Voronoi cell of the lattice (described as intersection of half-spaces) as the result of the preprocessing function. A direct consequence of our results is a derandomization of the best current polynomial time approximation algorithms for SVP and CVP, achieving a 2(O(n log log n/log n)) approximation factor.

关键词： lattice algorithms shortest vector problem closest vector problem Voronoi cell

来源：评论

学校读者我要写书评

暂无评论

Pricing Discrete Asian Barrier Options on lattices

Pricing Discrete Asian Barrier Options on Lattices

引用

IEEE Conference on Computational Intelligence for Financial Engineering and Economics (CIFEr)

作者： Hsu, William W. Y. Lu, Cheng-Yu Kao, Ming-Yang Lyuu, Yuh-Dauh Ho, Jan-Ming Acad Sinica Inst Informat Sci Taipei Taiwan Northwestern Univ Dept Elect Engn & Comp Sci Evanston IL USA Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei Taiwan

ISBN: (纸本)9781467318037

Asian barrier options are barrier options whose trigger is based on an average underlying price. They provide the advantages of both Asian options and barrier options. This paper introduces the first quadratic-time lattice algorithm to price European-style Asian barrier options. It is by far the most efficient lattice algorithm with convergence guarantees. The algorithm relies on the Lagrange multipliers to optimally distribute the number of states for each node of the multinomial lattice. We also show experiment results to demonstrate effectiveness and efficiency of our algorithm by comparing with Monte Carlo simulations.

关键词： Asian options barrier options multinomial model lattice algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for discrete lattice calculations

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2009年第13期228卷 4858-4880页

作者： Arndt, M. Sorkin, V. Tadmor, E. B. Univ Minnesota Dept Aerosp Engn & Mech Minneapolis MN 55455 USA Univ Minnesota Sch Math Minneapolis MN 55455 USA

We discuss algorithms for lattice-based computations, in particular lattice reduction, the detection of nearest neighbors, and the computation of clusters of nearest neighbors. We focus on algorithms that are most efficient for low spatial dimensions (typically d = 2, 3) and input data within a reasonably limited range. This makes them most useful for physically oriented numerical simulations, for example of crystalline solids. Different solution strategies are discussed, formulated as algorithms, and numerically evaluated. (c) 2009 Elsevier Inc. All rights reserved.

关键词： lattice algorithms lattice reduction Nearest neighbor Cluster computation Quasicontinuum

来源：评论

学校读者我要写书评

暂无评论

Array-based QR-RLS multichannel lattice filtering

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2008年第8期56卷 3510-3522页

作者： Gomes, Joao Barroso, Victor A. N. Univ Tecn Lisboa Inst Syst & Robot Inst Super Tecn Lisbon Portugal

An array-based algorithm for multichannel lattice filtering is proposed. The filter is formed by a set of units that are adapted locally and concurrently using recursions that closely match those for single-channel lattice filters. The design, based on a known modular decomposition approach, allows for unequal filter lengths to be specified for different input channels. Individual units are updated using a square-root recursive least-squares (RLS) algorithm in array form that relies mainly on Givens rotations and exhibits highly favorable numerical behavior and a regular structure that is appealing from a hardware implementation perspective. Iterative implementations of Givens rotations using the Newton method and CORDIC processors are examined in the context of fixed-point implementations. A procedure based on three CORDIC steps is proposed to handle complex data that arise in several applications of multichannel filtering. Algorithm initialization issues are also addressed. The array algorithm is compared in simulation with plain RLS, QR-RLS, and two related multichannel lattice algorithms. Its performance is shown to be comparable to that of other QR-decomposition-based algorithms under fixed-point arithmetic. In particular, it retains desirable graceful degradation properties as the numerical precision decreases.

关键词： adaptive filtering lattice algorithms multichannel filtering recursive least-squares (RLS) estimation

来源：评论

学校读者我要写书评

暂无评论

On polynomial-factor approximations to the shortest lattice vector length

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2003年第3期16卷 422-425页

作者： Kumar, R Sivakumar, D IBM Corp Almaden Res Ctr Dept K53 B1 San Jose CA 95120 USA

For every constant epsilon > 0, we obtain a 2(O(n(1/2+1/epsilon))) time randomized algorithm to approximate the length of the shortest vector in an n-dimensional lattice to within a factor of n(3+epsilon)..

关键词： lattice algorithms shortest lattice vector SVP

来源：评论

学校读者我要写书评

暂无评论

lattice algorithms for recursive instrumental variable methods

引用

INTERNATIONAL JOURNAL OF ADAPTIVE CONTROL AND SIGNAL PROCESSING 1996年第2-3期10卷 177-212页

作者： Swami, A Mendel, JM UNIV SO CALIF DEPT ELECT ENGN SYSTLOS ANGELESCA 90089

We develop recursive lattice algorithms for the estimation of the AR parameters of an ARMA process using an instrumental variable (TV) such as z(n) = y(2)(n), which leads to AR estimates based on the third-order cumulants, or z(n) = y(n - q), which leads to AR estimates based on the higher-order Yule-Walker equations. In the non-recursive mode the resulting set of linear equations involves the cross-correlation matrix of the observed process y(n), and the instrumental process z(n) and hence this matrix is generally not Hermitian. Our time- and order-recursive algorithm leads to a pair of lattices, one excited by y(n) and the other by z(n), the lattices being coupled through order and time update equations. We show that IV-based AR model fitting is equivalent to linear prediction with non-conventional orthogonality conditions. Extensions to ARMA processes are discussed. The joint-process estimation problem is also treated. Some statistical analysis is carried out and convergence results are given when y(n) and z(n) can be modelled as stationary processes. The only assumption that we make about z(n), the associated process, is that the cross-correlation of y(n) and z(n) suffices for the estimation of the AR parameters, i.e. we assume that z(n) is an instrumental process. Particular choices of z(n) lead to estimates based on the higher-order cumulants, which are useful when the non-Gaussian signal is corrupted by additive coloured Gaussian noise.

关键词： lattice algorithms recursive instrumental variable methods cumulants

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT COVARIANCE LADDER algorithms FOR FINITE ARITHMETIC APPLICATIONS

引用

SIGNAL PROCESSING 1987年第1期13卷 29-70页

作者： STROBACH, P SIEMENS AG Information Systems Laboratory ZT ZTI INF 121 D-8000 München 83 Fed. Rep. Germany

This paper is concerned with the problem of constructing numerically robust covariance ladder estimation algorithms for finite arithmetic applications. Conventional least-squares (LS) ladder algorithms suffer from mixed time and order recursive update equations resulting in a poor numerical accuracy when implemented with finite arithmetic. In this paper, a more ‘direct’ and numerically robust computation approach of the ladder update recursions using the most recently introduced algebraic method of generalized residual energies (GRE's) is presented. The new algorithms separate time and order recursions in two independent subalgorithms with a highly modular structure. Besides the general framework, five algorithms of this type are presented. Based on these algorithms, a VLSI ladder chip-set is proposed. Fixed-point simulations of the new VLSI structures are performed for several types of input data. The experimental analysis shows that the new algorithms are superior over conventional techniques and can operate at a multiplier wordlength as low as 8 bits. Dieser Aufsatz behandelt das Problem des Entwurfs numerisch robuster Kovarianz Ladder Algorithmen für die Anwendung in Echtzeitrechnern mit beschränkter numerischer Genauigkeit. Konventionelle Least-Squares (LS) Ladder Algorithmen basieren auf gemischt zeit- und ordnungsrekursiven Aktualisierungsgleichungen welche auf eine schlechte numerische Genauigkeit der Algorithmen führen. Eine erhebliche Verbesserung der numerischen Eigenschaften von Ladder Algorithmen läβt sich mit Hilfe der neuen algebraischen Methode der verallgemeinerten Residualenergien (GRE's) erreichen, welche in diesem Aufsatz vorgestellt wird. Die aus dem neuen Ansatz resultierenden Verfahren erlauben die Trennung von Zeit- und Ordnungsrekursionen in zwei unabhängige Teilalgorithmen mit höchst modularer Struktur. Neben der allgemeinen Herleitung werden insgesamt fünf numerisch robuste Ladder Algorithmen dieses Typs vorgestellt. Basierend auf diesen V

关键词： Autoregressive modeling ladder algorithms lattice algorithms VLSI realizations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：