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

Satisfiability decay along conjunctions of pseudo-random clauses

LOGIC JOURNAL OF THE IGPL 2006年第5期14卷 815-825页

作者： Shamir, Eli Hebrew Univ Jerusalem Inst Math IL-91905 Jerusalem Israel Hebrew Univ Jerusalem Sch Comp Sci IL-91905 Jerusalem Israel

k-SAT is a fundamental constraint satisfaction problem. It involves S(m), the satisfaction set of the conjunction of m clauses, each clause a disjunction of k literals. The problem has many theoretical, algorithmic and practical aspects. When the clauses are chosen at random it is anticipated (but not fully proven) that, as the density parameter m/n (n the number of variables) grows, the transition of S(m) to being empty, is abrupt: It has a "sharp threshold", with probability 1 - o(1). In this article we replace the random ensemble analysis by a pseudo-random one: Derive the decay rule for individual sequences of clauses, subject to combinatorial conditions, which in turn hold with probability 1 - o(1). This is carried out under the big relaxation that k is not constant but k = gamma log n, or even r log log n. Then the decay of S is slow, "near-perfect" (like a radioactive decay), which entails sharp thresholds for the transition-time of S below any given level, down to S = 0.

关键词： constraint satisfaction k-SAT sharp thresholds pseudorandom analysis unique k-SAT representations learning from examples

来源：评论

学校读者我要写书评

暂无评论

Rapid learning-based video stereolization using graphic processing unit acceleration

引用

JOURNAL OF ELECTRONIC IMAGING 2016年第5期25卷

作者： Sun, Tian Jung, Cheolkon Wang, Lei Kim, Joongkyu Xidian Univ Sch Elect Engn Xian 710071 Peoples R China Sungkyunkwan Univ Coll Informat & Commun Engn Suwon 440746 South Korea

Video stereolization has received much attention in recent years due to the lack of stereoscopic three-dimensional (3-D) contents. Although video stereolization can enrich stereoscopic 3-D contents, it is hard to achieve automatic two-dimensional-to-3-D conversion with less computational cost. We proposed rapid learning-based video stereolization using a graphic processing unit (GPU) acceleration. We first generated an initial depth map based on learning from examples. Then, we refined the depth map using saliency and cross-bilateral filtering to make object boundaries clear. Finally, we performed depth-image-based-rendering to generate stereoscopic 3-D views. To accelerate the computation of video stereolization, we provided a parallelizable hybrid GPU-central processing unit (CPU) solution to be suitable for running on GPU. Experimental results demonstrate that the proposed method is nearly 180 times faster than CPU-based processing and achieves a good performance comparable to the-state-of-the-art ones. (C) 2016 SPIE and IS&T

关键词： two-dimensional-to-three-dimensional conversion depth-image-based-rendering graphic processing unit acceleration learning from examples visual saliency video stereolization

来源：评论

学校读者我要写书评

暂无评论

NOISE-TOLERANT OCCAM ALGORITHMS AND THEIR APPLICATIONS TO learning DECISION TREES

引用

MACHINE learning 1993年第1期11卷 37-62页

作者： SAKAKIBARA, Y International Institute for Advanced Study of Social Information Science (IIAS-SIS) Fujitsu Laboratories Ltd Shizuoka Japan

In the distribution-independent model of concept learning of Valiant, Angluin arid Laird have introduced a formal model of noise process, called classification noise process, to study how to compensate for randomly introduced errors, or noise, in classifying the example data. In this article, we investigate the problem of designing efficient learning algorithms in the presence of classification noise. First, we develop a technique of building efficient robust learning algorithms, called noise-tolerant Occam algorithms, and show that using them, one can construct a polynomial-time algorithm for learning a class of Boolean functions in the presence of classification noise. Next, as an instance of such problems of learning in the presence of classification noise, we focus on the learning problem of Boolean functions represented by decision trees. We present a noise-tolerant Occam algorithm for k-DL (the class of decision lists with conjunctive clauses of size at most k at each decision introduced by Rivest) and hence conclude that k-DL is polynomially learnable in the presence of classification noise. Further, we extend the noise-tolerant Occam algorithm for k-DL to one for r-DT (the class of decision trees of rank at most r introduced by Ehrenfeucht and Haussler) and conclude that r-DT is polynomially learnable in the presence of classification noise.

