Implementation of GPAV (Generalized Pool-Adjacent Violators) algorithm.
(Burdakov et al., In: Di Pillo G, Roma M, editors. An O(n2) Algorithm for Isotonic Regression. Boston, MA: Springer US; 2006.
p. 25<U+2013>33. Available from: 10.1007/0-387-30065-1_3
gpav(Y, W = NULL, adj)vector of scores relative to a single example. Y must be a numeric named vector, where names
correspond to classes' names, i.e. nodes of the graph g (root node included).
vector of weight relative to a single example. If W=NULL (def.) it is assumed that
W is a unitary vector of the same length of the columns' number of the matrix S (root node included).
adjacency matrix of the graph which must be sparse, logical and upper triangular. Number of columns of adj must be
equal to the length of Y and W.
A list of 3 elements:
YFit: a named vector with the scores of the classes corrected according to the GPAV algorithm.
blocks: list of vectors, containing the partitioning of nodes (represented with an integer number) into blocks;
W: vector of weights.
Given the constraints adjacency matrix of the graph, a vector of scores \(\hat{y} \in R^n\) and a vector of strictly positive
weights \(w \in R^n\), the GPAV algorithm returns a vector \(\bar{y}\) which is as close as possible, in the least-squares sense,
to the response vector \(\hat{y}\) and whose components are partially ordered in accordance with the constraints matrix adj.
In other words, GPAV solves the following problem:
$$
\bar{y} = \left\{
\begin{array}{l}
\min \sum_{i \in V} (\hat{y}_i - \bar{y}_i )^2\\\\
\forall i, \quad j \in par(i) \Rightarrow \bar{y}_j \geq \bar{y}_i
\end{array}
\right.
$$
where \(V\) are the number of vertexes of the graph.
# NOT RUN {
data(graph);
data(scores);
Y <- S[3,];
adj <- adj.upper.tri(g);
Y.gpav <- gpav(Y,W=NULL,adj);
# }
Run the code above in your browser using DataLab