Showing posts with label Contraints. Show all posts
Showing posts with label Contraints. Show all posts

Sunday, December 5, 2010

SFF Trees for Cost-Sensitive Best M

John Langford sent me a helpful suggestion recently.
Another approach is to introduce a representational hack. Suppose we define our pairwise classifier as: $w_{left} x_{left} - w_{right} x_{right}$. Then, the output of the filter tree is $\underset{a}{\operatorname{arg\,max\,}} w_a x_a$, of an identical form to regression. However, we train things differently so as to achieve low regret $\ldots$
There are lots of directions to explore associated with this suggestion. Here are some meanderings of mine.

SFF Trees: Definition

I'm going to call this suggestion the Scoring Forfeit Filter (SFF) tree. The analogy is to when a scoring function is used to define a linear ordering for reduction of ranking to classification. Here's a more precise definition.
Definition:SFF Tree
An SFF tree is a forfeit filter tree $\Psi$ where at each internal node $\nu$ the importance-weighted classifier is of the form \[ \Psi_\nu (x) = 1_{f (x; \lambda) > f (x; \phi)}
\] where $\lambda$ and $\phi$ are the two classes input to $\nu$ (the predictions of the left and right subtrees respectively). The function $f$ is called the scoring function and is the same at each internal node (but different for each action).

What is cool about John's suggestion is that at test time the output of the SFF tree can be computed via $h^\Psi (x, \omega) = \underset{k \in K \setminus \omega}{\operatorname{arg\,max\,}} f (x; k)$ which looks just like how the output is computed for a regression reduction. However the regret bound is better, because the training procedure is different.

SFF Trees for Average Constrained CSMC

Since an SFF tree is a forfeit filter tree, the regret bound for Forfeit Filter trees on average constrained CSMC problems holds, namely \[ r_{av} (h^\Psi) \leq (|K| - 1) q (\Psi), \] where $q (\Psi)$ is the importance-weighted binary regret on the induced subproblem. This contrasts favorably to the regression regret bound, \[ r_{av} (h_g) \leq \sqrt{2 |K| \epsilon_{L^2} (g)}, \] where $\epsilon_{L^2} (g)$ is the $L^2$ loss on the underlying regression problem.

So this seems magical at first (i.e., can be viewed as a way to get a better regressor), but I intuit it as the training procedure focusing the subproblem oracle on problems that matter (e.g., distinguishing between best and $2^\mathrm{nd}$ best actions per instance) and ignoring problems that do not (e.g., accurately estimating the value of the $(n-1)^\mathrm{th}$ and $n^\mathrm{th}$ worst alternatives).

In practice, forcing the classifiers in the SFF tree to be based upon a scoring function might make it difficult to learn a low regret solution on the induced subproblem. The fact that the scoring function is shared at all the internal nodes is key to simplifying the output computation, but is different than the vanilla forfeit tree. In the vanilla case it is easy to envision training the tree in a bottom-to-top fashion via $\log_2 (|K|)$ sequential passes, each pass defining the training data for the next level of internal nodes, and each pass training a set of internal nodes at a particular depth. However, now the classifiers at the different levels are intertwined.

I'm not actually sure how to deal with this, and I won't know until I try something. Intuitively, if I were incrementally updating a warm model online, I'd try ignoring the dependency and just applying the updates. The motivation would be that I'm making tiny changes each update, so the stuff I'm ignoring is ``higher-order tiny''. Of course the massive nonlinearity at the decision boundary is a bit disturbing (and not very tiny). From a cold start but still using an online learning algorithm (on offline data), I'd try $\log_2 (|K|)$ passes in a bottom-to-top fashion, warm starting the entire tree at a certain depth before training any internal nodes at the next higher depth. Unlike in the vanilla case, each pass would train all internal nodes up to a certain depth, rather than just the internal nodes at a particular depth. Hopefully that works, but if it fails miserably I'd look into softening the nonlinearity at the decision boundary with a softmax-style approach, e.g., $p (\Psi_\nu = 1 | x) = 1 / (1 + e^{-\beta (f (x; \lambda) - f (x; \psi))})$ and anneal $\beta$ to $\infty$.

SFF Tree for Average Constrained CSBM

Average constrained CSBM is the problem of picking the top-$m$ actions given an instance. It can be reduced to average constrained CSMC by constructing a list of classifiers $\{\Psi_n | n \in [1, m]\}$ each of which is trained to select the best action, the next best action, etc.

