NDLI: Interruptible anytime algorithms for iterative improvement of decision trees

Please wait, while we are loading the content...

Toward economic machine learning and utility-based data mining

Economical active feature-value acquisition through Expected Utility estimation

Machine learning paradigms for utility-based data mining

Reinforcement learning for active model selection

Cost-sensitive classifier evaluation

Wrapper-based computation and evaluation of sampling methods for imbalanced datasets

Noisy information value in utility-based decision making

Learning policies for sequential time and cost sensitive classification

Improving classifier utility by altering the misclassification cost ratio

One-Benefit learning: cost-sensitive learning with restricted cost information

Utility based data mining for time series analysis: cost-sensitive learning for neural network predictors

Does cost-sensitive learning beat sampling for classifying rare classes?

Interruptible anytime algorithms for iterative improvement of decision trees

Contextual recommender problems [extended abstract]

A fast high utility itemsets mining algorithm

Interruptible anytime algorithms for iterative improvement of decision trees

Content Provider	ACM Digital Library
Author	Markovitch, Shaul Esmeir, Saher
Abstract	Finding a minimal decision tree consistent with the examples is an NP-complete problem. Therefore, most of the existing algorithms for decision tree induction use a greedy approach based on local heuristics. These algorithms usually require a fixed small amount of time and result in trees that are not globally optimal. Recently, the LSID3 contract anytime algorithm was introduced to allow using extra resources for building better decision trees. A contract anytime algorithm needs to get its resource allocation a priori. In many cases, however, the time allocation is not known in advance, disallowing the use of contract algorithms. To overcome this problem, in this work we present two interruptible anytime algorithms for inducing decision trees. Interruptible anytime algorithms do not require their resource allocation in advance and thus must be ready to be interrupted and return a valid solution at any moment. The first interruptible algorithm we propose is based on a general technique for converting a contract algorithm to an interruptible one by sequencing. The second is an iterative improvement algorithm that repeatedly selects a subtree whose reconstruction is estimated to yield the highest marginal utility and rebuilds it with higher resource allocation. Empirical evaluation shows a good anytime behavior for both algorithms. The iterative improvement algorithm shows smoother performance profiles which allow more refined control.
Starting Page	78
Ending Page	85
Page Count	8
File Format	PDF
ISBN	1595932089
DOI	10.1145/1089827.1089837
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-08-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Anytime algorithms Anytime learning Cost-quality tradeoff Decision trees Hard concepts
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in