关键词： learning from examples PROBABLY APPROXIMATELY CORRECT learning NOISY examples POLYNOMIAL-TIME LEARNABILITY DECISION LISTS DECISION TREES

来源：评论

学校读者我要写书评

暂无评论

A PARALLEL MONOTONIC CLASSIFICATION MACHINE

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 1994年第1期7卷 77-82页

作者： BENDAVID, A HEBREW UNIV JERUSALEM SCH BUSINESS ADMDEPT MANAGEMENT INFORMAT SYSTJERUSALEMISRAEL

Current parallel machines, such as array processors and Prolog or Lisp machines, are not optimized to execute monotonic classification tasks. A new special-purpose parallel computer is proposed, which efficiently solves this important type of problem from examples it encounters. After the study of sufficient examples, the macine is capable of classifying objects which it might have never seen before. What makes the machine unique is its low gate count when compared with its counterparts.

关键词： learning from examples MONOTONIC CLASSIFICATION PARALLEL COMPUTERS ARTIFICIAL INTELLIGENCE MACHINES

来源：评论

学校读者我要写书评

暂无评论

Global discretization of continuous attributes as preprocessing for machine learning

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 1996年第4期15卷 319-331页

作者： Chmielewski, MR GrzymalaBusse, JW UNIV KANSAS DEPT ELECT ENGN & COMP SCILAWRENCEKS 66045

Real-life data usually are presented in databases by real numbers. On the other hand, most inductive learning methods require a small number of attribute values. Thus it is necessary to convert input data sets with continuous attributes into input data sets with discrete attributes. Methods of discretization restricted to single continuous attributes will be called local, while methods that simultaneously convert all continuous attributes will be called global. in this paper, a method of transforming any local discretization method into a global one is presented. A global discretization method, based on cluster analysis is presented and compared experimentally with three known local methods, transformed into global. Experiments include tenfold cross-validation and leaving-one-out methods for ten real-life data sets. (C) 1996 Elsevier Science Inc.

关键词： discretization quantization continuous attributes learning from examples rough set theory

来源：评论

学校读者我要写书评

暂无评论

The Minimum Feature Subset Selection Problem

引用

Journal of Computer Science & Technology 1997年第2期12卷 145-153页

作者：陈彬洪家荣王亚东 DepartmentofComputerScience HarbinInstituteofTechnologyHarbin150001

In applications of learning from examples to real-world tasks, feature subset selection is important to speed up training and to improve generalization performance. ideally, an inductive algorithm should use subset of features as small as possible. In this paper however, the authors show that the problem of selecting the minimum subset of features is NP-hard. The paper then presents a greedy algorithm for feature subset selection. The result of running the greedy algorithm on hand-written numeral recognition problem is also given.

关键词： learning from examples NP-hard greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

On the optimization of fuzzy decision trees

引用

FUZZY SETS AND SYSTEMS 2000年第1期112卷 117-125页

作者： Wang, XZ Chen, B Qian, GL Ye, F Hebei Univ Dept Math Baoding 071002 Hebei Peoples R China Harbin Inst Technol Dept Comp Sci Machine Learning Grp Harbin 150001 Peoples R China

The induction of fuzzy decision trees is an important way of acquiring imprecise knowledge automatically. Fuzzy ID3 and its variants are popular and efficient methods of making fuzzy decision trees from a group of training examples. This paper points out the inherent defect of the likes of Fuzzy ID3, presents two optimization principles of fuzzy decision trees, proves that the algorithm complexity of constructing a kind of minimum fuzzy decision tree is NP-hard, and gives a new algorithm which is applied to three practical problems. The experimental results show that, with regard to the size of trees and the classification accuracy for unknown cases, the new algorithm is superior to the likes of Fuzzy ID3. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： machine learning learning from examples knowledge acquisition and learning fuzzy decision trees complexity of fuzzy algorithms NP-hardness