So here's something interesting: if we set $\Psi_n = \Psi$ in the list of classifiers, and if our average constrained CSMC classifier is an SFF tree, then we can compute the CSBM output via \[ h^\Psi (x, \omega) = \underset{k \in K \setminus \omega}{\operatorname{arg\,max\,^m}} f (x; k), \] where I made up the notation $\operatorname{arg\,max\,^m}$ to stand for selecting the top $m$ elements. Once again this is exactly how a regression reduction based approach would be utilized at test time. However again the regret bounds are different. When reducing average constrained CSBM to average constrained CSMC the regret bound is \[ r_{csbm} (h^\Psi) \leq m\, q (\Psi, m), \] where $q (\Psi, m)$ is the cost-sensitive regret averaged over the $m$ average constrained CSMC subproblems (these can, in turn, be reduced to importance-weighted classification maintaining a linear dependence on the regret). By contrast, when reducing to regression the regret bound is \[ r_{csbm} (h_g) \leq \sqrt{2 \min \{m, |K| -m\}} \sqrt{|K|} \sqrt{\epsilon_{L^2} (g)}, \] where $\epsilon_{L^2} (g)$ is the $L^2$ loss on the underlying regression problem.

So again we have the promise of a different training procedure leading to a better regressor, but with similar problems of dependencies between subproblems complicating the training picture. In the vanilla case of reduction of CSBM to CSMC, each classifier is trained sequentially and defines the training input distribution for the next classifier. Now all the classifiers are the same so some tricks are required.

Again, I'm not actually sure how to deal with this, and I won't know until I try something. Intuitively I would again try incrementally updating a warm model online, ignoring the dependency. For cold start with an online model applied to an offline data set I would first train for the top-1 problem, then the top-2 problem, etc. until I got to top-$m$. It's interesting to see how the composition of my two intuitive procedures would play out for a complete cold start:
  1. For $n$ in $[1, m]$
    1. For $l$ in $[\log_2 (|K|), 1]$
      1. Update the $l^\mathrm{th}$ and lower levels of internal nodes on the problem of picking the top-$n$ actions, and simultaneously
      2. Update the $l^\mathrm{th}+1$ and higher levels of internal nodes on the problem of picking the top-$(n-1)$ actions.
That's a total of $m \log_2 (|K|)$ passes over the data, which feels reasonable. The outer loop is to mitigate the dependencies created by $\Psi_n = \Psi$, and the inner loop is to mitigate the dependencies created by sharing $f$ across all internal nodes.

Now I suppose I should try this on some actual data.

Wednesday, September 15, 2010

Constrained Cost-Sensitive Best M with Partial Feedback

In a previous post I talked about constrained cost-sensitive best m (CSBM) and one way to reduce to constrained cost-sensitive multiclass classification (CSMC). CSBM is about choosing the best set of choices when the rewards of a set is the sum of the rewards of the elements, and the reduction to CSMC works by ``pick the best choice, then the next best choice, and so on''. Since then I've played with the offset tree, which is designed for problems where the historical data contains partial feedback (i.e., rewards are only revealed for actions taken). Now it's time for a mash-up, namely constrained CSBM with partial feedback.

The constrained CSBM definition is as follows. There is a distribution $D = D_x \times D_{\omega|x} \times D_{r|\omega,x}$, where $r: A \to [0, 1] \cup \{ -\infty \}$ takes values in the unit interval augmented with $-\infty$, and the components of $r$ which are $-\infty$-valued for a particular instance are revealed as part of the problem instance via $\omega \in \mathcal{P} (A)$ (i.e., $\omega$ is a subset of $A$). Allowed outputs in response to a problem instance are subsets of $A$ of size $m$, denoted \[ S_m = \{ S | S \subseteq A, |S| = m \}.\] The regret of a particular deterministic policy $h: X \times \mathcal{P} (A) \to S_m$ is given by \[ v (h) = E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ \max_{s \in S_m}\; E_{r \sim D_{r|\omega,x}} \left[ \sum_{a \in s} r (a) \right] - E_{r \sim D_{r|\omega,x}} \left[ \sum_{a \in h (x, \omega)} r (a) \right] \right]. \] Note when $|A \setminus \omega| < m$, any strategy achieves zero regret (via $-\infty$ reward); therefore the ``interesting'' parts of the problem space are when $|A \setminus \omega| \geq m$.

There are two plausible scenarios for CSBM with partial feedback.
  1. Only the total reward associated with the set of actions chosen is observed. There is actually a version of this problem at my current gig, since there is a page on the site whose elements are designed to act in concert to elicit a single response.
  2. The reward associated with each action chosen is observed. For instance advertisements are generally chosen in a set, but provide individualized feedback.
