0
$\begingroup$

How would you learn a function with the emphasis on feature interactions?

I have the standard assignment problem:

$$ \max_{x_{ij}} \sum_{(i, j)} w_{ij} x_{ij}, $$

where $w_{ij}$ is the weight of the edge between $i \in A$ and $j \in B$ and $x_{ij} \in \{0, 1\}$ s. t. $\sum_i x_{ij} = 1 \ \forall j $ and $\sum_j x_{ij} = 1 \ \forall i$. And the equal number of persons and objects, $|A| = |B|$.

The weights are random variables and I'm estimating $w_{ij}$ from the historical data.

The data for any particular $(i, j)$ is not available. Instead, for every element $i \in A$ and $j \in B$, I have independent variables $\textbf{x}_i$ and $\textbf{x}_j$ that define these elements. The historical weights are the function of these vectors as well: $w(k, l) = f(\textbf{x}_k, \textbf{x}_l)$ for some elements $k \in A_H, l \in B_H$.

Now, I can estimate $\hat{f}$ and get $\hat{w}$ for the current pairs $(i, j)$.

Suppose the underlying process is just a sum $w(i, j) = f_A(\textbf{x}_i) + f_B(\textbf{x}_j)$. Then $\hat{w}(i, j) = c_i + c_j$ and $\sum_{(i, j)} \hat{w}_{ij} x_{ij}$ is a constant that does not depend on the constrained $x_{ij}$.

The optimal assignment makes sense if the process involves interactions between $i$ and $j$ and the estimator captures them. Something like $w(i, j) = f_A(\textbf{x}_i) + f_I(\textbf{x}_i, \textbf{x}_j) + f_B(\textbf{x}_j)$.

For that matter, the assignment problem needs only $f_I(\textbf{x}_i, \textbf{x}_j)$. But it is unclear how to reduce the error rates of this particular part. I looked into tree-based methods:

  • Adding interactions manually help GBM packages pick the interactions that work, but this approach requires manual input for every model, or the number of features grows exponentially.
  • Non-greedy split finding algorithms find some interactions, but I'm not familiar with their limitations.

The best strategy seems to be this (GBRT-based):

  1. Learn $f_A(\textbf{x}_i) + f_B(\textbf{x}_j)$ with original features by greedy algorithms and boosting.
  2. Add standard interactions between features and learn $f_A(\textbf{x}_i) + f_I(\textbf{x}_i, \textbf{x}_j) + f_B(\textbf{x}_j)$.
  3. Find the difference between error rates in (1) and (2) to measure the variance related to interactions and contribution of $f_I$ to the weights.
  4. Solve the assignment problem. Get the optimal total value $V^*$.
  5. Compare $V^*$ in (4) with the value under random assignment $E[V_R]$ and errors in (3). This gives the approximate benefits of the optimal assignment.

I still don't have the explicit $\hat{f}_I$ this way, but it seems possible to calculate the values it returns.

Do you know better ways of learning weights for assignment problems?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.