J'aimerais générer des matrices de taille En fait, je ne me soucie pas de savoir qu'il a rang Lorsque le jeu à portée de main est les réels, je fais ce qui suit, ce qui est parfaitement adéquat pour mes besoins: générer des matrices Si je fais juste cela, puis sur Binaire / 1-5, le rang augmente. Il est également possible d'obtenir une approximation de rang inférieure à une matrice en faisant une SVD et de prendre les valeurs singulières Cette question est liée, mais la réponse acceptée n'est pas" aléatoire "et l'autre réponse suggère SVD, qui ne fonctionne pas ici comme indiqué . Une possibilité que j'ai pensé est de faire (pas que c'est super pertinent, mais je 'M fais cela dans Numpy.) Mise à jour: J'ai essayé l'approche suggérée par EMS dans les commentaires, avec cette simple mise en œuvre: < pré> xxx Il fonctionne rapidement pour les petites matrices mais tombe à part, par exemple 10x10 - Il semble rester coincé au rang 6 ou 7, au moins pour des centaines de milliers d'itérations. On dirait que cela pourrait fonctionner mieux avec une fonction objective meilleure (c'est-à-dire moins plate), mais Je ne sais pas ce que ce soit. J'ai également essayé une méthode de rejet simple pour construire la matrice: Cela fonctionne bien pour par exemple 10x10 matrices binaires avec n'importe quel rang, mais pas pour 0-4 matrices ou binaires beaucoup plus grands avec rang inférieur. (Par exemple, obtenir une matrice binaire 20x20 du rang 15 m'a pris 42 000 rejets; avec 20x20 du rang 10, il a fallu 1,2 million.) Ceci est clairement parce que l'espace renversé par le premier Nous voulons que l'intersection de l'étendue du premier Peut-être que cela peut être formulé en tant que problème de programmation entier, ou quelque chose? m x N et rang r , avec des éléments provenant d'un ensemble fini spécifié, par ex. {0,1} ou {1,2,3,4,5} . Je veux qu'ils soient "aléatoires" dans un sens très lâche de ce mot, c'est-à-dire que je veux obtenir une variété de sorties possibles de l'algorithme avec une distribution vaguement similaire à la distribution de toutes les matrices sur cet ensemble d'éléments avec le rang spécifié. r , juste que c'est ferme à une matrice de rang r ( mesurée par la norme Frobenius). u de Taille m x r et V de n x r , avec des éléments indépendamment échantillonnés par exemple Normal (0, 2). Alors u v ' est un m x matrice du rang r (Eh bien, <= r , mais je pense que c'est r avec une probabilité élevée). r . Ces valeurs, cependant, ne se trouvent pas dans l'ensemble souhaitée et les arrondir augmentera à nouveau le rang. R des vecteurs de ligne ou de colonne indépendants linéairement indépendants de l'ensemble, puis obtenez le reste de la matrice par des combinaisons linéaires de celles-ci. Je ne suis pas vraiment clair, cependant, que ce soit sur la façon d'obtenir des vecteurs "aléatoires" indépendants de manière linéaire, ou comment les combiner de manière quasirogandom après cela.
r Les lignes sont trop petites une partie de l'espace que j'écoule, par exemple {0,1} ^ 10 , dans ces cas. r lignes avec l'ensemble de valides valeurs.
Nous pourrions donc essayer d'échantillonner à partir de la portée et de rechercher des valeurs valides, mais étant donné que la Span implique des coefficients de valeur réelle qui ne nous retrouveront jamais à nous trouver des vecteurs valides (même si nous normalisons, par exemple, le premier composant est dans le jeu valide). < / p>
3 Réponses :
Mon ami, Daniel Johnson, qui a commenté ci-dessus, est venu avec une idée, mais je vois qu'il ne l'a affiché. Il est pas très étoffée, mais vous pourriez être en mesure de l'adapter.
Si
A est m par r etB est r par n et les deux ont rang r puisAB a rang r . Maintenant, nous avons juste à choisirA etB tel queAB a des valeurs que dans l'ensemble donné. Le cas le plus simple estS = {0,1,2, ..., j} .Un choix serait de faire
A binaire avec ligne appropriée des sommes / col qui garanti le rang correct etB avec des sommes de colonnes en ajoutant à pas plus dej (de sorte que chaque terme du produit estS ) et des sommes de rangée choisi au grade causer (ou au moins encourager le rejet peut être utilisé).Je pense juste que nous pouvons trouver deux échantillons indépendants régimes sur
A etB qui sont moins complexes et plus rapide que d'essayer pour attaquer toute la matrice à la fois. Malheureusement, toute ma matrice un code d'échantillonnage est de l'autre ordinateur. Je sais qu'il généralise facilement de permettre des entrées dans un plus grand ensemble que{0,1} (par exempleS ), mais je ne peux pas se rappeler comment le calcul mis à l'échelle avecm * n .
Je ne suis pas sûr de l'utilité de cette solution sera, mais vous pouvez construire une matrice qui vous permettra de rechercher la solution sur une autre matrice avec seulement 0 et 1 entrées. Si vous effectuez une recherche au hasard sur la matrice binaire, il est équivalent à modifier de façon aléatoire les éléments de la matrice finale, mais il est possible de trouver des règles pour faire mieux qu'une recherche aléatoire.
Si vous voulez générer un Il est clair que cette matrice est de rang m . Maintenant, vous pouvez construire une autre matrice, B, qui a 1s à certains endroits pour choisir les éléments de l'ensemble E . La structure de cette matrice est:
Chaque B i est un Si vous souhaitez rechercher un certain rang sur B au hasard, vous devez commencer avec un valide B avec rang maximum, et faites pivoter une colonne aléatoire j de un aléatoire B i d'une quantité aléatoire. Ceci est équivalent à la colonne changer i rangée j de A * B à un élément aléatoire à partir de notre ensemble, de sorte que il n'est pas une méthode très utile.
Cependant, vous pouvez faire certains trucs avec les matrices. Par exemple, si Par exemple, une méthode simple pour générer au maximum rang Une fois que vous créez une matrice qui satisfait la contrainte de rang, vous pouvez vous en sortir avec les traînant au hasard des lignes et des colonnes pour générer d'autres. m -by- n matrice sur l'ensemble des éléments E avec des éléments e i , 0 <= i m -by- k * m matrice, A < / em>:
k -by- n matrice. Ainsi, la taille de A B est m -by- n et rang ( A b ) est min (m, rang ( b )) . Si nous voulons que la matrice de sortie pour avoir seulement des éléments de notre jeu, E , puis chaque colonne de B i doit avoir exactement un ensemble d'éléments 1 , et l'ensemble de repos à 0 .
k est égal à 2, et il n'y a pas de chevauchement sur les premières rangées de B 0 et B 1 < / sub> , vous pouvez générer une ligne linéairement dépendante en ajoutant les premières lignes de ces deux sous-matrices. La deuxième ligne sera également dépendante linéairement sur les lignes de ces deux matrices. Je ne sais pas si cela facilement généralise à k plus grand que 2, mais je suis sûr qu'il y aura d'autres trucs que vous pouvez utiliser.
k (si m est k + 1 ) est d'obtenir un échantillon aléatoire valide B 0 , gardez en rotation toutes les lignes de cette matrice jusqu'à obtenir B 1 B m-2 , régler la première rangée de B m-1 à l'ensemble 1, et les rangées restantes à tous 0. Le rang ne peut pas être inférieur à k (en supposant n > k ), en raison B_0 colonnes ont exactement 1 élément non nul. Les lignes restantes des matrices sont toutes les combinaisons linéaires (en fait des copies exactes pour presque tous les sous-matrices) de ces lignes. La première ligne de la dernière sous-matrice est la somme de toutes les lignes de la première sous-matrice, et les rangées restantes de celui-ci sont tous des zéros. Pour les plus grandes valeurs m , vous pouvez utiliser les permutations de lignes de B 0 au lieu de simple rotation.
Qu'en est-il comme ça?
rank = 30 n1 = 100; n2 = 100 from sklearn.decomposition import NMF model = NMF(n_components=rank, init='random', random_state=0) U = model.fit_transform(np.random.randint(1, 5, size=(n1, n2))) V = model.components_ M = np.around(U) @ np.around(V)
Ceci est une approche intéressante, mais (a) il donne un tas d'éléments qui sont trop grands (pour un run np.bincount (M.astype (int) .ravel ()) donne [1496, 3057, 2973, 1720, 597, 134, 21, 2] , lorsque ce dernier moyen de nombres il y a deux 7 s), et (b) le rang fini par être 29 au lieu de 30.
(Dans tous les cas, je suis un bon six dernières années du projet où je voulais que cela. Mais encore.)
Mmm .. Je vois. Merci pour les commentaires.
Lorsque votre matrice est définie sur des ensembles finis, comme
{0,1} ou{1,2,3,4,5} utilisez-vous également des opérations cohérentes avec Un espace vectoriel sur ces ensembles? Sinon, vous allez avoir des problèmes. (par exemple, vous devriez faire l'arithmétique mod 5 sur les éléments{0,1,2,3,4} pour obtenir un groupe de matrices valide sur cet ensemble. Vous ne pouvez pas utiliser réel -Valée arithmétique et attendez-vous à vos tirages aléatoires, combinaisons linéaires, etc., à fermer.)@Ems Désolé, j'ai oublié de mentionner que j'utilise l'espace vectoriel réel normal. C'est ce que je veux: une matrice sur R mais dont les éléments proviennent de ces ensembles finis. Si je faisais la chose de combinaison linéaire, je devais évidemment faire attention à le faire de manière à ce que les éléments se trouvent toujours dans l'ensemble en question, mais je veux le rang w.r.t. les réels doivent être
r .Je ne pense pas que vous puissiez mélanger et faire correspondre le terrain sous-jacent comme ça. Si la définition de l'indépendance linéaire comprend des coefficients de valeur réelle sur les entrées dans les lignes / colonnes de votre matrice, l'étendue de certaines colonnes peut être énormes sous-ensembles des matrices sur R, et non les matrices sur votre ensemble fini. Si vous traitez les matrices comme si elles doivent être sur cet ensemble fini, vous devez traiter les opérations sur les entrées matricielles d'une manière cohérente avec cet ensemble fini. Vous avez besoin de l'ensemble
{0,1,2,3,4} équipé de sa propre addition et de sa propre multiplication.Clairement des matrices sur R avec des valeurs binaires ou 1-5 des rangs donnés
r existe; J'ai besoin d'un moyen de les générer. Je ne pense pas que je puisse les trouver pour un rang donné par ex.z_5 , car ce n'est pas la même chose:(1,2) et(2,1) est indépendant linéairement sur les réels mais dépendantsz_3 , puisque2 * (1,2) = (2,1) .Pour aggraver les choses, penser à l'affaire binaire n'en aidera pas beaucoup, car il est purement une question de commodité de la chance que des choses telles que
[1, 0] et[0, 1] sont indépendants dans R ^ 2. Par exemple, si vous pensez à la longueur-10 vecteurs de{1,2,3,4,5} , il n'y aura que 5 ^ {10} de tels vecteurs. Il n'y a pas de raison particulière pour laquelle il ne pouvait exister que deux vecteurs à l'intérieur de cet ensemble, dont la portée contient tout le reste des vecteurs, lorsque la portée est prise en fonction de l'arithmétique à valeur réelle.@Ems: si vous le faites sur
{0,1,2,3,4} (qui est parfaitement équivalent à mes fins), alors les vecteurs de base standard e_1 , ..., e_10 est contenu dans l'ensemble de 5 ^ 10 de tels vecteurs, de sorte que vous avez nécessairement besoin de 10 vecteurs pour la couvrir. Bon point, bien que je devrais probablement utiliser 0..4 au lieu de 1..5.Bien sûr, mais c'est parce que vous incluez l'élément zéro du champ sous-jacent. Si vous ne le faites pas, il devient un espace affiné et les choses changent. Donc, simplement en passant à 0, il change tout le teint du sous-espace de manière drastique.
Je pense que des progrès peuvent être faits à ce sujet, mais cela n'est en aucun cas un problème facile. Cela me rappelle les travaux effectués sur des matrices binaires d'échantillonnage avec des sommes de rangée et de colonne fixes, sur lesquelles des documents de recherche hautement considérés sont toujours publiés. Je pense à quels types de multiples de vecteur de votre ensemble fini peuvent éventuellement produire d'autres vecteurs dans l'ensemble fini. Cela dépend de non-trivialement de savoir si les éléments comprennent 0 ou non, qu'ils soient tous divisibles par des nombres communs également dans l'ensemble fini, etc. Je doute qu'une solution facile et rapide à ce sujet existe déjà.
En fait, probablement un très bon moyen d'essayer de goûter ceci est avec l'algorithme de métropole-hastings. Fabriquez une matrice de supposition initiale aléatoire avec des entrées uniquement à partir de votre jeu fini et que, à chaque itération, sélectionnez un endroit aléatoire à modifier (échanger son entrée pour un autre de l'ensemble fini). Computer une certaine mesure du changement qui «mesure» l'indépendance linéaire et accepte le changement proportionnellement à cette mesure. Vous rejetez souvent, mais après beaucoup d'itérations, vous aurez quelque chose d'extrêmement proche de ce que vous voulez.
Évidemment, cela pourrait avoir besoin de modifications. Mais je crois que c'est l'idée derrière les meilleurs algorithmes modernes pour l'échantillonnage des matrices binaires à la matrice fixe.
@EMS Toute suggestion pour une bonne mesure de dépendance linéaire? J'essaie une simple notation de mise en œuvre avec
max (old_rank - new_rank + 1e-4, 0) , mais la fonction objectif est trop plate et par ex. Les matrices binaires 10x10 semblent toujours rester coincées autour de 6 ou 7 pour des dizaines / des centaines de milliers d'itérations (évaluant 20 options par itération).Vous voulez probablement quelque chose comme
exp (-1.0 * abs (actuel_rank - souhaité_rank)) Mais cela pourrait nécessiter des tests.@Ems je ne pense pas ... Le problème est que le rang est trop plat, c'est-à-dire après un certain point, toutes les options ont toujours le même rang et j'ai besoin d'une sorte de mesure qui reconnaîtra des étapes vers un rang inférieur matrice, ou plus grosse étapes plus intelligentes que de perturber un élément de manière aléatoire.
Vous pouvez essayer de faire des propositions qui modifient un groupe d'entrées et que le nombre d'entrées change au fur et à mesure que la fonction de score s'améliore. Ce serait une forme de réchauffage en fonction de l'idée de coûts de recuit simulé. Mais à la fin, il s'agit d'un problème d'optimisation combinatoire, et ils impliquent généralement des paysages de scores lents / lents. Pensez à la recherche de configurations optimales d'atomes ou à la résolution du vendeur de déplacement mondial, avec Metropolis. Il faut un temps loooong, mais dans de nombreux cas, personne ne connaît encore un meilleur échantillonneur. Il est temps de passer à un GPU peut-être de faire de nombreuses autres propositions.
En passant, je devrais aussi dire que c'est de loin l'une des questions les plus utiles sur Stackoverflow que j'ai jamais vues et c'est énormément bien que vous l'avez posée et que vous partageez vos progrès avec des personnes.
Je serais très prudent sur l'utilisation d'une méthode de rejet. Une fois l'acceptation devient un événement rare (ce que cela signifie exactement est vague, mais les ordres de grandeur plus que les rejets acceptations) il y a la règle générale selon laquelle « des événements rares se produiront dans le moins probable de toutes les manières peu probables ». Cela signifie que chaque échantillon peut être très similaire. Peut-être que l'acceptation ne se produira que si le rang est beaucoup plus petit que r, ou quelque chose de similaire. Je suppose que cela dépend du « hasard » que vous recherchez. Des méthodes telles que Metropolis-Hastings devraient gérer ce phénomène de manière appropriée alors qu'une méthode ad hoc ne peut pas.
En outre, une belle façon de caractériser la distribution que vous voulez échantillon à partir est telle que chaque matrice satisfaisant certaines conditions (toutes les entrées sont dans un ensemble et avec le rang r donné par exemple) sont donnés probabilité égale: la répartition uniforme sur cette classe de matrices . Comme indiqué plus haut, cette classe est difficilement descriptible. Il est facile de matrices échantillons avec les entrées d'un ensemble donné et il est facile de matrices échantillons avec un rang donné, mais l'intersection de ces deux classes est faible.