Well I'd like to understand the first case, but I need to build some intuition so I'll focus on the second (easier) case. I'll assume that the historical policy is using a known conditional distribution over the power set of actions given an instance $p (\mathcal{A} | x, \omega)$. I'll use the shorthand $\mathcal{A}$ to refer to realizations from $\mathcal{P} (A)$.

The reduction works as follows: first the highest reward choice is chosen, then its reward is adjusted to $-\infty$, and the process is repeated until a set of size $m$ has been achieved. The individual steps are posed as constrained CSMC with partial feedback (CSMC-PF) problems, which is essentially CSBM with $m = 1$. The forfeit filter-offset tree was designed for constrained CSMC-PF, and in particular can be used as the $\mbox{Learn}$ oracle below. The forfeit filter-offset tree has the property that it always achieves finite regret, i.e., it chooses a feasible class whenever possible. In this context, it means the subproblems will never create duplicates.
Algorithm:Partial Feedback Set Select Train
Input: Action labels $A$, (maximum) size of set to select $m \leq |A| / 2$.
Input: Constrained CSMC-PF classifier $\mbox{Learn}$.
Data: Training data set $S$.
Result: Trained classifiers $\{\Psi_n | n \in [1, m] \}$.
  1. Define $\gamma_0 (\cdot, \cdot) = \emptyset$.
  2. For each $n$ from 1 to $m$:
    1. $S_n = \emptyset$.
    2. For each example $\bigl(x, \omega, \mathcal{A}, \{ r (a) | a \in \mathcal{A} \}, p (\cdot | x, \omega) \bigr) \in S$ such that $|A \setminus \omega| \geq m$:
      1. Let $\gamma_{n-1} (x, \omega)$ be the predicted best set from the previous iteration.
      2. For each action $a$:
        1. If $a \in \gamma_{n-1} (x, \omega)$, $r (n, a) = -\infty$;
        2. else $r (n, a) = r (a)$.
      3. $S_n \leftarrow S_n \cup \left\{\bigl( x, \omega \cup \gamma_{n-1} (x), \mathcal{A}, \{ r (n, a) | a \in \mathcal{A} \}, p (\cdot | x, \omega) \bigr) \right\}$.
    3. Let $\Psi_n = \mbox{Learn} (S_n)$.
    4. Let $\gamma_n (x) = \Psi_n (x) \cup \gamma_{n-1} (x)$.
  3. Return $\{ \Psi_n | n \in [1, m] \}$.
Comment: If $m > |A|/2$, negate all finite rewards and choose complement of size $|A| - m$.
Algorithm:Set Select Test
Data: Class labels $A$, number of positions to populate $l \leq m \leq |A|/2$.
Data: Instance feature realization $(x, \omega)$.
Data: Trained classifiers $\{\Psi_n | n \in [1, m] \}$.
Result: Set $h^\Psi: X \to S_l$.
  1. $\gamma_0^\Psi (x, \omega) = \emptyset$.
  2. For $n$ from 1 to $l$:
    1. $\gamma_n^\Psi (x, \omega) = \gamma_{n-1}^\Psi (x, \omega) \cup \Psi_n (x, \omega \cup \gamma_{n-1}^\Psi (x, \omega))$.
  3. If $|\gamma_l^\Psi (x, \omega)| = l$, $h^\Psi (x, \omega) = \gamma_l^\Psi (x, \omega)$;
  4. else set $h^\Psi (x, \omega)$ to an arbitrary element of $S_l$.
Comment: If $l \geq m > |A|/2$, negate all finite costs, and choose complement of size $|A| - l$.
The Partial Feedback Set Select Train algorithm ignores training data where $|A \setminus \omega| < m$, but for such an input any strategy achieves negative infinite reward and zero regret, so learning is pointless. Similarly, the Set Select Test algorithm is not defined when $|A \setminus \omega| < l \leq m$, but for such an input any strategy achieves negative infinite reward and zero regret, so for the purposes of subsequent analysis I'll suppose that we pick an arbitrary element in $S_l$.

