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

Classifier performance as a function of distributional complexity

PATTERN RECOGNITION 2004年第8期37卷 1641-1651页

作者： Attoor, SN Dougherty, ER Texas A&M Univ Dept Elect Engn College Stn TX 77843 USA Univ Texas MD Anderson Canc Ctr Dept Pathol Houston TX 77030 USA

When choosing a classification rule, it is important to take into account the amount of sample data available. This paper examines the performances of classifiers of differing complexities in relation to the complexity of feature-label distributions in the case of small samples. We define the distributional complexity of a feature-label distribution to be the minimal number of hyperplanes necessary to achieve the Bayes classifier if the Bayes classifier is achievable by a finite number of hyperplanes, and infinity otherwise. Our approach is to choose a model and compare classifier efficiencies for various sample sizes and distributional complexities. Simulation results are obtained by generating data based on the model and the distributional complexities. A linear support vector machine (SVM) is considered, along with several nonlinear classifiers. For the most part, we see that there is little improvement when one uses a complex classifier instead of a linear SVM. For higher levels of distributional complexity, the linear classifier degrades, but so do the more complex classifiers owing to insufficient training data. Hence, if one were to obtain a good result with a more complex classifier, it is most likely that the distributional complexity is low and there is no gain over using a linear classifier. Hence, under the model, it is generally impossible to claim that use of the nonlinear classifier is beneficial. In essence, the sample sizes are too small to take advantage of the added complexity. An exception to this observation is the behavior of the three-nearest-neighbor (3NN) classifier in the case of two variables (but not three) when there is very little overlap between the label distributions and the sample size is not too small. With a sample size of 60, the 3NN classifier performs close to the Bayes classifier, even for high levels of distributional complexity. Consequently, if one uses the 3NN classifier with two variables and obtains a low error, then the

关键词： classifier design classifier dimension distributional complexity small samples

来源：评论

学校读者我要写书评

暂无评论

Eigen-distribution on random assignments for game trees

引用

INFORMATION PROCESSING LETTERS 2007年第2期104卷 73-77页

作者： Liu, ChenGuang Tanaka, Kazuyuki Tohoku Univ Inst Math Sendai Miyagi 9808578 Japan

In this Letter, we investigate a special distribution, called eigen-distribution, on random assignments for a class of game trees T-2(k). There are two cases, where the assignments to leaves are independently distributed (ID) and correlated distributed (CD). In the ID case, we prove that the distributional probability p belongs to [root 7-13, root 5-1/2], and rho is a strictly increasing function on rounds 3 2 k epsilon [1, infinity). In the CD case, we propose a reverse assigning technique (RAT) to form two particular sets of assignments, 1-set and 0-set, then show that the E-1-distribution (namely, a particular distribution on the assignments of I-set such that all the deterministic algorithms have the same complexity) is the unique eigen-distribution for T-2(k) in the global distribution. 2 (c) 2007 Elsevier B.V. All rights reserved.

关键词： eigen-distribution game tree computational complexity distributional complexity randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Eigen-Distribution on Assignments for Game Trees with Random Properties 07

Eigen-Distribution on Assignments for Game Trees with Random...

引用

22nd ACM Symposium on Applied Computing

作者： Liu, ChenGuang Tanaka, Kazuyuki Tohoku Univ Math Inst Sendai Miyagi 9808578 Japan

ISBN: (纸本)9781595934802

In this paper, we investigate a special distribution, called eigen-distribution, on assignments for game tree T(2)(k) with random properties. There are two cases, where the assignments to leaves are independently distributed (ID) and correlated distributed (CD). In ID setting, we prove that the distributional probability rho belongs to [root 7-1/3, root 5-1/2], and rho is a strictly increasing function on rounds k is an element of [1,infinity). In CD setting, we propose a reverse assigning technique (RAT) to form I-set and 0-set, then show that E(1)-distribution (namely, a particular distribution on assignments of 1-set such that the complexity of any deterministic algorithm is equal) is the unique eigen-distribution.

关键词： Computational complexity distributional complexity Eigen-distribution Game trees Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Relationship between classifier performance and distributional complexity for small samples

Relationship between classifier performance and distribution...

引用

作者： Attoor, Sanju Nair Texas A&M University

Given a limited number of samples for classification, several issues arise with respect to design, performance and analysis of classifiers. This is especially so in the case of microarray-based classification. In this paper, we use a complexity measure based mixture model to study classifier performance for small sample problems. The motivation behind such a study is to determine the conditions under which a certain class of classifiers is suitable for classification, subject to the constraint of a limited number of samples being available. Classifier study in terms of the VC dimension of a learning machine is also discussed.

关键词： classifier small sample distributional complexity VC dimension Book Thesis

来源：评论

学校读者我要写书评

暂无评论

The communication requirements of efficient allocations and supporting prices

引用

JOURNAL OF ECONOMIC THEORY 2006年第1期129卷 192-224页

作者： Nisan, Noam Segal, Ilya Stanford Univ Dept Econ Stanford CA 94305 USA Hebrew Univ Jerusalem Inst Comp Sci Jerusalem Israel

We show that any communication finding a value-maximizing allocation in a private-information economy must also discover supporting prices (in general personalized and nonlinear). In particular, to allocate L indivisible items between two agents, a price must be revealed for each of the 2(L) - 1 bundles. We prove that all monotonic prices for an agent must be used, hence exponential communication in L is needed. Furthermore, exponential communication is needed just to ensure a higher share of surplus than that realized by auctioning all items as a bundle, or even a higher expected surplus (for some probability distribution over valuations). When the utilities are submodular, efficiency still requires exponential communication (and fully polynomial approximation is impossible). When the items are identical, arbitrarily good approximation is obtained with exponentially less communication than exact efficiency. (c) 2005 Elsevier Inc. All rights reserved.

关键词： communication complexity message space dimension preference elicitation informational efficiency of prices combinatorial auctions submodular valuations substitutable items homogenous items approximation distributional complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：