On the sample monotonization problem

Research output: Contribution to journalArticle

Abstract

The problem of finding a maximal subsample in a training sample consisting of the pairs "object-answer" that does not violate monotonicity constraints is considered. It is proved that this problem is NP-hard and that it is equivalent to the problem of finding a maximum independent set in special directed graphs. Practically important cases in which a partial order specified on the set of answers is a complete order or has dimension two are considered in detail. It is shown that the second case is reduced to the maximization of a quadratic convex function on a convex set. For this case, an approximate polynomial algorithm based on linear programming theory is proposed.

Original languageEnglish
Pages (from-to)1260-1266
Number of pages7
JournalComputational Mathematics and Mathematical Physics
Volume50
Issue number7
DOIs
Publication statusPublished - 2010
Externally publishedYes

Fingerprint

Programming theory
Directed graphs
Set theory
Linear programming
Computational complexity
Polynomials
Maximum Independent Set
Approximate Algorithm
Polynomial Algorithm
Training Samples
Violate
Quadratic Function
Partial Order
Directed Graph
Convex Sets
Convex function
Monotonicity
Two Dimensions
NP-complete problem

Keywords

  • Learning from precedents
  • Monotone constraints
  • NP-hard problem
  • Sample monotonization

ASJC Scopus subject areas

  • Computational Mathematics

Cite this

On the sample monotonization problem. / Takhanov, R. S.

In: Computational Mathematics and Mathematical Physics, Vol. 50, No. 7, 2010, p. 1260-1266.

Research output: Contribution to journalArticle

@article{dbe8fbeeb2b14feaa95edcb42f41d7f3,
title = "On the sample monotonization problem",
abstract = "The problem of finding a maximal subsample in a training sample consisting of the pairs {"}object-answer{"} that does not violate monotonicity constraints is considered. It is proved that this problem is NP-hard and that it is equivalent to the problem of finding a maximum independent set in special directed graphs. Practically important cases in which a partial order specified on the set of answers is a complete order or has dimension two are considered in detail. It is shown that the second case is reduced to the maximization of a quadratic convex function on a convex set. For this case, an approximate polynomial algorithm based on linear programming theory is proposed.",
keywords = "Learning from precedents, Monotone constraints, NP-hard problem, Sample monotonization",
author = "Takhanov, {R. S.}",
year = "2010",
doi = "10.1134/S0965542510070146",
language = "English",
volume = "50",
pages = "1260--1266",
journal = "Computational Mathematics and Mathematical Physics",
issn = "0965-5425",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "7",

}

TY - JOUR

T1 - On the sample monotonization problem

AU - Takhanov, R. S.

PY - 2010

Y1 - 2010

N2 - The problem of finding a maximal subsample in a training sample consisting of the pairs "object-answer" that does not violate monotonicity constraints is considered. It is proved that this problem is NP-hard and that it is equivalent to the problem of finding a maximum independent set in special directed graphs. Practically important cases in which a partial order specified on the set of answers is a complete order or has dimension two are considered in detail. It is shown that the second case is reduced to the maximization of a quadratic convex function on a convex set. For this case, an approximate polynomial algorithm based on linear programming theory is proposed.

AB - The problem of finding a maximal subsample in a training sample consisting of the pairs "object-answer" that does not violate monotonicity constraints is considered. It is proved that this problem is NP-hard and that it is equivalent to the problem of finding a maximum independent set in special directed graphs. Practically important cases in which a partial order specified on the set of answers is a complete order or has dimension two are considered in detail. It is shown that the second case is reduced to the maximization of a quadratic convex function on a convex set. For this case, an approximate polynomial algorithm based on linear programming theory is proposed.

KW - Learning from precedents

KW - Monotone constraints

KW - NP-hard problem

KW - Sample monotonization

UR - http://www.scopus.com/inward/record.url?scp=77955025004&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955025004&partnerID=8YFLogxK

U2 - 10.1134/S0965542510070146

DO - 10.1134/S0965542510070146

M3 - Article

VL - 50

SP - 1260

EP - 1266

JO - Computational Mathematics and Mathematical Physics

JF - Computational Mathematics and Mathematical Physics

SN - 0965-5425

IS - 7

ER -