Feature Generation Using General Constructor Functions

Most classification algorithms receive as input a set of attributes of the classified objects. In many cases, however, the supplied set of attributes is not sufficient for creating an accurate, succinct and comprehensible representation of the target concept. To overcome this problem, researchers have proposed algorithms for automatic construction of features. The majority of these algorithms use a limited predefined set of operators for building new features. In this paper we propose a generalized and flexible framework that is capable of generating features from any given set of constructor functions. These can be domain-independent functions such as arithmetic and logic operators, or domain-dependent operators that rely on partial knowledge on the part of the user. The paper describes an algorithm which receives as input a set of classified objects, a set of attributes, and a specification for a set of constructor functions that contains their domains, ranges and properties. The algorithm produces as output a set of generated features that can be used by standard concept learners to create improved classifiers. The algorithm maintains a set of its best generated features and improves this set iteratively. During each iteration, the algorithm performs a beam search over its defined feature space and constructs new features by applying constructor functions to the members of its current feature set. The search is guided by general heuristic measures that are not confined to a specific feature representation. The algorithm was applied to a variety of classification problems and was able to generate features that were strongly related to the underlying target concepts. These features also significantly improved the accuracy achieved by standard concept learners, for a variety of classification problems.     

Discovery as Autonomous Learning from the Environment

Discovery involves collaboration among many intelligent activities. However, little is known about how and in what form such collaboration occurs. In this article, a framework is proposed for autonomous systems that learn and discover from their environment. Within this framework, many intelligent activities such as perception, action, exploration, experimentation, learning, problem solving, and new term construction can be integrated in a coherent way. The framework is presented in detail through an implemented system called LIVE, and is evaluated through the performance of LIVE on several discovery tasks. The conclusion is that autonomous learning from the environment is a feasible approach for integrating the activities involved in a discovery process.     

What do Constructive Learners Really Learn?

In constructive induction (CI), the learner's problem representation is modified as a normal part of the learning process. This may be necessary if the initial representation is inadequate or inappropriate. However, the distinction between constructive and non-constructive methods appears to be highly ambiguous. Several conventional definitions of the process of constructive induction appear to include all conceivable learning processes. In this paper I argue that the process of constructive learning should be identified with that of relational learning (i.e., I suggest that what constructive learners really learn is relationships) and I describe some of the possible benefits that might be obtained as a result of adopting this definition.     

Learning hard concepts through constructive induction: framework and rationale

The intrinsic accuracy of an inductive problem is the accuracy achieved by exhaustive table look-up. Intrinsic accuracy is the upper bound for any inductive method. Hard concepts are concepts that have high intrinsic accuracy, but which cannot be learned effectively with traditional inductive methods. To learn hard concepts, we must use constructive induction - methods that create new features. We use measures of concept dispersion to explore (conceptually and empirically) the inherent weaknesses of traditional inductive approaches. These structural defects are buried in the design of the algorithms and prevent the learning of hard concepts. After studying some examples of successful and unsuccessful feature construction ("success" being defined here in terms of accuracy), we introduce a single measure of inductive difficulty that we call variation. We argue for a specific approach to constructive induction that reduces variation by incorporating various kinds of domain knowledge. All of these kinds of domain knowledge boil down to utility invariants, i.e., transformations that group together non-contiguous portions of feature space having similar class-membership values. Utility invariants manifest themselves in various ways: in some cases they exist in the user's stock of domain knowledge, in other cases they may be discovered via methods we describe.     

Practical Issues in Temporal Difference Learning

This paper examines whether temporal difference methods for training connectionist networks, such as Sutton's TD() algorithm, can be successfully applied to complex real-world problems. A number of important practical issues are identified and discussed from a general theoretical perspective. These practical issues are then examined in the context of a case study in which TD() is applied to learning the game of backgammon from the outcome of self-play. This is apparently the first application of this algorithm to a complex non-trivial task. It is found that, with zero knowledge built in, the network is able to learn from scratch to play the entire game at a fairly strong intermediate level of performance, which is clearly better than conventional commercial programs, and which in fact surpasses comparable networks trained on a massive human expert data set. This indicates that TD learning may work better in practice than one would expect based on current theory, and it suggests that further analysis of TD methods, as well as applications in other complex domains, may be worth investigating.     

Constructing X-of-N Attributes for Decision Tree Learning