My goal is to bound the average constrained CSBM regret \[ v (h) = E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ \max_{s \in S_m}\; E_{r \sim D_{r|\omega,x}} \left[ \sum_{a \in s} r (a) \right] - E_{r \sim D_{r|\omega,x}} \left[ \sum_{a \in h (x, \omega)} r (a) \right] \right] \] in terms of the average constrained CSMC regret on the induced subproblems. Once again I'll leverage a trick from the filter tree derivation and collapse the multiple subproblems into a single subproblem by defining an induced distribution. Let $D$ be the distribution of average constrained CSBM instances $(x, \omega, r)$. Define the induced distribution $D^\prime (\Psi, l)$ where $l \leq m$ of constrained CSMC-PF instances $(x^\prime, \omega^\prime, \mathcal{A}, \{ r^\prime (a) | a \in \mathcal{A} \}, p^\prime (\cdot | x^\prime, \omega^\prime))$.
  1. Draw $(x, \omega, r)$ from $D$.
  2. Draw $n$ uniform on $[1, l]$.
  3. Let $x^\prime = (x, n)$.
  4. Let $\omega^\prime = \omega \cup \gamma_{n-1} (x, \omega)$.
  5. For each action $a$:
    1. If $a \in \gamma_{n-1} (x, \omega)$, $r^\prime (a) = -\infty$;
    2. else $r^\prime (a) = r (a)$.
  6. Let $p^\prime (\cdot | x^\prime, \omega^\prime) = p (\cdot | x, \omega)$.
  7. Create constrained CSMC-PF example $(x^\prime, \omega^\prime, \mathcal{A}, \{ r^\prime (a) | a \in \mathcal{A} \}, p^\prime (\cdot | x^\prime, \omega^\prime))$.
Note $D^\prime (\Psi, l)$ depends upon the classifier via the duplicate penalty, but for any fixed classifier is well defined. Ultimately I'd like to relate the average constrained CSBM regret $v (h^\Psi)$ to the induced CSMC regret \[ \begin{aligned} q (\Psi, l) &= E_{(x^\prime, \omega^\prime) \sim D^\prime_{x^\prime, \omega^\prime} (\Psi, l) } \left[ \max_{a \in A}\; E_{r^\prime \sim D^\prime_{r^\prime|\omega^\prime,x^\prime} (\Psi, l)} \left[ r (a) \right] - E_{r^\prime \sim D^\prime_{r^\prime|\omega^\prime,x^\prime} (\Psi, l)} \left[ r ({\Psi (x^\prime, \omega^\prime)}) \right] \right] \\ &= \frac{1}{l} \sum_{n=1}^l q_n (\Psi), \end{aligned} \] where \[ \begin{aligned} q_n (\Psi) &= E_{(x, \omega) \sim D_{x,\omega}} [ q_n (\Psi | x, \omega) ], \\ q_n (\Psi | x, \omega) &= \max_{a \in A}\; E_{r \sim D_{r|\omega,x}} \left[ \tilde r_n (a) \right] - E_{r \sim D_{r|\omega,x}} \left[ \tilde r_n \bigl(\Psi_n (x, \gamma_{n-1} (x, \omega)) \bigr) \right], \\ \tilde r_n (a) &= \begin{cases} -\infty & \mbox{if } a \in\gamma_{n-1} (x, \omega); \\ r (a) & \mbox{otherwise}. \end{cases} \end{aligned} \]
Theorem:Regret Bound
For all average constrained CSBM distributions $D$, and all average constrained CSMC classifiers $\Psi$, \[ v (h^\Psi) \leq l\, q (\Psi, l). \] Proof: See Appendix.
The historical policy $p$ does not enter into this theorem, because it is passed as a ``black box'' into the CSMC-PF subproblems. Of course when using the forfeit filter-offset tree for the subproblems, in order to bound the subproblem regret in terms of the regret of the induced importance-weighted binary regret on the sub-subproblem, the historical policy has to obey $E_{\mathcal{A} \sim p} [ 1_{a \in \mathcal{A}} | x, \omega ] > 0$ whenever $a \not \in \omega$.

The remarks from the previous version of this reduction still apply.

The reduction still seems inefficient when comparing reduction to regression directly ($\sqrt{m} \sqrt{|A|} \sqrt{\epsilon_{L^2}}$) versus reduction to regression via CSMC ($m \sqrt{|A|} \sqrt{\epsilon_{L^2}}$). This suggests there is a way to reduce this problem which only leverages $\sqrt{m}$ CSMC subproblems. One possible source of inefficiency: the reduction is retrieving the elements in order, whereas the objective function is indifferent to order.

The regret bound indicates the following property: once I have trained to select sets of size $m$, I can get a regret bound for selecting sets of size $l$ for any $l \leq m$. This suggests a variant with $m = |A|$ could be used to reduce minimax constrained CSMC-PF to average constrained CSMC-PF. I'll explore that in a future blog post.

