.. _mlcrypteddatacorrectionrst: ========================================================= 2A.ml - Machine Learning et données cryptées - correction ========================================================= .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/td2a/ml_crypted_data_correction.ipynb|*` Comment faire du machine learning avec des données cryptées ? Ce notebook propose d’en montrer un principe exposés `CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy `__. Correction. .. code:: ipython3 %matplotlib inline .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: **Principe** Voir l’énoncé. Exercice 1 : écrire deux fonctions de cryptage, décryptage ---------------------------------------------------------- Il faut bien choisir :math:`n`, :math:`a` pour implémenter la fonction de cryptage : :math:`\varepsilon:\mathbb{N} \rightarrow \mathbb{Z}/n\mathbb{Z}` et :math:`\varepsilon(x) = (x * a) \mod n`. On vérifie ensuite qu’elle conserve l’addition au module :math:`n` près. .. code:: ipython3 def compose(x, a, n): return (a * x) % n def crypt(x): return compose(x, 577, 10000) crypt(5), crypt(6) .. parsed-literal:: (2885, 3462) .. code:: ipython3 crypt(5+6), (crypt(5) + crypt(6)) % 10000 .. parsed-literal:: (6347, 6347) .. code:: ipython3 crypt(6-5), (crypt(6) - crypt(5)) % 10000 .. parsed-literal:: (577, 577) .. code:: ipython3 crypt(5-6), (crypt(5) - crypt(6)) % 10000 .. parsed-literal:: (9423, 9423) Si :math:`a=47`, on cherche :math:`a',k` tel que :math:`aa' - nk=1`. .. code:: ipython3 n = 10000 for k in range(2, n): if (577*k) % n == 1: ap = k break ap .. parsed-literal:: 2513 .. code:: ipython3 def decrypt(x): return compose(x, 2513, 10000) decrypt(crypt(5)), decrypt(crypt(6)) .. parsed-literal:: (5, 6) .. code:: ipython3 decrypt(crypt(5)*67), decrypt(crypt(5*67)) .. parsed-literal:: (335, 335) Notes sur l’inverse de a ------------------------ Si :math:`n` est premier alors :math:`\mathbb{Z}/n\mathbb{Z}` est un corps. Cela implique que tout nombre :math:`a \neq 0` a un inverse dans :math:`\mathbb{Z}/n\mathbb{Z}`. Donc, :math:`\forall a \neq 0, \exists a'` tel que :math:`aa'=1`. On va d’abord montrer que :math:`\forall a \neq 0, \forall k \in \mathbb{N^*}, a^k \neq 0`. On procède par l’absurde en supposant que :math:`\exists k > 0` tel quel :math:`a^k=0`. Cela signifie qu’il existe :math:`v` tel quel :math:`a^k = vn`. Comme :math:`n` est premier, :math:`a` divise :math:`v` et on peut écrire que :math:`a^k = wan \Rightarrow a(a^{k-1} - wn)=0`. Par récurrence, on peut montrer qu’il existe :math:`z` tel que :math:`a = zn` donc :math:`a` est un multiple de :math:`n` et c’est impossible car :math:`a` et :math:`n` sont premiers entre eux. L’ensemble :math:`A=\{a, a^2, a^3, ...\}` est à valeur dans :math:`\mathbb{Z}/n\mathbb{Z}` et est fini donc il existe nécessairement :math:`i` tel que :math:`a^i \in A`. Il existe alors :math:`k > 0` tel que :math:`a^i \equiv a^k \mod n` et :math:`u` tel que :math:`a^i = a^k + un`. On suppose d’abord que :math:`i > k`, alors :math:`a^k(a^{i-k} -1) = un`. Comme :math:`n` est premier, :math:`a^{i-k} -1` divise :math:`n` donc il existe :math:`v` tel que :math:`a^{i-k}=un + 1` donc :math:`a^{i-k} \equiv 1 \mod n`. On note :math:`a^{i-k-1} = a^{-1}` l’inverse de :math:`a` dans :math:`\mathbb{Z}/n\mathbb{Z}`. Si :math:`k > i`, la même chose est vraie pour :math:`a^{k-i}`. Si :math:`i^*=\arg\min\{i \, | \, a^i \in A\}`, :math:`i^* \leqslant n-1` car l’ensemble :math:`A` contient au plus :math:`n-1` éléments et :math:`i^*-k < n-1`. On note maintenant :math:`j^* = \arg \min \{j \, | \, a^j \equiv 1 \mod n\}`. Donc ce cas, on peut montrer que :math:`A = \{1, a, ..., a^{j^*-1}\}`. :math:`j^*` est l’[ordre](https://fr.wikipedia.org/wiki/Ordre_(th%C3%A9orie_des_groupes) du sous-groupe engendré par :math:`a`. Le `théorème de Lagrange `__ nous dit que cet ordre divise :math:`n-1` qui est l’ordre du groupe multiplicatif :math:`\mathbb{Z}/n\mathbb{Z} \backslash \{0\}`. On peut donc écrire :math:`n-1=kj^*` avec :math:`k \in \mathbb{N}`. Par conséquent, :math:`a^{n-1} \equiv 1 \mod n`. Ce théorème en considérant les classes d’équivalence qui forment une partition de l’ensemble du groupe de départ. Exercice 2 : Entraîner une régression linéaire ---------------------------------------------- .. code:: ipython3 from sklearn.datasets import load_diabetes data = load_diabetes() .. code:: ipython3 X = data.data Y = data.target .. code:: ipython3 from sklearn.linear_model import LinearRegression clr = LinearRegression() clr.fit(X, Y) .. parsed-literal:: LinearRegression(copy_X=True, fit_intercept=True, n_jobs=1, normalize=False) .. code:: ipython3 clr.predict(X[:1]), Y[0] .. parsed-literal:: (array([ 206.11706979]), 151.0) .. code:: ipython3 from sklearn.metrics import r2_score r2_score(Y, clr.predict(X)) .. parsed-literal:: 0.51774942541329338 On considère seulement la fonction de décision brute car c’est une fonction qui peut-être calculée à partir d’additions et de multiplications. Pour la suite, nous aurons besoin d’un modèle qui fonctionne sur des variables normalisées avec `MinMaxScaler `__. On supprime également le biais pour le remplacer par une colonne constante. .. code:: ipython3 from sklearn.preprocessing import MinMaxScaler import numpy X_norm = numpy.hstack([MinMaxScaler((0, 100)).fit_transform(X), numpy.ones((X.shape[0], 1))]) Y_norm = MinMaxScaler((0, 100)).fit_transform(Y.reshape(len(Y), 1)).ravel() .. code:: ipython3 Y_norm.min(), Y_norm.max() .. parsed-literal:: (0.0, 100.0) .. code:: ipython3 clr_norm = LinearRegression(fit_intercept=False) clr_norm.fit(X_norm, Y_norm) .. parsed-literal:: LinearRegression(copy_X=True, fit_intercept=False, n_jobs=1, normalize=False) .. code:: ipython3 clr_norm.predict(X_norm[:1]), Y_norm[0] .. parsed-literal:: (array([ 56.42276317]), 39.252336448598129) .. code:: ipython3 from sklearn.metrics import r2_score r2_score(Y_norm, clr_norm.predict(X_norm)) .. parsed-literal:: 0.51774942541329338 Exercice 3 : réécrire la fonction de prédiction pour une régression linéaire ---------------------------------------------------------------------------- La fonction est un produit scalaire. .. code:: ipython3 def decision_linreg(xs, coef, bias): s = bias xs = xs.copy().ravel() coef = coef.copy().ravel() if xs.shape != coef.shape: raise ValueError("Not the same dimension {0}!={1}".format(xs.shape, coef.shape)) for x, c in zip(xs, coef): s += c * x return s .. code:: ipython3 list(X[0])[:5] .. parsed-literal:: [0.038075906433424102, 0.050680118739818703, 0.061696206518688498, 0.021872354994955798, -0.044223498424446402] .. code:: ipython3 clr.predict(X[:1]), decision_linreg(X[:1], clr.coef_, clr.intercept_) .. parsed-literal:: (array([ 206.11706979]), 206.1170697870923) .. code:: ipython3 clr_norm.predict(X_norm[:1]), decision_linreg(X_norm[:1], clr_norm.coef_, clr_norm.intercept_) .. parsed-literal:: (array([ 56.42276317]), 56.422763173548944) Exercice 4 : assembler le tout ------------------------------ Prendre une observation, crypter, prédire, décrypter, comparer avec la version non cryptée. Il faudra sans doute un peu ruser car la fonction de cryptage s’applique à des entiers et le modèle de prédiction à des réels. On multiplie par 10000 les variables. Comme le cryptage que nous avons choisi ne conserve que l’addition, nous garderons les modèles en clair. .. code:: ipython3 coef_int = [int(i) for i in clr_norm.coef_ * 100] coef_int .. parsed-literal:: [0, -7, 42, 24, -69, 46, 8, 14, 60, 5, -843] .. code:: ipython3 inter_int = int(clr_norm.intercept_ * 10000) inter_int .. parsed-literal:: 0 .. code:: ipython3 import numpy def decision_linreg_int(xs, coef): s = 0 for x, c in zip(xs, coef): s += c * x return s % 10000 def decision_crypt_decrypt_linreg(xs, coef_int): # On crypte les entrées int_xs = [int(x) for x in xs.ravel()] crypt_xs = [crypt(i) for i in int_xs] # On applique la prédiction. pred = decision_linreg_int(crypt_xs, coef_int) # On décrypte. dec = decrypt(pred % 10000) return dec / 100 (decision_linreg(X_norm[:1], clr_norm.coef_, clr_norm.intercept_), decision_crypt_decrypt_linreg(X_norm[0], coef_int)) .. parsed-literal:: (56.422763173548944, 54.65) .. code:: ipython3 p1s = [] p2s = [] for i in range(0, X_norm.shape[0]): p1 = decision_linreg(X_norm[i:i+1], clr_norm.coef_, clr_norm.intercept_) p2 = decision_crypt_decrypt_linreg(X_norm[i], coef_int) if i < 5: print(i, p1, p2) p1s.append(p1) p2s.append(p2) import matplotlib.pyplot as plt plt.plot(p1s, p2s, '.') .. parsed-literal:: 0 56.4227631735 54.65 1 13.4181768255 11.59 2 47.3159066512 45.73 3 44.2112042336 42.02 4 32.2304805013 30.26 .. parsed-literal:: [] .. image:: ml_crypted_data_correction_35_2.png **Notes** Les coefficients sont en clair mais les données sont cryptées. Pour crypter les coefficients du modèle, il faudrait pouvoir s’assurer que l’addition et la multiplication sont stables après le cryptage. Cela nécessite un cryptage différent comme `Fully Homomorphic Encryption over the Integers `__. Les entiers cryptés sont dans l’intervalle [0, 10000], cela veut dire qu’il est préférable de crypter des entiers dans un intervalle équivalent sous peine de ne pouvoir décrypter avec certitude. Ceci implique que l’algorithme fasse des calculs qui restent dans cet intervalle. C’est pourquoi les entrées et les sorties prennent leur valeur dans l’intervalle [0, 100] afin que le produit *coefficient x entrée* reste dans l’intervalle considéré. Pour éviter ce problème, il faudrait décomposer chaque entier en une séquence d’entiers entre 0 et 100 et réécrire les opérations addition et multiplication en fonction. Questions --------- Le cryptage choisi est moins efficace qu’un cryptage `RSA `__ qui conserve la multiplication. Il faudrait transformer l’écriture du modèle pour utiliser des multiplications plutôt que des additions. Si je vous disais qu’une des variables est l’âge d’une population, vous pourriez la retrouver. Il en est de même pour un chiffrage RSA qui change un entier en un autre. On peut crypter des éléments de ces entiers et les recomposer dans le monde crypté. C’est ce que propose d’autres type de cryptage. **On peut aussi altérer les données en ajoutant un bruit aléatoire qui change peu la prédiction mais qui change la valeur cryptée. Dans ce cas, la distribution de chaque variable paraîtra uniforme.** On peut entraîner un modèle sur des données cryptées si on peut reproduire l’addition et la multiplication avec les nombres cryptés. Une option est le cryptage : `Fully Homomorphic Encryption over the Integers `__. Cela implique qu’on peut approcher toute fonction par un polynôme (voir `développement limité `__). Le gradient d’un polynôme est un polynôme également. Il est possible de calculer la norme du gradient crypté mais pas de la comparer à une autre valeur cryptées. De ce fait les arbres de décision se prêtent mal à ce type d’apprentissage puisque chaque noeud de l’arbre consiste à comparer deux valeurs. Cependant, on peut s’en sortir en imposant à l’algorithme d’apprentissage d’un arbre de décision de ne s’appuyer sur des égalités. Cela nécessite plus de coefficients et la discrétisation des variables continues. Il reste une dernière chose à vérifier. Chaque noeud d’un arbre de décision est déterminé en maximisant une quantité. Comment trouver le maximum dans un ensemble de données cryptées qu’on ne peut comparer ? On utilise une propriété des normes : .. math:: \lim_{d \rightarrow \infty} (x^d + y^d)^{1/d} = \max(x, y) Il existe d’autres options : `Machine Learning Classification over Encrypted Data `__. Ajouter du bruit sur une colonne -------------------------------- Les données peuvent être cryptées mais la distribution est inchangée à une permutation près. Pour éviter cela, on ajoute un peu de bruit, nous allons voir comment faire cela. On suppose que nous avons une colonne qui des entiers distribués selon une loi de Poisson. .. code:: ipython3 from numpy.random import poisson X = poisson(size=10000) mx = X.max()+1 X.min(), mx .. parsed-literal:: (0, 8) .. code:: ipython3 from matplotlib import pyplot as plt plt.hist(X, bins=mx, rwidth=0.9); .. image:: ml_crypted_data_correction_40_0.png .. code:: ipython3 def crypt(x): return compose(x, 5794, 10000) .. code:: ipython3 import numpy Xcrypt = numpy.array([crypt(x) for x in X]) .. code:: ipython3 Xcrypt[:10] .. parsed-literal:: array([ 0, 5794, 5794, 5794, 5794, 0, 7382, 7382, 0, 1588]) .. code:: ipython3 plt.hist(Xcrypt, bins=mx, rwidth=0.9); .. image:: ml_crypted_data_correction_44_0.png Même distribution dans un ordre différent. Pour changer cette distribution, on ajoute un petit bruit peu important pour la variable numérique considérée mais qui sera cryptée de manière totalement différente. .. code:: ipython3 import random Xbruit = numpy.array([100*x + random.randint(0,100) for x in X]) Xbruit[:10] .. parsed-literal:: array([ 90, 145, 120, 172, 131, 76, 343, 398, 17, 288]) .. code:: ipython3 fix, ax = plt.subplots(1, 2, figsize=(12,4)) ax[0].hist(Xbruit, bins=mx, rwidth=0.9) ax[1].hist(Xbruit, bins=mx*100); .. image:: ml_crypted_data_correction_47_0.png .. code:: ipython3 Xbruitcrypt = numpy.array([crypt(x) for x in Xbruit]) .. code:: ipython3 fix, ax = plt.subplots(1, 2, figsize=(12,4)) ax[0].hist(Xbruitcrypt, bins=mx, rwidth=0.9) ax[1].hist(Xbruitcrypt, bins=mx*100); .. image:: ml_crypted_data_correction_49_0.png Le bruit ajouté ne change rien, la nouvelle variable permet de discriminer aussi bien mais il multiplie le nombre de valeurs distinctes. Si chaque valeur est presque unique, l’histogramme de la variable cryptée est quasi-uniforme.