[PYTHON] Essayez de décomposer la procession du daimyo en Tucker

introduction

L'algèbre linéaire a une opération appelée décomposition de singularité, qui est utilisée pour approcher la matrice. Pour plus de détails, reportez-vous à la section «Essayez la décomposition en valeurs singulières de la matrice daimyo».

Maintenant, une matrice est comme un tableau à deux dimensions dans un programme. Vous pouvez obtenir la valeur d'un tableau à deux dimensions en spécifiant deux index. De même, une matrice peut spécifier des éléments en spécifiant deux index, ligne et colonne. Un tenseur est une extension d'une matrice à un tableau multidimensionnel. Il est très difficile de discuter sérieusement des tenseurs, mais dans cet article, il est normal de le considérer comme un «tableau multidimensionnel».

Maintenant, comme la matrice, il est nécessaire d'approcher le tenseur. Dans le cas d'une matrice, la décomposition de singularité était la meilleure approximation (au sens de la norme de Frobenius), mais on ne comprend pas bien comment approcher un tenseur général [^ 1]. La décomposition qui divise un tenseur en un petit tenseur (tenseur du noyau) et un ensemble de matrices correspondant à chaque mode est appelée décomposition de Tucker. Dans ce qui précède, j'ai pensé que l'image monochrome était une matrice telle quelle et je l'ai décomposée en valeurs singulières, mais dans cet article, je pense que l'image couleur est un tenseur du troisième ordre et je la décompose par Tucker. Plusieurs algorithmes pour obtenir la décomposition de Tucker ont été proposés, mais dans cet article, nous présenterons l'algorithme le plus simple appelé SVD d'ordre supérieur (HOSVD), qui utilise docilement la décomposition en valeurs singulières.

[^ 1]: Il y a peut-être une théorie générale, mais je ne sais pas.

TODO: télécharger le code sur GitHub

Démontage Tucker

Avant d'expliquer la décomposition de Tucker, je vais résumer les termes, matrices et représentations graphiques des tenseurs utilisés dans cet article [^ 2]. L'indice d'une matrice ou d'un tenseur est appelé un "pied". La procession a deux jambes. Ce nombre de lignes et de colonnes est appelé la "dimension" du pied. Notez que dans les tableaux multidimensionnels, le "nombre de jambes" est appelé la dimension, mais dans les matrices et les tenseurs, le "type de valeurs qui peuvent être indexées" est appelé la dimension.

[^ 2]: Je ne suis pas très familier avec cela, alors sachez que ce qui suit peut avoir une notation non industrielle.

Une matrice ou un tenseur est représenté par un "carré" avec des "lignes". La «ligne» est le pied. La procession a deux jambes et le tenseur du troisième étage a trois jambes. Si vous souhaitez clarifier la dimension de chaque pied, écrivez-la à côté.

À propos, la chose la plus importante dans la représentation graphique est le fonctionnement des lignes de connexion. Vous pouvez créer une nouvelle matrice en additionnant les jambes qui ont les mêmes dimensions. Par exemple, une matrice peut être le produit d'une matrice m-par-n et d'une matrice n-par-1, résultant en une matrice m-par-1. Exprimer cela avec des carrés et des lignes ressemble à ceci.

Même avec des tenseurs, vous pouvez écraser ces jambes pour créer un nouveau tenseur en additionnant les jambes qui ont la même dimension. Dans la représentation graphique, vous connectez vos jambes comme une matrice. Le tenseur résultant est un tenseur avec les dimensions de chaque jambe, avec le nombre de jambes restantes comme le nombre d'étages.

Désormais, les données d'image couleur peuvent être représentées par un tableau tridimensionnel avec trois index: hauteur, largeur et couleur. Considérez cela comme un tenseur à trois jambes et essayez de l'approcher par décomposition de singularité. Généralement, la décomposition de Tucker se rapproche de toutes les jambes, mais cette fois, comme il n'y a que 3 dimensions de jambes "couleur", nous approcherons seulement les jambes "hauteur" et "largeur".

À l'origine, un tenseur à trois branches de hauteur h, largeur w et couleur c est séparé en un produit d'un tenseur et de deux matrices. Le tenseur central est appelé le "tenseur du noyau", et dans ce cas il a des pattes colorées et des pattes reliées aux matrices gauche et droite par la dimension r. Les matrices gauche et droite ont des jambes de hauteur h et des jambes de dimension r, des jambes de largeur w et des jambes de dimension r, respectivement, et r est la jambe qui "transmet l'information". La décomposition de Tucker compresse les informations en réduisant la dimension de r. Essayons ci-dessous.