Appendix


This is the proof of the regret bound.

If $\Psi$ achieves infinite regret on the induced subproblem, the bound holds trivially. Thus consider a $\Psi$ that achieves finite regret.

If $|A \setminus \omega| < l$, then $v = 0$ for any choice in $S_l$, and the bound conditionally holds trivially. Thus consider $|A \setminus \omega| \geq l$: since $\Psi$ achieves finite regret no duplicates are generated from any sub-classifier and $h^\Psi (x, \omega) = \gamma^\Psi_l (x, \omega)$.

Consider a fixed $(x, \omega)$ with $|A \setminus \omega| \geq l$. It is convenient to talk about \[ v (h | x, \omega, n) = \max_{s \in S_m}\; E_{r \sim D_{r|\omega,x}} \left[ \sum_{a \in s} r (a) \right] - E_{r \sim D_{r|\omega,x}} \left[ \sum_{a \in \gamma^\Psi_n (x, \omega)} r (a) \right], \] the conditional regret on this instance at the $n^\mathrm{th}$ step in Partial Feedback Set Select Test. Let \[ s^* (x, \omega, n) = \underset{s \in S_m}{\operatorname{arg\,max\,}} E_{r \sim D_{r|\omega,x}} \left[ \sum_{a \in s} r (a) \right] \] be any maximizer of the first term (which is unique up to ties); note any $s^* (x, \omega, n)$ will select $n$ classes with respect to largest conditional expected reward.

Proof is by demonstrating the property $v (h^\Psi | x, \omega, n) \leq \sum_{r=1}^n q_r (\Psi, l)$. The property holds with equality for $n = 1$. For $n > 1$ note \[ \begin{aligned} v (h^\Psi | x, \omega, n) - v (h^\Psi | x, \omega, n - 1) &= \max_{a \in A \setminus s^* (x, \omega, n - 1)} E_{r \sim D_{r|\omega,x}} \left[ r (a) \right] \\ &\quad - E_{r \sim D_{r|\omega,x}} \left[ r \left(\Psi_n \left(x, \omega \cup \gamma^\Psi_{n-1} (x, \omega) \right) \right) \right], \\ &\leq \max_{a \in A \setminus \gamma^\Psi_{n-1} (x, \omega)} E_{r \sim D_{r|\omega,x}} \left[ r (a) \right] \\ &\quad - E_{r \sim D_{r|\omega,x}} \left[ r \left(\Psi_n \left(x, \omega \cup \gamma^\Psi_{n-1} (x, \omega) \right) \right) \right], \\\ &\leq \max_{a \in A \setminus \gamma^\Psi_{n-1} (x, \omega)} E_{r \sim D_{r|\omega,x}} \left[ \tilde r_n (a) \right] \\ &\quad - E_{r \sim D_{r|\omega,x}} \left[ \tilde r_n \left(\Psi_n \left(x, \omega \cup \gamma^\Psi_{n-1} (x, \omega) \right) \right) \right], \\ &= q_n (\Psi, l | x, \omega), \end{aligned} \] where the second inequality is due to the optimality of $s^* (x, \omega, n - 1)$ and the third inequality is because $\tilde r_n (a) \leq r (a)$ with equality if $a \not \in \gamma^\Psi_{n-1} (x, \omega)$. Summing the telescoping series establishes \[ v (h^\Psi | x, \omega) = v (h^\Psi | x, \omega, l) \leq \sum_{r=1}^l q_r (\Psi, l | x, \omega) = l\, q (\Psi, l | x, \omega). \] Taking the expectation with respect to $D_{x, \omega}$ completes the proof.

Wednesday, September 8, 2010

Constrained Best M: Reduction to Constrained CSMC

In a previous post I talked about the Ad Selection Problem, which I now prefer to call cost-sensitive best m (CSBM), since actual ad selection is vastly more complicated. CSBM is akin to cost-sensitive multiclass classification (CSMC) where $m$ unique classes have to chosen and the goal is to minimize the total cost. In that previous I reduced CSBM to CSMC, but the reduction was a bit tortured: first, the costs all had to bounded above by a constant; second, the algorithm could possibly generate duplicates anyway and so a randomization step was included to enforce feasibility; and third the analysis was cluttered with the implications of the randomization step.

