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

universal algorithms for learning theory part I : piecewise constant functions

JOURNAL OF MACHINE LEARNING RESEARCH 2005年第9期6卷 1297-1321页

作者： Binev, P Cohen, A Dahmen, W DeVore, R Temlyakov, V Univ S Carolina Dept Math Ind Math Inst Columbia SC 29208 USA Univ Paris 06 Lab Jacques Louis Lions F-75013 Paris France Rhein Westfal TH Aachen Inst Geomet & Prakt Math D-52056 Aachen Germany

This paper is concerned with the construction and analysis of a universal estimator for the regression problem in supervised learning. universal means that the estimator does not depend on any a priori assumptions about the regression function to be estimated. The universal estimator studied in this paper consists of a least-square fitting procedure using piecewise constant functions on a partition which depends adaptively on the data. The partition is generated by a splitting procedure which differs from those used in CART algorithms. It is proven that this estimator performs at the optimal convergence rate for a wide class of priors on the regression function. Namely, as will be made precise in the text, if the regression function is in any one of a certain class of approximation spaces (or smoothness spaces of order not exceeding one - a limitation resulting because the estimator uses piecewise constants) measured relative to the marginal measure, then the estimator converges to the regression function (in the least squares sense) with an optimal rate of convergence in terms of the number of samples. The estimator is also numerically feasible and can be implemented on-line.

关键词： distribution-free learning theory nonparametric regression universal algorithms adaptive approximation on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

universal algorithms for channel decoding of uncompressed sources

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第5期54卷 2243-2262页

作者： Ordentlich, Erik Seroussi, Gadiel Verdu, Sergio Viswanathan, Krishnamurthy Hewlett Packard Labs Palo Alto CA 94304 USA Princeton Univ Dept Elect Engn Princeton NJ 08544 USA

In many applications, an uncompressed source stream is systematically encoded by a channel code (which ignores the source redundancy) for transmission over a discrete memoryless channel. The decoder knows the channel and the code but does not know the source statistics. This paper proposes several universal channel decoders that take advantage of the source redundancy without requiring prior knowledge of its statistics.

关键词： belief propagation channel decoding denoising discrete memoryless channels joint source-channel decoding loss-less compression soft decoding universal algorithms

来源：评论

学校读者我要写书评

暂无评论

universal algorithms for multinomial logistic regression under Kullback-Leibler game

引用

NEUROCOMPUTING 2020年 397卷 369-380页

作者： Dzhamtyrova, Raisa Kalnishkan, Yuri Royal Holloway Univ London Dept Comp Sci Egham Surrey England Moscow Inst Phys & Technol Lab Adv Combinator & Network Applicat Moscow Russia

We consider the framework of competitive prediction, where one provides guarantees compared to other predictive models that are called experts. We propose a universal algorithm predicting finite-dimensional distributions, i.e. points from a simplex, under Kullback-Leibler game. In the standard framework for prediction with expert advice, the performance of the learner is measured by means of the cumulative loss. In this paper we consider a generalisation of this setting and discount losses with time. A natural choice of predictors for the probability games is a class of multinomial logistic regression functions as they output a distribution that lies inside a probability simplex. We consider the class of multinomial logistic regressions to be our experts. We provide a strategy that allows us to 'track the best expert' of this type and derive the theoretical bound on the discounted loss of the strategy. We provide the kernelized version of our algorithm, which competes with a wider set of experts from Reproducing Kernel Hilbert Space (RKHS) and prove a theoretical guarantee for the kernelized strategy. We carry out experiments on three data sets and compare the cumulative losses of our algorithm and multinomial logistic regression. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Online learning Sequential prediction Competitive prediction universal algorithms Loss bounds Kullback-Leibler game

来源：评论

学校读者我要写书评

暂无评论

EMBEDDING RECURSIVE FUNCTIONS IN universal algorithms

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1988年第3-4期24卷 273-276页

作者： HIGGINS, J Department of Computer Science Brigham Young University Provo Utah 84602 United States

This note provides a demonstration of the fact that any function with a suitably sparse but infinite domain may be extended to a universal algorithm in the sense of Kolmogorov. Further, it is shown that strings random... 详细信息

