Optimizing multiple objective functions simultaneously

Question

I apologize in advance - I am new to both stackexchange as well as as a lot of statistics/machine learning. This is a question I feel must have some fundamentally obvious answer, but after a lot of searching I have not been able to find one.

The problem:

I have a 60 x 80 matrix, where each row indicates a subject (n = 60) , and each column indicates a feature of that subject: $$ \begin{matrix} 1 & 0 & 0 ... & 1 \\ 0 & 1 & 1 ... & 0\\ 0 & 1 & 0 ... & 1\\ ... & ... & ... & ... \\ 1 & 1 & 0 ... & 0\\ \end{matrix} $$

I want to find the combination of features that:

a) maximizes the number of features

b) maximizes the number of subjects who have that exact feature set

What that boils down to in optimization terms is finding the 1x80 vector, let's call it F, of 0's and 1's that optimizes two objective functions:

a) $$arg_Fmax(\sum_{i=1}^mF_i)$$

b) $$arg_Fmin(\sum_{j=1}^nD_j)$$ where D is the distance between F and the vector for each subject.

Now, I have no clear idea where to start, so I cannot even tell y'all things I have tried. I have read a bit about this and it's only confused me with talk of centroids and Pareto optimums, and I can feel myself getting more lost. Am I overcomplicating this? Please also let me know if there is something I can improve in terms of formulating the problem or providing information to you.

EDIT: Basically, I want to select the greatest amount of subjects with the greatest number of features in common, where a 1 in each column indicates the presence of that feature and a 0 indicates a lack of that feature. I interpreted that as identifying a feature vector, F, that had a lot of 1's (features) but also matched the feature vectors of a lot of subjects.

In my mind, that means finding the feature vector F that a)has the greatest sum of its elements (the most 1's) and b) minimizes the sum of L2 distances between F and each subjects feature vector. Or maybe the cosine difference. I left "distance" vague because I have not decided how to characterize the distance between vectors.

As to your last point, if I choose a feature vector F that is all 1's (aka selects for all features) then it will not match any subject's feature correctly as every subject has a unique combination of 1's and 0's. I want to match the greatest number of subjects correctly, while selecting the greatest number of features.

Answer 1

I am going to interpret the following as being what the OP wants:

For each number of features k, from 1 to 80:

Consider all submatrices of your matrix, where each submatrix is indexed by a specified set of rows and set of k columns. Find the maximum number of selected rows (subjects) such that there is a submatrix with those selected rows and k columns (features), for which the submatrix consists entirely of ones. This gives the optimal solution for k features. Note that this approach uses in effect an all or nothing "distance" measure; there is no middle ground.

At the conclusion of this, you will know the maximum number of subjects for each number of features. Choose the combination you prefer.

For a given value of k (number of features), the above problem of determining {the maximum number of selected rows (subjects) such that there is a submatrix with those selected rows and k columns (features), for which the submatrix consists entirely of ones} can be formulated and solved as a binary linear programming problem (which is not to rule out other, possibly faster, approaches). For convenience to crank out some quick prototype results, I used the YALMIP package http://users.isy.liu.se/johanl/yalmip/ under MATLAB, and made use of its "implies" command to formulate the needed constraints. To provide a concrete example, I ran this for a randomly generated 60 by 80 matrix, for which each element was 1 with probability 0.8, and 0 with probability 0.2, independent across all elements (I'm not claiming that is a realistic or representative matrix).

The results are as follows:

(number of features, maximum number of subjects)

 1    56
 2    51
 3    46
 4    42
 5    38
 6    35
 7    33
 8    31
 9    28
10    26
11    25
12    24
13    22
14    21
15    20
16    19
17    18
18    17
19    16
20    15
21    14
22    14
23    13
24    13
25    12
26    12
27    11
28    10
29    10
30     9
31     9
32     9
33     8
34     8
35     8
36     7
37     7
38     7
39     6
40     6
41     6
42     6
43     5
44     5
45     5
46     5
47     4
48     4
49     4
50     4
51     4
52     3
53     3
54     3
55     3
56     3
57     2
58     2
59     2
60     2
61     2
62     2
63     2
64     2
65     1
66     1
67     1
68     1
69     1
70     1
71     1
72     0
73     0
74     0
75     0
76     0
77     0
78     0
79     0
80     0

As you can see, in this example, there are some "inefficient" (not pareto optimal) numbers of features, specifically, 21, 23, 25, 28, 30-31, 33-34, 36-37, 39-41, 43-45, 47-50, 52-55, 57-63, 65-70, all of which you would presumably not pick, because more features can be used and still get the same maximum number of subjects.

Number of features $\ge $ 72 is not "feasible" for any number of subjects in this example, i.e., zero is the maximum possible number of subjects if number of features $\ge $ 72, which of course is the case because the maximum row sum of the matrix = 71. So the maximum row sum could be used as an easy way to determine the maximum value of k (number of features) for which the optimization even needs to be attempted.

Similarly, the maximum column sum of the matrix is 56, which in this case, as always, will be the maximum possible number of subjects for one feature.

Answer 2

Basically you have two options ahead of you.

1. You assume a (possibly linear) tradeoff between the two objective functions and reduce your multi-objective problem to a single objective problem. Basically you try to optimize something like: $$\sum F_i + \alpha \sum D_i$$ Where you are assuming that the second objective is $\alpha$ times more important than the first.

2. You do not specify a tradeoff: in this case rather than producing a single "best" you create a "pareto front", which is the list of choices where you can't be better off in one optimal dimension without being worse off in another.

For a proper treatment at undergraduate level of these problems I suggest Luke's Essentials of Meta Heuristics which is a great book and completely free.

However in your specific case there is no reason to go through fancy algorithms. Since you have only 80 options I suggest you to compute $\sum F_i$ and $\sum D_i$ for each possible $F_i$. You are then left with a $80 \times 2$ matrix where each row is a feature $F$ and each column is one of the two objectives you are trying to maximize.

Once that's done start deleting each row/feature when both of its objectives are lower than what is available in another row. For example: $$\begin{bmatrix} 80 & 20 \\ 30 & 30 \\ 10 & 10 \end{bmatrix}$$ Here you can remove the third row since it is "dominated" by the second (both its objectives are lower than what is available in the second row).

Keep removing until nothing can be removed. If there is only one row left, that's your best. If, as it is more likely, there are many rows left each is a candidate best and then it's up to you to decide how much of one objective you are willing to sacrifice to improve the other one.