Since then I introduced constrained CSMC, which is like vanilla CSMC but with some of the classes forbidden as part of the instance specification. Constrained CSMC was designed with the goal of simplifying the CSBM reduction, but it does slightly more. It actually allows me to define a reduction from average constrained CSBM to average constrained CSMC, and since CSBM is a special case of average constrained CSBM, this accomplishes my original goal plus a bonus.

The average constrained CSBM definition is as follows. There is a distribution $D = D_x \times D_{\omega|x} \times D_{c|\omega,x}$, where $c: K \to \mathbf{R}$ takes values in the extended reals $\mathbf{R} = \mathbb{R} \cup \{ \infty \}$, and the components of $c$ which are $\infty$-valued for a particular instance are revealed as part of the problem instance via $\omega \in \mathcal{P} (K)$ (i.e., $\omega$ is a subset of $K$). Allowed outputs in response to a problem instance are subsets of $K$ of size $m$, denoted \[ S_m = \{ S | S \subseteq K, |S| = m \}.\] The regret of a particular classifier $h: X \times \mathcal{P} (K) \to S_m$ is given by \[ r_{csbm} (h) = E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ E_{c \sim D_{c|\omega,x}} \left[ \sum_{k \in h (x, \omega)} c (k) \right] - \min_{h \in S_m}\, E_{c \sim D_{c|\omega,x}} \left[ \sum_{k \in h} c (k) \right] \right]. \] Note when $|K \setminus \omega| < m$, any strategy achieves zero regret (via $\infty$ cost); therefore the ``interesting'' parts of the problem space are when $|K \setminus \omega| \geq m$.

The reduction takes an average constrained CSBM problem and converts it into a set of average constrained CSMC problems. The average constrained CSMC definition is as follows. There is a distribution $D = D_x \times D_{\omega|x} \times D_{c|\omega,x}$, where $c: K \to \mathbf{R}$ takes values in the extended reals $\mathbf{R} = \mathbb{R} \cup \{ \infty \}$, and the components of $c$ which are $\infty$-valued for a particular instance are revealed as part of the problem instance via $\omega \in \mathcal{P} (K)$ (i.e., $\omega$ is a subset of $K$). The regret of a particular classifier $h: X \times \mathcal{P} (K) \to K$ is given by \[ r_{av} (h) = E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ E_{c \sim D_{c|\omega,x}} \left[ c (h (x, \omega)) - \min_{k \in K}\, E_{c \sim D_{c|\omega,x}} \left[ c (k) \right] \right] \right]. \] Average constrained CSMC can be attacked using variants of reductions designed for unconstrained CSMC, such as argmax regression or the filter tree. These reductions have the property that they always achieve finite regret, i.e., they choose a feasible class whenever possible. In this context, it means the subproblems will never create duplicates.

The reduction works as follows: first the lowest cost choice is chosen, then its cost is adjusted to $\infty$, and the process is repeated until a set of size $m$ has been achieved. It is basically the same reduction as presented in a previous post, but reducing to average constrained CSMC instead of unconstrained CSMC leads to some advantages: costs need not be bounded above and feasibility is naturally enforced.

Algorithm:Set Select Train
Input: Class labels $K$, (maximum) size of set to select $m \leq |K| / 2$.
Input: Average constrained CSMC classifier $\mbox{Learn}$.
Data: Training data set $S$.
Result: Trained classifiers $\{\Psi_n | n \in [1, m] \}$.
  1. Define $\gamma_0 (\cdot, \cdot) = \emptyset$.
  2. For each $n$ from 1 to $m$:
    1. $S_n = \emptyset$.
    2. For each example $(x, \omega, c) \in S$ such that $|K \setminus \omega| \geq m$:
      1. Let $\gamma_{n-1} (x, \omega)$ be the predicted best set from the previous iteration.
      2. For each class $k$:
        1. If $k \in \gamma_{n-1} (x, \omega)$, $c (n, k) = \infty$;
        2. else $c (n, k) = c (k)$.
      3. $S_n \leftarrow S_n \cup \left\{\bigl( x, \omega \cup \gamma_{n-1} (x), c (n, \cdot) \bigr) \right\}$.
    3. Let $\Psi_n = \mbox{Learn} (S_n)$.
    4. Let $\gamma_n (x) = \Psi_n (x) \cup \gamma_{n-1} (x)$.
  3. Return $\{ \Psi_n | n \in [1, m] \}$.
Comment: If $m > |K|/2$, negate all finite costs and choose complement of size $|K| - m$.