Faire une image d'une procession de daimyo

Commençons par créer une image de la procession du daimyo cible. La dernière fois je l'ai fait en monochrome, mais cette fois je vais faire une image couleur. Les quatre lettres sont respectivement jaune (R, G, 0), cyan (0, G, B), magenta (R, 0, B) et blanc (R, G), de sorte que la couleur "saignement" due à l'approximation puisse être facilement comprise. Colorions avec, B). Est-ce que c'est comme ça? La police est installée pour Google Colab en cours de route et le chemin de la police est spécifié, mais si vous utilisez un autre environnement, veuillez le corriger en conséquence.

from PIL import Image, ImageDraw, ImageFont
import numpy as np
from scipy import linalg
from IPython.display import display
!apt-get -y install fonts-ipafont-gothic
fpath='/usr/share/fonts/opentype/ipafont-gothic/ipagp.ttf'
fontsize = 50
font = ImageFont.truetype(fpath, fontsize)
LX = 200
LY = fontsize
img  = Image.new('RGB', (LX,LY),color="black")
draw = ImageDraw.Draw(img)
draw.text((0,0), "Gros", fill=(255,255,0), font=font)
draw.text((0,0), "Nom", fill=(0,255,255), font=font)
draw.text((0,0), "ligne", fill=(255,0,255), font=font)
draw.text((0,0), "Colonne", fill="white", font=font)
img

Une fois exécutée, une telle image sera créée.

Récupérons les données de l'image.

data = np.array(img.getdata()).reshape(LY,LX,3)

Vous pouvez considérer «data» comme un tableau tridimensionnel, un tenseur avec trois jambes, chacune avec trois dimensions: hauteur LY, largeur LX et couleur. La tâche de cet article est d'approcher cela. Avant cela, jetons un coup d'œil à chacun des plans RVB.

R = data[:,:,0]
G = data[:,:,1]
B = data[:,:,2]
display(Image.fromarray(np.uint8(R)))
display(Image.fromarray(np.uint8(G)))
display(Image.fromarray(np.uint8(B)))

Si vous regardez le monde de R uniquement, le monde de G uniquement et le monde de B uniquement, il manque une lettre à chacun. De plus, comme la «colonne» est blanche, elle ne sera pas ébréchée.

Décomposition de singularité

Tout d'abord, créons une fonction qui décompose les valeurs singulières. Voir ci-dessus pour plus de détails. Une fonction qui prend une matrice et retourne deux matrices proches l'une de l'autre à un rang donné ressemblerait à ceci:

def perform_svd(X, rank):
  U, s, V = linalg.svd(X)
  Ur = U[:, :rank]
  Sr = np.diag(np.sqrt(s[:rank]))
  Vr = V[:rank, :]
  A = Ur @ Sr
  B = Sr @ Vr
  return A, B

Si vous insérez la matrice «X», deux matrices «A, B» seront renvoyées. Vous pouvez obtenir une approximation de rang bas de «X» par «rang» en calculant «A @ B».

Approximation Tensol

Maintenant, approchons le tenseur, mais comme c'est un gros problème, essayons différentes méthodes d'approximation.

Décomposition de valeurs singulières pensant qu'il s'agit d'une matrice de force

Cette fois, le tenseur mesure 50 en hauteur, 200 en largeur et 3 en couleur. Le nombre d'éléments est de 30 000. Ignorez complètement la structure d'origine, considérez-la comme une matrice de 200 * 150, décomposez-la en valeurs singulières et approchez-la. Sera-ce une telle fonction?

def simple_image(X, rank):
  X = data.reshape((200,150))
  A, B = perform_svd(X, rank)
  Y = (A @ B).reshape(LY,LX,3)
  Y = np.clip(Y, 0, 255)
  Y = np.uint8(Y)
  print((A.size+B.size)/X.size)
  return Image.fromarray(Y)

Le résultat de l'exécution ressemble à ceci.

display(simple_image(data, 50))
display(simple_image(data, 21))
display(simple_image(data, 8))

Le taux de compression des données est également affiché. Du haut sont 58,3%, 24,5% et 9,3%. C'est la somme du nombre d'éléments de A et B divisée par le nombre d'éléments de X lorsque la matrice 200 * 150 X est divisée en deux matrices A et B. Malgré la méthode très approximative, la structure originale reste telle qu'elle est.

Décomposition de singularité du plan RVB