关键词： Kolmogorov complexity sparse sets universal algorithms F.4.m

来源：评论

学校读者我要写书评

暂无评论

universal algorithms for Clustering Problems

引用

ACM TRANSACTIONS ON algorithms 2023年第2期19卷 15-15页

作者： Ganesh, Arun Maggs, Bruce M. Panigrahi, Debmalya Univ Calif Berkeley Soda Hall Berkeley CA 94709 USA Duke Univ 308 Res Dr Durham NC 27710 USA Emerald Innovat 308 Res Dr Durham NC 27710 USA

This article presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers such that they are a good solution for any subset of clients that actually realize. Specifically, we aim for low regret, defined as the maximum over all subsets of the difference between the cost of the algorithm's solution and that of an optimal solution. A universal algorithm's solution sol for a clustering problem is said to be an (alpha, beta)-approximation if for all subsets of clients C', it satisfies sol(C') <= alpha center dot opt(C') + beta center dot mr, where opt(C') is the cost of the optimal solution for clients C' and mr is the minimum regret achievable by any solution. Our main results are universal algorithms for the standard clustering objectives of k-median, k-means, and k-center that achieve (O(1), O(1))-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other l(p) objectives and the setting where some subset of the clients are fixed. We also give hardness results showing that (alpha, beta)-approximation is NP-hard if alpha or beta is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (O(1), O( 1))-approximation is the strongest type of guarantee obtainable for universal clustering.

关键词： universal algorithms clustering

来源：评论

学校读者我要写书评

暂无评论

Schemes for bidirectional modeling of discrete stationary sources

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第11期52卷 4789-4807页

作者： Yu, Jiming Verdu, Sergio Princeton Univ Dept Elect Engn Princeton NJ 08544 USA

We develop adaptive schemes for bidirectional modeling of unknown discrete stationary sources. These algorithms can be applied to statistical inference problems such as noncausal universal discrete denoising that exploit bidirectional dependencies. Efficient algorithms for constructing those models are developed and we compare their performance to that of the DUDE algorithm for universal discrete denoising.

关键词： bidirectional modeling discrete stationary sources universal algorithms universal discrete denoising

来源：评论

学校读者我要写书评

暂无评论

universal discrete denoising:: Known channel

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2005年第1期51卷 5-28页

作者： Weissman, T Ordentlich, E Seroussi, G Verdú, S Weinberger, MJ Stanford Univ Dept Elect Engn Stanford CA 94305 USA Hewlett Packard Labs Palo Alto CA 94304 USA Princeton Univ Dept Elect Engn Princeton NJ 08544 USA

A discrete denoising algorithm estimates the input sequence to a discrete memoryless channel (DMC) based on the observation of the entire output sequence. For the case in which the DMC is known and the quality of the reconstruction is evaluated with a given single-letter fidelity criterion, we propose a discrete denoising algorithm that does not assume knowledge of statistical properties of the input sequence. Yet, the algorithm is universal in the sense of asymptotically performing as well as the optimum denoiser that knows the input sequence distribution, which is only assumed to be stationary. Moreover, the algorithm is universal also in a semi-stochastic setting, in which the input is an individual sequence, and the randomness is due solely to the channel noise. The proposed denoising algorithm is practical, requiring a linear number of register-level operations and sublinear working storage size relative to the input data length.

关键词： context models denoising discrete filtering discrete memoryless channels (DMCs) individual sequences noisy channels universal algorithms

来源：评论

学校读者我要写书评

暂无评论

Deformation techniques to solve Generalised Pham Systems

引用

THEORETICAL COMPUTER SCIENCE 2004年第2-3期315卷 593-625页

作者： Pardo, LM Martín, JS Univ Cantabria Fac Ciencias Dept Matemat Estadist & Computac E-39071 Santander Spain Univ Rey Juan Carlos Dept Informat Estadist & Telemat Escuela Super Ciencias Expt & Tecnol Mostolas 28933 Spain