Algorithm:Set Select Test
Data: Class labels $K$, number of positions to populate $l \leq m \leq |K|/2$.
Data: Instance feature realization $(x, \omega)$.
Data: Trained classifiers $\{\Psi_n | n \in [1, m] \}$.
Result: Set $h^\Psi: X \to S_l$.
  1. $\gamma_0^\Psi (x, \omega) = \emptyset$.
  2. For $n$ from 1 to $l$:
    1. $\gamma_n^\Psi (x, \omega) = \gamma_{n-1}^\Psi (x, \omega) \cup \Psi_n (x, \omega \cup \gamma_{n-1}^\Psi (x, \omega))$.
  3. If $|\gamma_l^\Psi (x, \omega)| = l$, $h^\Psi (x, \omega) = \gamma_l^\Psi (x, \omega)$;
  4. else set $h^\Psi (x, \omega)$ to an arbitrary element of $S_l$.
Comment: If $l \geq m > |K|/2$, negate all finite costs, and choose complement of size $|K| - l$.

The Set Select Train algorithm ignores training data where $|K \setminus \omega| < m$, but for such an input any strategy achieves infinite cost and zero regret, so learning is pointless. Similarly, the Set Select Test algorithm is not defined when $|K \setminus \omega| < l \leq m$, but for such an input any strategy achieves infinite cost and zero regret, so for the purposes of subsequent analysis I'll suppose that we pick an arbitrary element in $S_l$.

My goal is to bound the average constrained CSBM regret \[ r_{csbm} (h) = E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ E_{c \sim D_{c|\omega,x}} \left[ \sum_{k \in h (x, \omega)} c (k) \right] - \min_{h \in S_m}\, E_{c \sim D_{c|\omega,x}} \left[ \sum_{k \in h} c (k) \right] \right] \] in terms of the average constrained CSMC regret on the induced subproblems. Once again I'll leverage a trick from the filter tree derivation and collapse the multiple subproblems into a single subproblem by defining an induced distribution. Let $D$ be the distribution of average constrained CSBM instances $(x, \omega, c)$. Define the induced distribution $D^\prime (\Psi, l)$ where $l \leq m$ of average constrained CSMC instances $(x^\prime, \omega^\prime, c^\prime)$ as follows:
  1. Draw $(x, \omega, c)$ from $D$.
  2. Draw $n$ uniform on $[1, l]$.
  3. Let $x^\prime = (x, n)$.
  4. Let $\omega^\prime = \omega \cup \gamma_{n-1} (x, \omega)$.
  5. For each class $k$:
    1. If $k \in \gamma_{n-1} (x, \omega)$, $c^\prime (k) = \infty$;
    2. else $c^\prime (k) = c (k)$.
  6. Create cost-sensitive example $(x^\prime, \omega^\prime, c^\prime)$.
Note $D^\prime (\Psi, l)$ depends upon the classifier via the duplicate penalty, but for any fixed classifier is well defined. Ultimately I'd like to relate the average constrained CSBM regret $r_{csbm} (h^\Psi)$ to the induced cost-sensitive regret \[ \begin{aligned} q (\Psi, l) &= E_{(x^\prime, \omega^\prime) \sim D^\prime_{x^\prime, \omega^\prime} (\Psi, l) } \left[ E_{c^\prime \sim D^\prime_{c^\prime|\omega^\prime,x^\prime} (\Psi, l)} \left[ c ({\Psi (x^\prime, \omega^\prime)}) \right] - \min_{k \in K}\, E_{c^\prime \sim D^\prime_{c^\prime|\omega^\prime,x^\prime} (\Psi, l)} \left[ c (k) \right] \right] \\ &= \frac{1}{l} \sum_{n=1}^l q_n (\Psi), \end{aligned} \] where \[ \begin{aligned} q_n (\Psi) &= E_{(x, \omega) \sim D_{x,\omega}} [ q_n (\Psi | x, \omega) ], \\ q_n (\Psi | x, \omega) &= E_{c \sim D_{c|\omega,x}} \left[ \tilde c_n \bigl(\Psi_n (x, \gamma_{n-1} (x, \omega)) \bigr) \right] - \min_{k \in K}\, E_{c \sim D_{c|\omega,x}} \left[ \tilde c_n (k) \right] \\ \tilde c_n (k) &= \begin{cases} \infty & \mbox{if } k \in \gamma_{n-1} (x, \omega); \\ c (k) & \mbox{otherwise}. \end{cases} \end{aligned} \]
Theorem:Regret Bound
For all average constrained CSBM distributions $D$ and average constrained CMSC classifiers $\Psi$, \[ r_{csbm} (h^\Psi) \leq l\, q (\Psi, l). \] Proof: See appendix.
Some of the remarks from the previous version of this reduction still apply, and others do not.

