근위 거리 알고리즘을 이용한 등위회귀함수 추정

Abstract

This paper deals with algorithms for solving the problem of estimating isotonic re- gression functions under partial order constraints. When the cost function is an error square function, this problem becomes a quadratic programming problem, and an effi- cient algorithm using a recursive division method is known. Although generalization has been proposed for the case where the cost function is an arbitrary differentiable con- vex function, there is an error in applying huber loss function, and it cannot applied to cost functions that can not be partially differentiated, such as an absolute loss function and a hinge loss function. In this paper, I show the problems of the generalized-isotonic- recursive-partitioning(GIRP) algorithm under the huber loss function, explain the cause of the problem, and present a range of applicable function space.Then, I propose an al- gorithm that can be applied to the loss functions that can not be solved by previous algorithms, through the proximity distance algorithm, which is a kind of the MM algo- rithm. In addition, the theoretical speeds of the two algorithms to be used in projecting the optimal solution of the upper bound function into a sequence constrained set in the implementation of the proximal distance algorithm are compared and the actual perfor- mance is presented through simulation. Finally, I demonstrate the results for estimating isotonic regression function on real data, under an absolute loss function and a huber loss function by using the proximal distance algorithm.

본 논문에서는 부분적인 순서 제약 조건하에서 등위회귀함수를 추정하는 문제를 푸는 알고리즘을 다룬다. 손실함수가 오차제곱함수일 경우, 이 문제는 이차계획법 문제가 되고 재귀적 분할법을 이용한 효율적인 알고리즘이 알려져 있다. 손실함수가 미분가능한 임의의 볼록함수인 경우에 대한 일반화도 제안되어 있으나, 실제 적용해본 결과, 후버 손실함수에서 오류가 발생하였고, 절대오차 손실함수나 힌지 손실함수와 같이 부분적으로 미분이 불가한 함수에 대해서는 적용하지 못하는 한계가 있었다. 이 논문에서는 먼저 일반화된 재귀적 분할 알고리즘이 후버 손실함수에서 발생하는 문제와 원인을 제시하고, 실제로 적용가능한 함 수의 범위를 제시하였다. 다음으로, 상계최소화법의 일종인 근위 거리 알고리즘을 통하여, 기존의 풀리지 않던 손실함수들에 대해서도 적용 가능한 알고리즘을 제안하였다. 더불어, 근위 거리 알고리즘 구현 과정에서 대리함수의 최적해를 순서 제약이 있는 집합으로 사영 시킬 때 사용될 2개 알고리즘의 이론상 속도를 비교하였고, 시뮬레이션을 통해 실제 성능을 제시하였다. 마지막으로, 절대오차 손실함수와 후버 손실함수하에서 근위 거리 알고리즘을 사용해 등위회귀함수를 추정하는 예를 제시하였다.