While many constructive induction algorithms focus on generating new binary attributes, this paper explores novel methods of constructing nominal and numeric attributes. We propose a new constructive operator, X-of-N. An X-of-N representation is a set containing one or more attribute-value pairs. For a given instance, the value of an X-of-N representation corresponds to the number of its attribute-value pairs that are true of the instance. A single X-of-N representation can directly and simply represent any concept that can be represented by a single conjunctive, a single disjunctive, or a single M-of-N representation commonly used for constructive induction, and the reverse is not true. In this paper, we describe a constructive decision tree learning algorithm, called XofN. When building decision trees, this algorithm creates one X-of-N representation, either as a nominal attribute or as a numeric attribute, at each decision node. The construction of X-of-N representations is carried out by greedily searching the space defined by all the attribute-value pairs of a domain. Experimental results reveal that constructing X-of-N attributes can significantly improve the performance of decision tree learning in both artificial and natural domains in terms of higher prediction accuracy and lower theory complexity. The results also show the performance advantages of constructing X-of-N attributes over constructing conjunctive, disjunctive, or M-of-N representations for decision tree learning.     

Feature construction with Inductive Logic Programming: A Study of Quantitative Predictions of Biological Activity Aided by Structural Attributes

Recently, computer programs developed within the field of Inductive Logic Programming (ILP) have received some attention for their ability to construct restricted first-order logic solutions using problem-specific background knowledge. Prominent applications of such programs have been concerned with determining structure-activity relationships in the areas of molecular biology and chemistry. Typically the task here is to predict the activity of a compound (for example, toxicity), from its chemical structure. A summary of the research in the area is: (a) ILP programs have largely been restricted to qualitative predictions of activity (high, low etc.); (b) When appropriate attributes are available, ILP programs have equivalent predictivity to standard quantitative analysis techniques like linear regression. However ILP programs usually perform better when such attributes are unavailable; and (c) By using structural information as background knowledge, an ILP program can provide comprehensible explanations for biological activity. This paper examines the use of ILP programs as a method of discovering new attributes. These attributes could then be used by methods like linear regression, thus allowing for quantitative predictions while retaining the ability to use structural information as background knowledge. Using structure-activity tasks as a test-bed, the utility of ILP programs in constructing new features was evaluated by examining the prediction of biological activity using linear regression, with and without the aid of ILP learnt logical attributes. In three out of the five data sets examined the addition of ILP attributes produced statistically better results. In addition six important structural features that have escaped the attention of the expert chemists were discovered. The method used here to construct new attributes is not specific to the problem of predicting biological activity, and the results obtained suggest a wider role for ILP programs in aiding the process of scientific discovery.     

构造性混合决策树

提出了一种构造性混合决策树学习方法CHDT。该方法用符号学习来进行定性分析,用神经学习进行后续的定量分析,在一定程度上模拟了人类的思维过程。CHDT采用了一种独特的构造性归纳机制,较好地解决了在缺乏领域知识指导的情况下进行构造性学习的问题,它通过采用FTART2网络和适宜于混合决策树的神经网络嵌入机制,获得了较强的泛化能力。实验结果表明,CHDT能构造出结构简洁、预测精度高的混合决策树。     

一个增量式判定树学习算法INDUCE

ＩＮＤＵＣＥ算法采用自顶向下判定树归纳的学习方法,不仅具有健壮性好,效率高和正确率高等优点,还具有增量学习能力,可以动态修正概念描述的不足,该算法还运用了构造性归纳的思想,在学习过程中生成新的描述子,使概念描述空间搜索的效率得到提高。运行实例表明,ＩＮＤＵＣＥ具有很好的应用前景。     

Nearest-Neighbours for Time Series

This paper presents an application of lazy learning algorithms in the domain of industrial processes. These processes are described by a set of variables, each corresponding a time series. Each variable plays a different role in the process and some mutual influences can be discovered.A methodology to study the different variables and their roles in the process are described. This methodology allows the structuration of the study of the time series.The prediction methodology is based on a k-nearest neighbour algorithm. A complete study of the different parameters of this kind of algorithm is done, including data preprocessing, neighbour distance, and weighting strategies. An alternative to Euclidean distance called shape distance is presented, this distance is insensitive to scaling and translation. Alternative weighting strategies based on time series autocorrelation and partial autocorrelation are also presented.Experiments using autorregresive models, simulated data and real data obtained from an industrial process (Waste water treatment plants) are presented to show the feasabilty of our approach.     

Adaptive Fraud Detection

