Как стать автором
Обновить

Path Machine: идея одного алгоритма

Время на прочтение 4 мин
Количество просмотров 3.1K

Предыстория


Лет 15 назад я узнал о существовании фундаментальных путей — групп, которые могут различать топологические пространства по связности. Дальше будет не о них, но они натолкнули на идею регрессора и классификатора — без всяких оптимизаций, основанного на запоминании выборки.

Далее подробнее.

Идеи и домыслы


Поскольку фундаментальные пути — это петли из выбранной точки, и эквивалентность на них, то как можно найти такие петли в данных? И надо ли?

Идея пришла по аналогии с KNN и SVM — «аналогисткими» алгоритмами. Что если петлю заменить на «трубу», цилиндр из одной данных точки в другую, и то, что попало в трубу — относить к тому же классу что и эти две точки пути (уже не фундаментального)? «Труба» должна быть такой ширины, чтобы правильно относить классы… и в пределе — это прямая. Расстояние до новой, неизвестной точки должно быть минимальным в пути, тогда мы сможем отнести её к тому же классу, что и путь.



Регрессор можно построить по проекции точки на прямую между точками данных, и интерполировать соответствующие точкам данных целевые значения тем же соотношением, в котором проекция делит путь.

Этот способ по построению запоминает всю выборку и выдает точные предсказания на тренировочном множестве.

Примитивная реализация


Как построить путь? Я взял максимальный по норме элемент, и стал искать ближайший к нему, соединяя получил путь. В конце — замкнул с началом (спорно конечно, но вот так).

Estimator
Это самая первая версия кода, смотрите ниже обновленный notebook.

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))


Теоретически (и технически), возможно так же сделать и predict_proba — как 1 — отнормированные расстояния. Но как вероятности толком протестировать я сходу не придумал, поэтому…

Некоторые тесты


Начал я с классических Boston Housing и Iris, и за baseline выбрал Ridge и LogisticRegression. Ну а что, а вдруг.

Вообще, предлагаю посмотреть jupyter notebook.

Вкратце: регрессор сработал хуже, классификатор сработал лучше.
update: после StandardScaler, регрессор заработал лучше.

Покатал я также и на синтетических датасетах. Там вообще что в лес, что дрова.

Но было подмечено вот что:

  1. Регрессор неплохо работает на пространствах малых размерностей,
  2. И регрессор, и классификатор — чувствительны к шумам, начиная с некоторого порога,
  3. Регрессор, в отличие от линейки, заподозрил мультимодальность (в Boston Housing),
  4. По построению, классификатор хорошо отработал (лучше всех...:)) на линейно неразделимом множестве moons.

Выводы, плюсы-минусы и применимость


Плюсов лично я не особо вижу в текущей реализации. Как технически, так и математически. Возможно, это можно доработать до чего-то более толкового. Соответственно и применимости особой тоже не вижу. Разве что без препроцессинга работать с очень малыми данными…

Минусов много: требуется держать весь датасет в памяти, обобщающая способность построена на экстраполяции, основной и единственный гиперпараметр — норма — не поддается особым подборам-переборам.

Но, так или иначе, для меня полученное было сюрпризом, чем и я решил здесь поделиться.
Теги:
Хабы:
+3
Комментарии 12
Комментарии Комментарии 12

Публикации

Истории

Работа

Data Scientist
66 вакансий

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн