האם שינוי סדר פשוט יכול לשפר את הקיבוץ שלך ב-77%?

Thanks everyone for coming. This is going to be based on our joint work with Ron Eisenberg and Jonathan Svirsky, which are both graduate students in my lab. Yonatan just graduated and this work was presented in ICLR last year. Okay, so what is multi view clustering or what is the multi view setting? It is actually also multimodal setting, but for, for the sake of this discussion, let's call it multi view. So we're thinking of some parameter of interest which is low dimensional, and then we have two measurement devices that are measuring this parameter of interest. And maybe they're also measuring something which is irrelevant for the parameter of interest. Could be noise, could be nuisance variables, something that I'm not really interested in. And, and the modalities that I'm interested in could be fmri, eeg, ultrasound and omics. But, but the basic setting is that I have pairs of observations from different high dimensional vectors and the pairing could be through the individuals or through other source of meta information. And then what I'm trying to do is I'm trying to, given the matrices that we have from the measurement device which like I said, measured the important information which is shared and the nuisance information, I want to find some shared representation which is also going to be useful for clustering. Okay? So my gold standard would be to extract theta, and then this theta would be useful for clustering. So a classical method to solve this problem is canonical correlation analysis. It's almost 100 years old. The idea is I think of this as a generalization of pca, but essentially you take two matrices of different dimensions, same number of observations, samples of pairs, so the same individual in a different matrix correspond to the same individual. And then I want to project both of these matrices into a shared space. Here in this example, I'm projecting into one dimensional space just for the sake of simplicity. And then my objective is to maximize the correlation in this low dimensional space. So essentially I'm just learning these linear combinations of variables in each of the input spaces, X and Y. So conceptually I'm learning to project to this low dimensional space and then these two new axes are correlated. Namely if I gradually grow in one dimension, the other dimension also grows and CC has a closed form solution using the empirical covariance matrices of X and Y and the cross covariance matrices. And in this very simple two dimensional example, if these are my two sets of samples and CCA would find these two directions and then I would project to the low dimensional space, one dimension in this example, and then you can see that the after projection, the samples are correlated. And also I'm capturing the cluster structure in both of these projections. So in fact CCA in this setting is linear, but it has many, many nonlinear extensions, including kernel CCA by Bach and Jordan and even work by Tomer Michaeli, which is here, and myself, and many, many methods. And if you look at how useful CCA is for clustering. So this is a Google Scholar search of CCA and clustering, and you can see that there's nearly half a million academic works that mention the fact that this is useful for clustering, which means that there's more use cases of this idea. And here are examples of CCA and different variants of cca. So deep CCA and deep CCA autoencoders applied to some coupled coupled setting of mnist. And you can see that the low dimensional representation colored by the true label does capture the cluster separation. So our basic research question is how can we use some CCA method, classical cca, nonlinear cca, but do something to make it better capture the cluster structure? And our key observation is very simple and it's that the pairing that we use for different samples and different views is defined by nature. So this could be different in same individual. But if we just permute samples and create artificial pairings by creating pairs of samples that are from the same cluster. So I'm permuting the indices of samples in one view and then I'm creating artificial pairings by only permuting from within the cluster, then conceptually it looks like this illustration. I want to see how this affects the representation that I'm learning with cca. And this is a very simple three dimensional illustration. So you see on the top view it's two observation spaces, X and Y, both three dimensions, three dimensional. And you see that the cluster separation is not perfect. But once we project the CCA and we add more pairs of samples which are artificially created by the permutations, you can see that the separation created in CCA space is better for clustering the data. Okay, so this is a very simple example. Here's another simple example which is used academically. It's a coupled noisy version of mnist. So different background noise. If you just apply CCA to the original coupled setting of X and Y, then you get results like you see on the left two panels. And if you permute the samples and then apply cca, you get something like you see on the right, so namely a better three dimensional representation to capture the cluster structure. Okay, so theoretically we tried to explain why this thing works or why this thing is better for capturing the cluster separation. And our theoretical analysis is attempting to relate the eigenvector solution that you get from CCA to the eigenvector solution that you get from a supervised method, which is called linear discriminant analysis. It's also a linear method and LDA is trying to maximize the objective that I wrote here, which is to maximize the variance across classes and to minimize the variance within the class. Okay, so that's the ratio that we see here. And what we showed is that essentially if we permute samples and augment the data set with many, many such permutations by only permuting within the class, within the correct classes, then the solution of CCA would approach the solution of lda. Okay, but I am kind of cheating here because I am permuting by knowing the label. But this is for this theoretical analysis. In practice, we will permute unsupervised without knowing the labels. Here, here's an illustration. We take two halves of fascia nimnist. In the first plot you see what CCA gives you. It's not a good embedding for capturing the cluster separation. But then if you permute the samples and apply CCA again and again, you get a better two dimensional embedding for clustering this data. And on the bottom it's a little bit small, but you can see the K means accuracy or ari here improves from 0.59 to 0.872. Okay, so this is an unsupervised permutation. So we don't use the ground truth labels to permute. And you can see that there is an improvement here. On the bottom you see something more quantitatively. On the x axis you see the number of samples that we permute and we see three different plots. So the light blue one is the one that I get for permuting only within the same class. So it's kind of cheating. It's an oracle permutation. And you can see that the clustering accuracy based on the low dimensional embedding does improve compared to the baseline, which is just classical cca. And you can see that the unsupervised setting, which is clustering, permuting within clusters, also does improve the performance. That's the purple. And just randomly permuting actually degrades the performance, not permuting within the clusters. We also tried to quantify what the effect of wrong labels. So because we only permute within the clusters, we're not guaranteed to find the correct pseudo labels. That we assign for each cluster. So we try to quantify how this affects our solution. So we model this as the optimal solution plus some perturbation matrix. And then this tells us that if the pseudo label mistakes that we make are large, then the representation that we get is going to be not close to the LDA solution. But if we get reliable pseudo labels, then the solution that we get can be close to the LDA solution. Okay, so we also this is analysis for the linear setting for a CCA connecting it to lda. But we also propose an end to end deep learning solution for clustering. It's essentially two encoders or more encoders if you have more than two views, which tries to maximally correlate the samples in the low dimensional space. And then after you do this, for each batch, you permute samples which were assigned pseudo labels with a clustering head and then you iterate again and again with sgd. So it's not retrained the network from scratch, it's done just throughout the iterations. We just permute samples from each batch. And this is a procedure which we call coper. And I'll show results in the next slides. But basically we do have to reliably select pseudo label and I'm going to talk about that as well. So how do we select those reliable pseudo labels? We embed samples into two spaces. We have a clustering head in each space that assigns pseudo labels. We look for the samples that are closest to the cluster center and then we only select samples with agree in terms of their pseudo labels. So this filters out and we end up with selecting only samples which we think are correct in terms of the labels. We only permute them. And this happens throughout the training of the neural networks. Here we compare ourselves to different methods. Some are CCA based, deep CCA based and other which were proposed to this end to end deep cc, deep clustering, deep multi view or multimodal clustering task. So we compare ourselves to vision data sets or other domains, biological data sets. You can see that the average gain over the best method is roughly 5.7. We also show gains compared to the linear method. So just CCA plus. This permutation also increases the clustering performance. And we also show ablation. Demonstrating each component of the method is crucial. And importantly, you can see that the permutation itself Leads to roughly 77.2 accuracy gain compared to not doing the permutation. So just to conclude, these reliable tail labels allow us to kind of augment the samples with permutations. Of pairs of indices. And we also propose this, we connect this to LDA and we also propose this end to end solution for multiview clustering. We have code for this. And you can email me for questions.