Improve `cvector-generator`

[ngxson]

• Fix random direction of vector produced by PCA method cvector: better prompt handling, add "mean vector" method #8069 (comment) (cc @jukofyork)
• Performance: Using batch and multi-sequences (for llama_decode)
• Performance: Allow using GPU (need to test, because some backends don't support certain ops)
• Add SVD and UMAP
• Add tests if possible

Ref: #7514

Note: I'm writing this for tracking, but people are free to do PRs if you have any ideas to share. I'm planning to do some of the tasks in August 2024.

[mhnghfv]

I've looked into the code and related material and it seems like this PCA idea is broken.
A normal PCA implementation would:

1. Center the data by subtracting the mean
2. Compute a matrix of covariances between the dimensions of the data (the covariance matrix)
3. Compute eigenvectors of covariance matrix.

The hardest part is the last part, so in #6880 , @jukofyork suggested a simple algorithm that can calculate the largest eigenvector (which easy to do efficiently compared to trying to do all eigenvectors at once), which would give the 1st principle component.
You have however seemed to misinterpreted that as being the whole of the PCA algorithm. This resulted in your confusion about the embedding matrix not being square in #7514 - covariance matricies are always square so this is not a problem for PCA, but you skipped the first two parts of the algorithm and tried to feed the input directly into step 3. @christianazinn saw that this is how it was done in SciPy but said "We may care to implement this after everything else works" and instead suggested substituting it with multiplying the matrix by its transpose as a temporary fix, but since this would still be the wrong matrix (not the covariance matrix), the algorithm would not work correctly until the real covariance matrix was implemented.

However, even if PCA was implemented correctly, it might still not work. This is because you're not supposed to take the PCA of the difference between the positive and negative vectors. If we look at the paper that #5970 referenced, we see that in "Constructing the PCA Model" they specify "we do not use any labels by default unless explicitly stated otherwise, making the procedure unsupervised" - this is an unsupervised method, meaning it takes random unlabeled data (not positive and negative examples) and finds features on its own. Another quote from the paper - "PCA - We take an unlabelled dataset D that primarily varies in the concept of interest. We take the top PCA direction that explains the maximum variance in the data."

Some of the wording in the papers seems to imply that running PCA on the differences would make sense, but if you think about how PCA is supposed to work, you would expect that to fail, since the first step centers the data, which would subtract the average difference and obliterate the main direction of difference between the positive and negative examples, leaving PCA to find some other unrelated feature left behind after that. Random pairing would not have this issue since random differences would not average to anything meaningful and therefore keep the negative-positive feature intact. Randomizing the order/direction of the pairing (e.g. positive-negative vs negative-positive) would also alleviate this issue, which I expect might be the reason why the paper reports good performance of PCA on paired differences, though there might also be some other reason that I'm missing. But even in the paper, PCA is used mainly as an unsupervised method, while mean difference is used as a supervised method.

The blog post referenced in #5970 seems to be confused by this and suggest taking PCA of differences in the blog post. If you look at github issues for the control vector library that is used in the blog, vgel/repeng, people report it not working for some models other than the one the author used (issue 33). But it does appear to work in the blog post and some other related discussion, so maybe there's something about PCA that counterintuitively works here despite what would be would expected.

Your implementation also seems like it could accidentally work in some situations, since you are multiplying a matrix of differences by its transpose, which is somewhat vaguely similar to how correlation is calculated, though differences to the mean are used rather than paired differences. But for examples that vary significantly in some direction from the mean, properly paired differences would be roughly in the same direction as difference from the mean so your matrix would accidentally compute something PCA-like, which could work, sometimes, and only when the direction of the largest difference is aligned with the desired negative-positive difference. Indeed, your examples didn't work as expected for me when I tested them, the control vector produced sad/dramatic outputs for both positive and negative scale values. The model I was using was not llama however so maybe it really does work on llama for some reason.

TL;DR PCA is not supposed to be used for paired negative-positive examples, and the implementation is broken anyway.
My personal opinion is that it should either be removed it or the original unsupervised control vectors should be implemented with a correct PCA implementation. Mean-difference method should be correct afaik and can be kept as is.

[jukofyork]

Finding the eigenvectors of a data matrix multiplied by its transpose is a valid way of computing PCA so long as you mean center the data matrix first (if you use SVD on the data matrix and then take the right singular vectors then you don't need to mean centre though).

I think the main problem with the current code is it's missing the final step where you project the data onto the vector to decide if the sign of the vector needs flipping - without this step the control vectors are very broken.

@ngxson said in a different thread he was busy with his job at but going to look at this soon.

If he doesn't then I will have a look at fixing it - I'm just not that familiar with the ggml stuff and it looks like quite a time investment to be sure of not leaking memory and/or doing other stupid stuff :/

Computing the first PCA component only is actually really easy and doesn't really need to calculate the covariance matrix at all: use gradient descent to train an autoencoder with a single scaler using least squares loss (aka Oja's rule). You can extend this idea to get the first few PCA components too (by repeated subtraction of the component then reruning) but as the eigenvalues get smaller and smaller if starts to suffer from numerical problems.

[jukofyork]

I've actually found what I think is a better way to do this though via the cross-covariance matrix:

https://github.com/jukofyork/control-vectors

The basic idea is to generate 3 samples for each prompt: baseline, negative and positive. Then subtract the positive and negative from the baseline (instead of mean centering). Then finally find the eigenvectors of the cross-covariance matrix of these two matrices (and use either the discriminant ratio or variance reduction to find the eigenvector you want and some other stuff - see the code here ).

The reason this seems to work better is it specifically looks for directions that are "balanced" in terms of their vector norms from the baseline. The cross-covariance matrix can only have a large value if both are large (and is maximised when both are equidistant from the baseline) whereas the covariance matrix can have a large value if one is almost the same as the baseline.

[mhnghfv]

Finding the eigenvectors of a data matrix multiplied by its transpose is a valid way of computing PCA so long as you mean center the data matrix first (if you use SVD on the data matrix and then take the right singular vectors then you don't need to mean centre though).

I mean, I did mention that in

which is somewhat vaguely similar to how correlation is calculated, though differences to the mean are used rather than paired differences

difference to mean being the same as centered data. (instead of correlation I should have said covariance).
But it's still the case the original algorithm can (should?) be used on unlabeled data unsupervised. Maybe we should somehow allow mixing in labeled with unlabeled data for easy semi-supervised training

[mhnghfv]

The basic idea is to generate 3 samples for each prompt: baseline, negative and positive. Then subtract the the positive and negative from the baseline (instead of mean centering). Then finally find the eigenvectors of the cross-covariance matrix of these two matrices

sounds like a good idea

[jukofyork]

difference to mean being the same as centered data. (instead of correlation I should have said covariance). But it's still the case the original algorithm can (should?) be used on unlabeled data unsupervised

I've tried many different methods over the last month or so and I think what you mean is: concatonate both datasets and find the principal eigenvector? If so, then this doesn't always work because often the principle (and even the 2nd) eigenvector will actually not be the direction that forms an axis between the two things you want, eg: in terms of creative writing trying to use "positive" and "dark" examples often ends up with "story writing" as the first principle component. You can do some post processing like in the code I linked above to find which direction is the correct one, but it is still inferior to the cross-covariance matrix method from my experiments.

[jukofyork]

There is a lot of my thoughts in this thread:

https://huggingface.co/jukofyork/creative-writing-control-vectors-BETA-v0.1/discussions/2

and the different iterations of things I've tried are here:

https://huggingface.co/collections/jukofyork/creative-writing-control-vectors-66859c95443833e90f8a7f84

The latest control vectors use soft-thresholding as a form of L1-regularisation (the scale factor in llama.cpp can be thought of as similar to L2-regularisation).

The biggest limitation of the method is only being able to effect a single "writing trait" at a time - vector addition somewhat works but if very finicky and blended training data ends up with much less discrimination between the classes...

The transformers code won't actually let me get the inputs to the down_proj matrix, but if you can get samples of both input and output then it may be possible to modify the down_proj matrix as a "cheap" form of fine tuning (ie: back prop only through the down_proj matrix using least squares, use contrastive or triplet loss, and so on).

It may turn out you still need the control vectors though (to act as a bias / affine transformation) as from experiments with Householder transformations on down_proj it seems very hard to make a model change it default behavior using linear transformations alone (ie: you can reflect and rotate a models' sense of "dark" and "positive" writing, but you can't actually get rid of "positively bias" like this).

[ngxson]

@mhnghfv Hi and thanks for having a look into the code. To give you a bit of context, the PCA implementation is initially proposed by @christianazinn . I'm not particularly good at math (since my background is software engineer), so to be honest, I would have been impossible for me to do this without invaluable help from him and @jukofyork .

However, the implementation is not guaranteed to be exactly correct, so we're currently depend on help from contributors. It would be very helpful if you can create a PR to showcase your approach.

A quick update for the current issue: I started some initial work in this branch, but it turns out to be far more complicated than I thought. It's true that simply subtracting negative - positive pairs is quite naive, but doing other way will require a refactoring. As I'm currently busy with other part of the project, I can't be confident that it can be finished very soon.

[jukofyork]

If you can get the code to the stage where the data matrices are just stored as plain C++ vectors or a straightforward chunk of C floats, then I can quite quickly get the rest of the code working just using plain C++ vectors (on the CPU) and then look at porting this to use the ggml GPU code if necessary.

I just can't spend the time needed to learn all the ins and outs of the ggml stuff atm, and I can't see an easy and straightforward way to pull apart the existing code as all the differencing logic is done online via ggml calls :/

If I could just get a couple of std::vector<std::vector<float>> to work from then I can bypass all the ggml stuff and it would super easy for me to do all the rest.

[jukofyork]

Even just some very barebones code to set up the callbacks, pulling the floats out of the ggml tensors and placing in a std::vector and correctly deallocating memory and/or closing any contexts so as not to leak memory or resources, and I would be good to go :)

[jukofyork]

A quick update for the current issue: I started some initial work in this branch, but it turns out to be far more complicated than I thought. It's true that simply subtracting negative - positive pairs is quite naive, but doing other way will require a refactoring. As I'm currently busy with other part of the project, I can't be confident that it can be finished very soon.

Yeah, I thought I might be able to fix the sign problem easily when ChuckMcSneed mentioned it in the other thread, but by having the matrices pre-differenced I couldn't see an easy way either :/

I think the pre-differenced matrix is the main blocker atm.

[ngxson]

Even just some very barebones code to set up the callbacks, pulling the floats out of the ggml tensors and placing in a std::vector and correctly deallocating memory and/or closing any contexts so as not to leak memory or resources, and I would be good to go :)

IIRC this is actually what @christianazinn did in the first version of the implementation. It works well for prototyping because it doesn't require playing with ggml, so it's also a good practice. Once everything works and you want to have proper GPU support, I can help to convert the implementation to ggml.