|
Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, 2010, Volume 50, Number 7, Pages 1327–1333
(Mi zvmmf4912)
|
|
|
|
On the sample monotonization problem
R. S. Takhanov Dorodnicyn Computing Center, Russian Academy of Sciences, ul. Vavilova 40, Moscow, 119991 Russia
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.
Key words:
monotone constraints, sample monotonization, learning from precedents, NP-hard problem.
Received: 26.01.2009
Citation:
R. S. Takhanov, “On the sample monotonization problem”, Zh. Vychisl. Mat. Mat. Fiz., 50:7 (2010), 1327–1333; Comput. Math. Math. Phys., 50:7 (2010), 1260–1266
Linking options:
https://www.mathnet.ru/eng/zvmmf4912 https://www.mathnet.ru/eng/zvmmf/v50/i7/p1327
|
Statistics & downloads: |
Abstract page: | 284 | Full-text PDF : | 102 | References: | 42 | First page: | 16 |
|