The reduction still seems inefficient when comparing reduction to regression directly ($\sqrt{m} \sqrt{|K|} \sqrt{\epsilon_{L^2}}$) versus reduction to regression via CSMC ($m \sqrt{|K|} \sqrt{\epsilon_{L^2}}$). This suggests there is a way to reduce this problem which only leverages $\sqrt{m}$ CSMC subproblems. One possible source of inefficiency: the reduction is retrieving the elements in order, whereas the objective function is indifferent to order.

The regret bound indicates the following property: once I have trained to select sets of size $m$, I can get a regret bound for selecting sets of size $l$ for any $l \leq m$. This suggests a variant with $m = |K|$ could be used to reduce minimax constrained CSMC to average constrained CSMC. I'll explore that in a future blog post.


Appendix

This is the proof of the regret bound.

If $\Psi$ achieves infinite regret on the induced subproblem, the bound holds trivially. Thus consider a $\Psi$ that achieves finite regret.

If $|K \setminus \omega| < l$, then $r_{csbm} = 0$ for any choice in $S_l$, and the bound conditionally holds trivially. Thus consider $|K \setminus \omega| \geq l$: since $\Psi$ achieves finite regret no duplicates are generated from any sub-classifier and $h^\Psi (x, \omega) = \gamma^\Psi_l (x, \omega)$.

Consider a fixed $(x, \omega)$ with $|K \setminus \omega| \geq l$. It is convenient to talk about \[ r_{csbm} (h^\Psi | x, \omega, n) = E_{c \sim D_{c|\omega,x}} \left[ \sum_{k \in \gamma^\Psi_n (x, \omega)} c (k) \right] - \min_{h \in S_n}\, E_{c \sim D_{c|\omega,x}} \left[ \sum_{k \in h} c (k) \right], \] the conditional regret on this instance at the $n^\mathrm{th}$ step in Set Select Test. Let \[ h^* (x, \omega, n) = \underset{h \in S_n}{\operatorname{arg\,min\,}} E_{c \sim D_{c|\omega,x}} \left[ \sum_{k \in h} c (k) \right] \] be any minimizer of the second term (which is unique up to ties); note any $h^* (x, \omega, n)$ will select $n$ classes with respect to smallest conditional expected cost.

Proof is by demonstrating the property $r_{csbm} (h^\Psi | x, \omega, n) \leq \sum_{r=1}^n q_r (\Psi, l)$. The property holds with equality for $n = 1$. For $n > 1$ note \[ \begin{aligned} r_{csbm} (h^\Psi | x, \omega, n) - r_{csbm} (h^\Psi | x, \omega, n - 1) &= E_{c \sim D_{c|\omega,x}} \left[ c (\Psi_n (x, \omega \cup \gamma^\Psi_{n-1} (x, \omega))) \right] \\ &\quad - \min_{k \in K \setminus h^* (x, \omega, n - 1)} E_{c \sim D_{c|\omega,x}} \left[ c (k) \right] \\ &\leq E_{c \sim D_{c|\omega,x}} \left[ c (\Psi_n (x, \omega \cup \gamma^\Psi_{n-1} (x, \omega))) \right] \\ &\quad - \min_{k \in K \setminus \gamma^\Psi_{n-1} (x, \omega)} E_{c \sim D_{c|\omega,x}} \left[ c (k) \right] \\ &\leq E_{c \sim D_{c|\omega,x}} \left[ \tilde c_n (\Psi_n (x, \omega \cup \gamma^\Psi_{n-1} (x, \omega))) \right] \\ &\quad - \min_{k \in K \setminus \gamma^\Psi_{n-1} (x, \omega)} E_{c \sim D_{c|\omega,x}} \left[ \tilde c_n (k) \right] \\ &= q_n (\Psi, l | x, \omega), \end{aligned} \] where the second inequality is due to the optimality of $h^* (x, \omega, n - 1)$ and the third inequality is because $\tilde c_n (k) \geq c (k)$ with equality if $k \not \in \gamma^\Psi_{n-1} (x, \omega)$. Summing the telescoping series establishes \[ r_{csbm} (h^\Psi | x, \omega) = r_{csbm} (h^\Psi | x, \omega, l) \leq \sum_{r=1}^l q_r (\Psi, l | x, \omega) = l\, q (\Psi, l | x, \omega). \] Taking the expectation with respect to $D_{x, \omega}$ completes the proof.