suppose we have data matrix A m-by-n (m observations and n features) which I want to Apply SVM on it achieving privacy (Privacy-Preserving SVM)
the questions are:-
1 - Is applying kernel trick considered as Privacy-Preserving SVM?
2 - Is converting the data matrix into D = A.Transpose[A] and learning from *D m-by-m * considered as Applying a kernel?
thnq .. :)
Before giving some detail, I'll briefly say: regarding (1), kernel trick is basically the worst thing for privacy, and regarding (2), you have replaced each vector with a vector of kernel products (via the linear kernel), and this is non-equivalent to replacing inner products with kernel products inside the algorithm.
Some background on (1) for those who asked. Suppose you want to learn a linear predictor; among those consistent with the data (i.e. correct on all examples), which do you choose? The SVM solution is to pick the one which maximizes the minimum distance to any example (maximizes the 'margin'). In the case that no consistent predictor exists, small penalization is assigned to margin violations (learning the best linear predictor, in the presence of noise, is NP-hard).
now say your data is a set of records for some group of people (for instance, each "point" is a vector of medical parameters for some person). You want to release a predictor (say, a website where someone can put in some info and see if they have some disease or not), but don't want anyone to be able to reconstruct properties of the people in your data set. Here's an example; let's say I know someone is the only person in some remote part of saskatchewan, and I want to see if they were used to learn this predictor. And say, one of the attributes in the web form is location. For privacy ignorant algorithms, I can see how sensitive the algorithm is to queries with this personal data, and infer things about the person in question (for instance, if saying I'm from remote-part-of-saskatchewan but varying all other parameters always says I have the disease (and the answer is sensitive to location), that means that guy has the disease). Said another way, if I know some unique characteristics of a person, I can see how the algorithm reacts to them in order to determine other properties of that person.
Anyway, here's why the kernel trick is the worst thing for this. The kernel trick just means you store your predictor as $$ p(x) = \sum_{i=1}^m a_ik(v_i, x), $$ where $\{v_i\}_1^m$ are your support vectors. This means the predictor for any kernelized linear classifier (not just SVM) will explicitly store a set of records! Therefore, if you manage to plug in a support vector for $x$, you can expect it to strongly affect the value of the predictor. Going back to the remote-part-of-saskatchewan example, suppose the kernel is gaussian, and you fix all other parameters, and see the effect of the saskatchewan input. Since distances are all huge in high dimension, that means, if the guy is in the dataset, the predictor value will be strongly affected by matching the remote-part-of-saskatchewan fields or not. Thinking geometrically, each support vector plops a gaussian in the space (color them white or black based on their label), and if this guy is really the only person in that remote part of saskatchewan (and if he was a support vector), that means his gaussian will basically entirely control the value of the predictor.
EDIT. I should say that research in privacy preserving learning is all about taking privacy-ignorant algorithms and making them output privacy-secure predictors. There are definitely strategies to make kernelized algorithms more privacy preserving--for instance, don't let any region of the space be "covered" by just one support vector (some sort of smoothness condition, i.e. how much the predictor is affected by removing or adding in this example); this in turn usually means.. have TONS of support vectors. Another strategy is to inject perturbations in places, but notice this is delicate--if you just perturb this saskatchewan record, it is still basically the only gaussian in that region of space, so you've done nothing. Anyway all I am saying is that kernelized algorithms are a difficult starting point for privacy preservation. (and the "have TONS of support vectors parts" starts to mitigate the benefits of the kernel trick..)
About (2).. let $A$ contain all points as columns; a linear predictor can be written as $$ p(x) = x^\top Av $$ where $v$ is a vector of weights (in the linear case, you can "compress" this and just keep weights $w=Av$ around). (to be explicit, you also check the predicate $p(x)\geq 0$.) In your case, you have replaced $A$ with $AA^\top$, and also you must map any input vector $x$ to $Ax$, thus your predictor is $$ p'(Ax) = x^\top A^\top AA^\top v'. $$ For general matrices $A$, it is possible that some choice $v$ does not have a choice $v'$ which makes these equivalent...... thus, this is not the same as simply "kernelizing" the algorithm.
That said, it is reasonable to replace your data with kernel products in this way, but that is a feature selection issue; i've attempted to discuss the math part...........
Well, it is important to specify what exactly you mean by "privacy". If you want a formal guarantee that no attacker will be able to learn very much about any individual, even given the output of your SVM, your best bet is probably to try and guarantee "differential privacy". This is a strong formal guarantee that the distribution output by your learning algorithm is insensitive to any individual datapoint in your training set.
Luckily for you, it is known how to train SVMs while preserving differential privacy. Here are the two papers you might be interested in:
"Differentially Private Empirical Risk Minimization" by Chaudhuri, Monteleoni, and Sarwate and...
"Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning" by Rubinstein, Bartlett, Huang, and Taft.
