2
$\begingroup$

For each observations there are 207 variables (binary, either a 'symptom' happened or not), class variable is also binary.

For each variable or symptom there is a weight attached (currently set manually to be between -5 and 50) and for each observation there is a critical line (there are 3 different critical lines). Matrix of dummy variables is multiplied by weights and resulting matrix is added up across different columns for each observations resulting in some score. If this score is higher then particular critical line associated with observation then prediction is 1, otherwise is 0.

The problem is to set up those weights and critical lines optimally. I obviously have a data set to see which symptoms usually correspond to '1' in prediction.

For me it looks like an optimization problem but obviously the prediction itself can be made with machine learning but I am looking for another resource.

Question is: do you guys know any areas of OR or can point out me some keywords to look at on how this type of problems are solved? I am good with Python so if you want to recommend me some packages I am more then happy. The only thing I though about is to randomly generate weights in (-5, 50) interval and for loads of trials maybe I will find ones that correspond to best accuracy (point is to minimize false positives).

Thank you!

-EDIT 20.07

My current formulation is as follows:

max( sum over N (t_i * s_i)) st.

(M x')_i >= L_i then s_i = 1

(M x')_i < L_i then s_i = 0

sum over N(s_i) =< 0.06N

where N is the number of observation, M number of variables x is a vector of weights, M is a NxM matrix of dummy variables where each row represents one observation therefore Mx' results in a Nx1 vector of cumulative weights for each observation.

As I mentioned in the comment, optimal cut-off line L = [L_1, ..., L_n] is also a part of the problem. Vector of true allocations t is known. The point is that once I got cut-off lines and weights, the system would process new observations using them.

I also don't want to many positive s_i and this is another constrain of the problem.

Thank you for all comments, I am new to stack exchange so please bear with me.

Blockquote

$\endgroup$
3
  • $\begingroup$ You say you have three different cutoffs ("critical lines") for predicting a 1. What determines which cutoff each observation gets, and why are there three cutoff values (versus one, or five, or 10)? $\endgroup$
    – prubin
    Jul 18, 2020 at 19:23
  • $\begingroup$ Oh yeah, I completely forgot about mentioning this part. For each observation, I know which group it falls into (one of three groups), but the exact cut-off lines are also a part of the problem. I need to set optimal weights and cut-off lines. $\endgroup$
    – samiczy
    Jul 20, 2020 at 7:26
  • $\begingroup$ Is the idea to predict which group a new observation falls into (so that there should be exactly one group where the prediction exceeds the cutoff), or are you trying to predict something else (say, whether the subject has a particular disease) for subjects coming from multiple groups? If the latter, are you constrained to use the same function coefficients for all groups (and just vary the cutoffs), or can you fit different coefficients to different groups? $\endgroup$
    – prubin
    Jul 21, 2020 at 16:01

3 Answers 3

1
$\begingroup$

There are multiple ways to solve this problem, in my opinion it would be more of a ML problem but you can do with linear programming.

Let $a_i$ be the array of features for element $i$. Assuming you have a sample where given $a_i$ you are told the class it belongs to ($S_0$ or $S_1$), let $x$ be the matrix of weights and let $b\in[0,1]$ be an scalar. Establishing that \begin{equation} a_i'x \geq b \Longleftrightarrow a_i'\in S_0 \end{equation} \begin{equation} a_i'x \lt b \Longleftrightarrow a_i'\in S_1 \end{equation}

Then, we could say the given sample should be classified correctly: \begin{equation*} a_i'x \ge b, \hspace{10mm} i\in S_0 \\ a_i'x \lt b, \hspace{10mm} i\in S_1 \end{equation*}

There is no need for an objective function, although you may need one in case the problem is infeasible (there is no linear separation). In that case your objective function could be to maximize the accuracy of your predictions, recall, f1-score, depends on the problem.

$\endgroup$
1
  • $\begingroup$ I am familiar with OR stuff from undegrad maths like LP, convex optimization, knapsack problem etc. but I have not came across an OR problem that has an objective function depending on conditions (usually it just was an easy function or at least one that we can take derivative of). When I wrote about ML approach I just meant that one can build a model that would predict the outcome based on variables, did you have in mind some methods of determining the weights with ML, how then? Could you expand a little? Thanks! $\endgroup$
    – samiczy
    Jul 17, 2020 at 12:17
1
$\begingroup$

Given weights I can easily calculate how good these weights are for predicting but how can I determine weights?

From the answer above, $x$ would represent the weights and $b$ the cut point to decide whether a sample belongs to $S_0$ or $S_1$, those are the two variables in the OR problem. $a$ represents the observations from the sample. Solving that problem in linear programming would give you the resulting weights as well as the cut point.

$\endgroup$
1
$\begingroup$

This sure sounds like you guys are taking the long road to Logistic Regression....

You have a bunch of observations, presumably with outcomes to do the training or calculate the model, right?

Each observation has 207 data elements that are numerical. (Some/many of those will likely be dropped in the final model)

And you want to make a model from that to use on new data to predict 1/0 outcomes?

This is classic logistic regression, which should be your starting point (easiest) and then maybe some ML model, but this is not optimization unless you consider the calculation of weights for logistical regression an optimization problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.