In Heintz et al. (Electron. J. SADIO 1(1) (1998) 37), Castro et al. (Found., Comput. Math. (2003) to appear) and Pardo (Proceedings EACA'2000, 2000, pp. 25-51), the authors have shown that universal solving procedures require exponential running time. Roughly speaking, a universal solving procedure takes as input a system of multivariate polynomial equations and outputs complete symbolic information on the solution variety. Here, we introduce a non-universal solving procedure adapted to Generalised Pham Systems. The aim is to compute partial information of the variety defined by the input system. The Algorithm is based on an homotopic deformation and on a non-Archimedean lifting procedure from a non-singular zero of the homotopy curve. The complexity of the procedure is also stated and it depends on some intrinsic quantity called the deformation degree of the given input system. (C) 2004 Elsevier B.V. All rights reserved.

关键词： Generalised Pham System universal algorithms homotopic deformation geometric degree

来源：评论

学校读者我要写书评

暂无评论

SET COVERING WITH OUR EYES CLOSED

引用

SIAM JOURNAL ON COMPUTING 2013年第3期42卷 808-830页

作者： Grandoni, Fabrizio Gupta, Anupam Leonardi, Stefano Miettinen, Pauli Sankowski, Piotr Singh, Mohit Univ Lugano IDSIA CH-6928 Manno Lugano Switzerland Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00185 Rome Italy Max Planck Inst Informat D-66123 Saarbrucken Germany Univ Roma La Sapienza I-00185 Rome Italy Univ Helsinki Helsinki Inst Informat Technol FIN-00014 Helsinki Finland Univ Warsaw Inst Informat PL-02097 Warsaw Poland McGill Univ Sch Comp Sci Montreal PQ H3A 2A7 Canada Carnegie Mellon Univ Pittsburgh PA 15213 USA

Given a universe U of n elements and a weighted collection S of m subsets of U, the universal set cover problem is to a priori map each element u is an element of U to a set S(u) is an element of S containing u such that any set X subset of U is covered by S(X) - boolean OR S-u is an element of X(u). The aim is to find a mapping such that the cost of S(X) is as close as possible to the optimal set cover cost for X. (Such problems are also called oblivious or a priori optimization problems.) Unfortunately, for every universal mapping, the cost of S(X) can be O(root n) times larger than optimal if the set X is adversarially chosen. In this paper we study the performance on average, when X is a set of randomly chosen elements from the universe: we show how to efficiently find a universal map whose expected cost is O(log mn) times the expected optimal cost. In fact, we give a slightly improved analysis and show that this is the best possible. We generalize these ideas to weighted set cover and show similar guarantees to (nonmetric) facility location, where we have to balance the facility opening cost with the cost of connecting clients to the facilities. We show applications of our results to universal multicut and disc-covering problems and show how all these universal mappings give us algorithms for the stochastic online variants of the problems with the same competitive factors.

关键词： approximation algorithms universal algorithms online algorithms set cover facility location

来源：评论

学校读者我要写书评

暂无评论

universal denoising for the finite-input general-output channel

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2005年第4期51卷 1507-1517页

作者： Dembo, A Weissman, T Stanford Univ Dept Math Stanford CA 94305 USA Stanford Univ Dept Stat Stanford CA 94305 USA Stanford Univ Dept Elect Engn Stanford CA 94305 USA

We consider the problem of reconstructing a finite-alphabet signal corrupted by a known memoryless channel with a general output alphabet. The goodness of the reconstruction is measured by a given loss function. We (constructively) establish the existence of a universal (sequence of) denoiser(s) attaining asymptotically the optimum distribution-dependent performance for any stationary source that may be generating the noiseless signal. We show, in fact, that there is a whole family of denoiser sequences with this property. These schemes are shown to be universal also in a semistochastic setting, where the only randomness assumed is that associated with the channel noise. The scheme is practical, requiring O (n(1+epsilon)) operations (for any epsilon > 0) and working storage size sublinear in the input data length. This extends recent work that presented a discrete universal denoiser for recovering a discrete source corrupted by a discrete memoryless channel (DMC).

关键词： denoising discrete universal denoising filtering individual sequences memoryless channels noisy channels quantization sliding-window schemes universal algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：