La méthode précédente ignorait à l'origine complètement les trois structures de hauteur, largeur et couleur. Considérons maintenant un peu la structure originale. Un moyen simple d'approximer le tenseur qui exprime une image couleur consiste à considérer les plans R, V et B comme une «matrice», à les décomposer en valeurs singulières, puis à les combiner. Faisons le.

def rgb_svd(X, rank):
  R = X[:,:,0]
  G = X[:,:,1]
  B = X[:,:,2]
  Rh, Rw = perform_svd(R, rank)
  Gh, Gw = perform_svd(G, rank)
  Bh, Bw = perform_svd(B, rank)
  return Rh, Rw, Gh, Gw, Bh, Bw

Le tenseur «X» est séparé en une matrice représentant le plan RVB, R est séparé en Rh et Rw, G est séparé en Gh et Gw, et B est séparé en Bh et Bw, respectivement. Si vous faites Rh @ Rw, le plan R sera restauré, donc si vous restaurez les plans G et B de la même manière, l'image d'origine sera restaurée. La restauration d'image ressemblera à ceci.

def rgb_image(X, rank):
  Rh, Rw, Gh, Gw, Bh, Bw = rgb_svd(X, rank)
  R = Rh @ Rw
  G = Gh @ Gw
  B = Bh @ Bw
  Y = np.asarray([R,G,B]).transpose(1,2,0)
  Y = np.clip(Y, 0, 255)
  Y = np.uint8(Y)
  print((Rh.size+Rw.size)*3/X.size)
  return Image.fromarray(Y)

Lançons-le.

display(rgb_image(data, 50))
display(rgb_image(data, 10))
display(rgb_image(data, 4))

Les taux de compression sont de 125%, 25% et 10% à partir du haut. La décomposition de singularité peut avoir plus d'éléments que les données d'origine si la valeur de rang à gauche est grande. Pour les deux autres, j'ai essayé de faire correspondre le taux de compression avec la méthode approximative que j'ai mentionnée plus tôt. Je pensais que l'approximation serait meilleure car la structure était prise en considération, mais elle était étonnamment mauvaise.

Démontage Tucker

Décomposons maintenant le sujet principal de Tucker. Voir aussi Approximation de bas rang des images par décomposition de Tucker pour le principe de la décomposition de Tucker. Cette fonction divise le tenseur à trois pattes «X» en le tenseur de noyau «C» et les matrices gauche et droite «U» et «V».

def tucker_decomposition(X, rank):
  X = X.transpose(0,2,1)
  XR = X.reshape(LY*3, LX)
  _, _, V = linalg.svd(XR)
  V = V[:rank,:]
  Vt = V.transpose(1,0)
  XL = X.reshape(LY, LX*3)
  U, _, _ = linalg.svd(XL)
  U = U[:,:rank]
  Ut = U.transpose(1,0)
  # Make a core tensor
  UX = np.tensordot(Ut, X, (1,0))
  C = np.tensordot(UX, Vt, (2, 0))
  return U, C, V

Une fonction qui restaure une image à partir d'une matrice et d'un tenseur désassemblés ressemble à ceci.

def tucker_image(X, rank):
  U, C, V = tucker_decomposition(X, rank)
  UC = np.tensordot(U,C,(1,0))
  Y = np.tensordot(UC, V, (2,0))
  Y = Y.transpose((0,2,1))
  Y = np.clip(Y, 0, 255)
  Y = np.uint8(Y)
  print((U.size+C.size+V.size)/X.size)
  return Image.fromarray(Y)

Lançons-le.

display(tucker_image(data, 50))
display(tucker_image(data, 23))
display(tucker_image(data, 10))

Les taux de compression sont de 66,7%, 24,5% et 9,3% à partir du haut. C'est clairement mieux que la décomposition de valeur singulière pour chaque RVB, mais est-ce une comparaison subtile avec la méthode approximative?

Sommaire

J'ai pensé que l'image couleur "Daimyo Matrix" était un tenseur à trois pattes, et j'ai essayé de compresser les informations en utilisant une décomposition de valeurs singulières. Il était surprenant qu'il soit préférable de décomposer de force tout le plan RVB en valeurs singulières plutôt que de les décomposer chacune en valeurs singulières. Contrairement au cas des matrices, l'approximation tenseur n'est pas très explicite quant à ce qu'il faut faire. J'espère que vous allez essayer ce code et penser: "Je vois, l'approximation de bas rang de Tensol est profonde."

Matériel complémentaire

TODO: écrivez une description de l'algorithme de décomposition de Tucker dans cet article.