One method for detecting fraud is to check for suspicious changes in user behavior. This paper describes the automatic design of user profiling methods for the purpose of fraud detection, using a series of data mining techniques. Specifically, we use a rule-learning program to uncover indicators of fraudulent behavior from a large database of customer transactions. Then the indicators are used to create a set of monitors, which profile legitimate customer behavior and indicate anomalies. Finally, the outputs of the monitors are used as features in a system that learns to combine evidence to generate high-confidence alarms. The system has been applied to the problem of detecting cellular cloning fraud based on a database of call records. Experiments indicate that this automatic approach performs better than hand-crafted methods for detecting fraud. Furthermore, this approach can adapt to the changing conditions typical of fraud detection environments.     

基于资源信息细分的学习评价系统的设计与实现

在网络化学习系统中,如何准确地发现学习者的缺陷是学习评价系统的主要任务,也是一个非常困难的问题。该系统通过对学习资源标注知识点、能力点、方法点、错误现象和错误归因等信息,将学习资源所包含的信息进一步细分和深化,再以测试结果为基础进行评价,能够更准确地发现学习者的缺陷。     

Control-Sensitive Feature Selection for Lazy Learners

High sensitivity to irrelevant features is arguably the main shortcoming of simple lazy learners. In response to it, many feature selection methods have been proposed, including forward sequential selection (FSS) and backward sequential selection (BSS). Although they often produce substantial improvements in accuracy, these methods select the same set of relevant features everywhere in the instance space, and thus represent only a partial solution to the problem. In general, some features will be relevant only in some parts of the space; deleting them may hurt accuracy in those parts, but selecting them will have the same effect in parts where they are irrelevant. This article introduces RC, a new feature selection algorithm that uses a clustering-like approach to select sets of locally relevant features (i.e., the features it selects may vary from one instance to another). Experiments in a large number of domains from the UCI repository show that RC almost always improves accuracy with respect to FSS and BSS, often with high significance. A study using artificial domains confirms the hypothesis that this difference in performance is due to RC's context sensitivity, and also suggests conditions where this sensitivity will and will not be an advantage. Another feature of RC is that it is faster than FSS and BSS, often by an order of magnitude or more.     

递归逻辑程序的强构造分层学习算法及其实现

本文提出了一种逻辑程序的强构造分层学习算法用该算法解决了一类递归逻辑程序的强构造二层学问题，为强的构造学习研究提供了一个新的思路，并就有关问题进行了详细的讨论。     

Task-specific Part Discovery for Fine-grained Few-shot Classification

Localizing discriminative object parts(e.g.,bird head)is crucial for fine-grained classification tasks,especially for the more challenging fine-grained few-shot scenario.Previous work always relies on the learned object parts in a unified manner,where they at-tend the same object parts(even with common attention weights)for different few-shot episodic tasks.In this paper,we propose that it should adaptively capture the task-specific object parts that require attention for each few-shot task,since the parts that can distin-guish different tasks are naturally different.Specifically for a few-shot task,after obtaining part-level deep features,we learn a task-spe-cific part-based dictionary for both aligning and reweighting part features in an episode.Then,part-level categorical prototypes are gen-erated based on the part features of support data,which are later employed by calculating distances to classify query data for evaluation.To retain the discriminative ability of the part-level representations(i.e.,part features and part prototypes),we design an optimal trans-port solution that also utilizes query data in a transductive way to optimize the aforementioned distance calculation for the final predic-tions.Extensive experiments on five fine-grained benchmarks show the superiority of our method,especially for the 1-shot setting,gain-ing 0.12％,8.56％ and 5.87％ improvements over state-of-the-art methods on CUB,Stanford Dogs,and Stanford Cars,respectively.     

Classification of Multivariate Time Series and Structured Data Using Constructive Induction

We present a method of constructive induction aimed at learning tasks involving multivariate time series data. Using metafeatures, the scope of attribute-value learning is expanded to domains with instances that have some kind of recurring substructure, such as strokes in handwriting recognition, or local maxima in time series data. The types of substructures are defined by the user, but are extracted automatically and are used to construct attributes.Metafeatures are applied to two real domains: sign language recognition and ECG classification. Using metafeatures we are able to generate classifiers that are either comprehensible or accurate, producing results that are comparable to hand-crafted preprocessing and comparable to human experts.     

A Multistrategy Approach to Classifier Learning from Time Series

We present an approach to inductive concept learning using multiple models for time series. Our objective is to improve the efficiency and accuracy of concept learning by decomposing learning tasks that admit multiple types of learning architectures and mixture estimation methods. The decomposition method adapts attribute subset selection and constructive induction (cluster definition) to define new subproblems. To these problem definitions, we can apply metric-based model selection to select from a database of learning components, thereby producing a specification for supervised learning using a mixture model. We report positive learning results using temporal artificial neural networks (ANNs), on a synthetic, multiattribute learning problem and on a real-world time series monitoring application.