3
$\begingroup$

I have a dataset full of 0s and 1s, and when I visualize it with t-SNE, which does dimensionality reduction. There is clearly some structure in it as shown below. Each color corresponds to a particular category. There are 10 categories, and there are roughly 180 data points for each category. Each data point is a 64-dimension vector, i.e. there are 64 features. The category information is NOT used by t-SNE, and the coloring is applied after t-SNE run is done.

enter image description here

Since the dataset is all 0s and 1s, and each data point is a 64 vector, so I thought I could plot them as 8x8 dimension binary images as shown below. I have plotted 3 examples for each category

enter image description here

If you compare among images in a single column, there appear to be some similarity sort of. If you compare among images in a single row, they look random to me. My question is that is there such an algorithm for rearranging the pixels, which is equivalent to reordering the elements in the original 64-dimension vector, so that MAXimize the visual similarity among images in each column (i.e. make them look as similar as possible) while MINimizing the visual similarity among images in each row (i.e. make them look as different as possible)? The whole point to make it easy to spot visual patterns for different categories if possible.

Update:

Thank you for @aelguindy's answer. For the record, I posted what the images look like before scrambling.

enter image description here

This notebook shows how the scrambled version is generated. This dataset is only for experiment. I have another real dataset of 0s and 1s that have nothing to do with hand-written images, of which I was trying to find visual patterns if possible.

$\endgroup$
  • $\begingroup$ Thanks. I have tried your approach, but I haven't made it work very well. I guess one big difference between my problem and the movie one is that there are distinct image classes in the datatset. I will update my question to make it more concrete. $\endgroup$ – zyxue Oct 29 '16 at 16:57
  • 1
    $\begingroup$ I've re-opened at your request, but I still think it's a duplicate of cs.stackexchange.com/q/55896/755. I still think those exact same methods should apply. I don't see understand why you think they won't apply here. The distinct image classes don't mess up the methods I described there; they should still work fine. (The image classes might provide additional information that might let us do even better, but I don't think it'll do any worse.) $\endgroup$ – D.W. Oct 29 '16 at 18:12
  • 1
    $\begingroup$ Your last comment makes it sound like you might misunderstand how my answer there works. My method never considers the "transitions" between frames or the similarity between consecutive frames; it only considers the correlation between the intensities of two pixels, in the same frame. $\endgroup$ – D.W. Oct 29 '16 at 18:13
  • 1
    $\begingroup$ I'm not sure what implementation you're referring to. Have you tried to implement the methods described there? The Jupyter notebook you shared doesn't implement it. The tSNE experiments are something different. $\endgroup$ – D.W. Oct 29 '16 at 18:24
  • 1
    $\begingroup$ Thank you all for your comments. I have completed rewritten the question, trying to make it as straightforward as possible. $\endgroup$ – zyxue Nov 2 '16 at 5:27
4
+50
$\begingroup$

This will not be an algorithm in the usual sense. It's a bunch of heuristics that you may find useful. The main difficulty comes from the undefined nature of the phrase "visually similar".

If I understand your question correctly. You have a few separate problems:

Defining what pairwise "visual similarity" is

You are looking for a function $S$ of two vectors to the interval $[0, 1]$. I imagine that you want it to ideally satisfy the following:

  • $S(\vec{x}, \vec{x}) = 1$, which means that a vector is most visually similar to itself.
  • $S(\vec{x}, \vec{y}) = S(\vec{y}, \vec{x})$, which means that measuring similarity between $x, y$ does not depend on their order.
  • $S(\vec{1}, \vec{0}) = 0$, which means that the most unsimilar vectors are the all-ones-vector and all-zeroes-vector.

Even with these restrictions you have a lot of choices. You can just count the number of matching pixels, but a one pixel shift in the image could give you maximum mismatch even if the images are visually very similar.

One simple heuristic that may suffice is counting all matching pixels. Then adding the number of $2\times2$ squares having a matching number of ones (sliding the comparison over all possible sub-squares), ..etc. You can try giving less weight to bigger squares. If you normalize by the maximum value you get (which is computed by comparing an image to itself). You get a value from 0 to 1. It's clear that this satisfies the assumptions above and captures similarity better than just comparing pixels.

These ideas are just examples of what you can do. If you experiment a bit, you can find some interesting $S$'s that capture your personal notion of visual similarity.

Deciding what you want to maximize for the data set.

Now assuming you have such an $S$, the question becomes what do you want to optimize. For a column (resp row), you can compute the sum or the median or the minimum (resp maximum). You can try to maximize the average column similarities minus the average row similarities or something of that sort.

Again, for an abstract $S$ that is not perfectly defined, you need to try different options and see what works best. As a guideline, optimizing for median vaguely means you optimize the common case, while allowing for outliers.

Quickly computing a permutation on $[1 \dots 64]$ that maximizes this quantity.

For some choice of $S$ and a choice of optimization criterion, it is extremely unlikely that you will find an efficient algorithm that finds the permutation optimizing that criterion. As you noticed in your question, the number of permutation grows very quickly with the size of the image.

One common heuristic that works quite well and is really easy to code, is local search. The idea is:

// Obj(p) is the criterion to be maximized. opt = null for t trials: p = random permutation for s steps: p' = copy p randomly swap two (or three) elements of p' if Obj(p') > Obj(p): p = p' if Obj(p) > Obj(opt): opt = p

This usually works well in practice. You have the knobs s and t that control the running time, you can even run the different trials fully in parallel. Increasing them usually yields better and better results. t controls the number of "starting points" for the search, which s controls the depth of the search. Again, you will need to experiment a bit.

Hope this helps.

$\endgroup$

Your Answer

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

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