Contexte
Il y a environ 15 ans, j'ai appris l'existence de
chemins fondamentaux - des groupes qui peuvent distinguer les espaces topologiques par la connectivité. Le reste ne sera pas à leur sujet, mais ils ont eu l'idée d'un régresseur et d'un classificateur - sans aucune optimisation basée sur le stockage de l'échantillon.
Plus de détails.
Idées et conjectures
Étant donné que les chemins fondamentaux sont des boucles à partir d'un point sélectionné et leur équivalence, comment trouver de telles boucles dans les données? Et est-ce nécessaire?
L'idée est venue par analogie avec KNN et SVM - des algorithmes "analogues". Que se passe-t-il si la boucle est remplacée par un «tuyau», un cylindre d'un point de données à un autre, et que ce qui tombe dans le tuyau est affecté à la même classe que ces deux points du chemin (qui ne sont plus fondamentaux)? Le «tuyau» doit être d'une largeur suffisante pour classer correctement les classes ... et à la limite c'est une ligne droite. La distance jusqu'à un nouveau point inconnu doit être minimale en cours de route, nous pouvons alors l'attribuer à la même classe que le chemin.
Un régresseur peut être construit en projetant un point sur une ligne droite entre des points de données et en interpolant des valeurs cibles correspondant à des points de données avec le même rapport dans lequel la projection divise le chemin.
Cette méthode de construction se souvient de l'ensemble de l'échantillon et fournit des prévisions précises sur l'ensemble d'entraînement.
Implémentation primitive
Comment construire un chemin? J'ai pris l'élément maximum selon la norme, et j'ai commencé à chercher le plus proche de lui, en connectant le chemin reçu. En fin de compte - fermé avec le début (discutable bien sûr, mais comme ça).
EstimateurCeci est la toute première version du code, voir le cahier mis à jour ci-dessous.class PathMachine(BaseEstimator): def __init__(self, norm=np.linalg.norm, classify=False): self.norm = norm self.classify = classify def find_start(self, X): index_max = None value_max = -np.inf for index, x in enumerate(X): value = self.norm(x) if value > value_max: index_max = index value_max = value return index_max def find_next(self, point, target, X, y): index_min = None value_min = np.inf for index, x in enumerate(X): if self.classify and (y[index] != target): continue value = self.norm(x - point) if value < value_min: index_min = index value_min = value return index_min def fit(self, X, y): X = np.copy(X) y = np.copy(y).flatten() self.paths = {} if self.classify else [] start_index = self.find_start(X) start_value = X[start_index] start_target = y[start_index] X = np.delete(X, start_index, axis=0) y = np.delete(y, start_index, axis=0) while len(X) > 0: next_index = self.find_next(start_value, start_target, X, y) if self.classify and next_index is None: start_index = self.find_start(X) start_value = X[start_index] start_target = y[start_index] continue next_target = y[next_index] if self.classify: if not next_target in self.paths: self.paths[next_target] = [] self.paths[next_target].append({ 'start': start_value, 'next': X[next_index] }) else: self.paths.append({ 'start': start_value, 'next': X[next_index], 'value': start_target, 'target': next_target }) start_value = X[next_index] start_target = y[next_index] X = np.delete(X, next_index, axis=0) y = np.delete(y, next_index, axis=0) if self.classify: self.paths[start_target].append({ 'start': start_value, 'next': self.paths[start_target][0]['start'] }) else: self.paths.append({ 'start': start_value, 'next': self.paths[0]['start'], 'value': start_target, 'target': self.paths[0]['target'] }) return self def predict(self, X): result = [] for x in X: if self.classify: predicted = None min_distance = np.inf for target in self.paths: for path in self.paths[target]: point = x - path['start'] line = path['next'] - path['start'] if np.allclose(self.norm(line), 0): continue direction = line / self.norm(line) product = np.dot(point, direction) projection = product * direction distance = self.norm(projection - point) if distance < min_distance: predicted = target min_distance = distance result.append(predicted) else: predicted = None min_distance = np.inf for path in self.paths: point = x - path['start'] line = path['next'] - path['start'] if np.allclose(self.norm(line), 0): continue direction = line / self.norm(line) product = np.dot(point, direction) projection = product * direction parameter = np.sign(product) * self.norm(projection) /\ self.norm(line) distance = self.norm(projection - point) if distance < min_distance: predicted = (1 - parameter) * path['value'] +\ parameter * path['target'] min_distance = distance result.append(predicted) return np.array(result) def score(self, X, y): if self.classify: return f1_score(y.flatten(), self.predict(X), average='micro') else: return r2_score(y.flatten(), self.predict(X))
Théoriquement (et techniquement), il est possible de faire predict_proba de la même manière - comme 1 - distances normalisées. Mais je n'ai pas eu l'occasion de vraiment tester les probabilités, alors ...
Quelques tests
J'ai commencé avec le classique Boston Housing and Iris, et pour la ligne de base, j'ai choisi Ridge et LogisticRegression. Eh bien, et si.
En général, je suggère de regarder le
cahier jupyter .
En bref: le régresseur fonctionnait moins bien, le classificateur fonctionnait mieux.
mise à jour: après StandardScaler, le régresseur fonctionnait mieux.J'ai également roulé sur des jeux de données synthétiques. Il y a généralement quelque chose dans la forêt, c'est du bois de chauffage.
Mais cela a été remarqué:
- Le régresseur fonctionne bien dans les espaces de petites dimensions,
- Le régresseur et le classifieur sont tous deux sensibles au bruit, à partir d'un certain seuil,
- Le régresseur, contrairement à la ligne, soupçonne la multimodalité (dans Boston Housing),
- Par construction, le classificateur a bien fonctionné (le meilleur de tous ... :)) sur un ensemble de lunes linéairement inséparables.
Conclusions, avantages, inconvénients et applicabilité
Personnellement, je ne vois aucun avantage dans la mise en œuvre actuelle. Techniquement et mathématiquement. Peut-être que cela peut être modifié en quelque chose de plus sensé. Par conséquent, je ne vois aucune application particulière non plus. Est-il possible de travailler avec de très petites données sans prétraitement ...
Il existe de nombreux inconvénients: il est nécessaire de conserver l'ensemble de données en mémoire, la capacité de généralisation est basée sur l'extrapolation, le seul et principal hyperparamètre - la norme - ne se prête pas à une énumération-sélection spéciale.
Mais, de toute façon, pour moi, la réception a été une surprise, que j'ai décidé de partager ici.