来源：评论

学校读者我要写书评

暂无评论

Generalization properties of modular networks: Implementing the parity function

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS 2001年第6期12卷 1306-1313页

作者： Franco, L Cannas, SA Univ Nacl Cordoba Fac Matemat Astron & Fis Condensed Matter Grp RA-5000 Cordoba Argentina

The parity function is one of the most used Boolean function for testing learning algorithms because both of its simple definition and its great complexity. Being one of the hardest problems, many different architectures have been constructed to compute parity, essentially by adding neurons in the hidden layer in order to reduce the number of local minima where gradient-descent learning algorithms could get stuck. We construct a family of modular architectures that implement the parity function in which, every member of the family can be characterized by the fan-in max of the network, i.e., the maximum number of connections that a neuron can receive. We analyze the generalization ability of the modular networks first by computing analytically the minimum number of examples needed for perfect generalization and second by numerical simulations. Both results show that the generalization ability of these networks is systematically improved by the degree of modularity of the network. We also analyze the influence of the selection of examples in the emergence of generalization ability, by comparing the learning curves obtained through a random selection of examples to those obtained through examples selected accordingly to a general algorithm we recently proposed.

关键词： circuit complexity generalization learning from examples modular neural networks parity function

来源：评论

学校读者我要写书评

暂无评论

COMBINING ROUGH SETS learning-METHOD AND NEURAL learning-METHOD TO DEAL WITH UNCERTAIN AND IMPRECISE INFORMATION

引用

NEUROCOMPUTING 1995年第1期7卷 61-84页

作者： YASDI, R University Heidelberg Im Neuheimerfeld 294 69120 Heidelberg Germany

Any system designed to reason about the real world must be capable of dealing with uncertainty. The complexity of the real world and the finite size of most knowledge bases pose significant difficulties for the traditional concept of the learning system. Experience has shown that many learning paradigms fail to scale up to those problems. One response to these failures has been to construct systems which use multiple learning paradigms. Thus the strengths of one paradigm counterbalance some of the weaknesses of the others. As a result the effectiveness of the overall system will be enhanced. Consequently, integrated techniques have been widespread over the last years. A multistrategy which addresses those issues is presented. This approach joins two forms of learning, the technique of neural networks and rough sets. These seem at first quite different but they share the common ability to work well in a natural environment. In a closed loop fashion we will achieve more robust concept learning capabilities for a variety of difficult classification tasks. The objective of integration is twofold: (i) to improve the overall classification effectiveness of learned objects' description, (ii) to refine the dependency factors of the rules.

关键词： INDUCTIVE learning learning from examples ROUGH SETS NEURAL NETS

来源：评论

学校读者我要写书评

暂无评论

An integration of rule induction and exemplar-based learning for graded concepts

引用

MACHINE learning 1995年第3期21卷 235-267页

作者： Zhang, JP Michalski, RS GEORGE MASON UNIV CTR ARTIFICIAL INTELLIGENCEFAIRFAXVA 22030

This paper presents a method for learning graded concepts. Our method uses a hybrid concept representation that integrates numeric weights and thresholds with rules and combines rules with exemplars. Concepts are learned by constructing general descriptions to represent common cases. These general descriptions are in the form of decision rules with weights on conditions, interpreted by a similarity measure and numeric thresholds. The exceptional cases are represented as exemplars. This method was implemented in the Flexible Concept learning System (FCLS) and tested on a variety of problems. The testing problems included practical concepts, concepts with graded structures, and concepts that can be defined in the classic view. For comparison, a decision tree learning system, an instance-based learning system, and the basic rule learning variant of FCLS were tested on the same problems. The results have shown a statistically meaningful advantage of the proposed method over others both in terms of classification accuracy and description simplicity on several problems.

关键词： learning from examples graded concepts exemplar-based learning concept learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：