Antecedentes
Há cerca de 15 anos, aprendi sobre a existência de
caminhos fundamentais - grupos que podem distinguir espaços topológicos pela conectividade. O resto não será sobre eles, mas eles tiveram a ideia de um regressor e um classificador - sem nenhuma otimização baseada no armazenamento da amostra.
Mais detalhes.
Ideias e conjecturas
Como os caminhos fundamentais são loops a partir de um ponto selecionado e a equivalência entre eles, como esses loops podem ser encontrados nos dados? E isso é necessário?
A idéia surgiu por analogia com KNN e SVM - algoritmos "análogos". E se o loop for substituído por um "pipe", um cilindro de um ponto de dados para outro, e o que caiu no pipe for atribuído à mesma classe que esses dois pontos do caminho (não é mais fundamental)? O "tubo" deve ter uma largura que permita classificar corretamente as classes ... e, no limite, é uma linha reta. A distância para um ponto novo e desconhecido deve ser mínima ao longo do caminho, então podemos atribuí-lo à mesma classe que o caminho.
Um regressor pode ser construído projetando um ponto em uma linha reta entre os pontos de dados e interpolando os valores-alvo correspondentes aos pontos de dados com a mesma proporção na qual a projeção divide o caminho.
Esse método de construção lembra toda a amostra e fornece previsões precisas sobre o conjunto de treinamento.
Implementação primitiva
Como construir um caminho? Peguei o elemento máximo de acordo com a norma e comecei a procurar o mais próximo dele, conectando o caminho recebido. No final - fechado com o começo (discutível, é claro, mas assim).
EstimadorEsta é a primeira versão do código, veja o bloco de notas atualizado abaixo.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))
Teoricamente (e tecnicamente), é possível fazer o prog_proba da mesma maneira - como 1 - distâncias normalizadas. Mas não tive a chance de testar realmente as probabilidades, então ...
Alguns testes
Comecei com o clássico Boston Housing and Iris e, para a linha de base, escolhi Ridge e LogisticRegression. Bem, o que, e se.
Em geral, sugiro olhar para o
notebook jupyter .
Em resumo: o regressor funcionou pior, o classificador funcionou melhor.
atualização: após o StandardScaler, o regressor funcionou melhor.Eu também montei em conjuntos de dados sintéticos. Geralmente, há algo na floresta, que é lenha.
Mas isso foi notado:
- O regressor funciona bem em espaços de pequenas dimensões,
- Tanto o regressor quanto o classificador são sensíveis ao ruído, começando em um certo limite,
- Ao contrário da linha, o regressor suspeitava de multimodalidade (em Boston Housing),
- Por construção, o classificador funcionou bem (o melhor de tudo ... :)) em um conjunto de luas linearmente inseparáveis.
Conclusões, Prós, Contras e Aplicabilidade
Pessoalmente, não vejo vantagens na implementação atual. Técnica e matematicamente. Talvez isso possa ser modificado para algo mais sensato. Portanto, também não vejo nenhuma aplicabilidade específica. É possível trabalhar com dados muito pequenos sem pré-processamento ...
Existem muitas desvantagens: é necessário manter todo o conjunto de dados na memória, a capacidade de generalização se baseia na extrapolação, o principal e único hiperparâmetro - a norma - não é passível de enumeração de seleção especial.
Mas, enfim, para mim o recebimento foi uma surpresa, que resolvi compartilhar aqui.