#516

pending completion

Build # #516

Build Type

push

coveralls-python

Committed by

web-flow

Commit Message

<a href="https://github.com/lmcinnes/umap/commit/<a class=hub.com/lmcinnes/umap/commit/0d36c0f67ec6b34c723ed10e3bc9bc6ceada61bf">0d36c0f67<a href="https://github.com/lmcinnes/umap/commit/0d36c0f67ec6b34c723ed10e3bc9bc6ceada61bf">">Merge </a><a class="double-link" href="https://github.com/lmcinnes/umap/commit/<a class="double-link" href="https://github.com/lmcinnes/umap/commit/9f6f2569171ae8330ca9100e00f32c6882499440">9f6f25691</a>">9f6f25691</a><a href="https://github.com/lmcinnes/umap/commit/0d36c0f67ec6b34c723ed10e3bc9bc6ceada61bf"> into 1bc1f3169">1bc1f3169</a>

Run Details

6 of 6 new or added lines in 3 files covered. (100.0%)

4198 of 4798 relevant lines covered (87.49%)

0.87 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.28

/umap/aligned_umap.py

import numpy as np
import numba
from sklearn.base import BaseEstimator
from sklearn.utils import check_random_state, check_array

from umap.sparse import arr_intersect as intersect1d
from umap.sparse import arr_union as union1d
from umap.umap_ import UMAP, make_epochs_per_sample
from umap.spectral import spectral_layout
from umap.layouts import optimize_layout_aligned_euclidean

INT32_MIN = np.iinfo(np.int32).min + 1
INT32_MAX = np.iinfo(np.int32).max - 1


@numba.njit(parallel=True)
def in1d(arr, test_set):
    test_set = set(test_set)
    result = np.empty(arr.shape[0], dtype=np.uint8)
    for i in numba.prange(arr.shape[0]):
        if arr[i] in test_set:
            result[i] = True
        else:
            result[i] = False

    return result


def invert_dict(d):
    return {value: key for key, value in d.items()}


@numba.njit()
def procrustes_align(embedding_base, embedding_to_align, anchors):
    subset1 = embedding_base[anchors[0]]
    subset2 = embedding_to_align[anchors[1]]
    M = subset2.T @ subset1
    U, S, V = np.linalg.svd(M)
    R = U @ V
    return embedding_to_align @ R


def expand_relations(relation_dicts, window_size=3):
    max_n_samples = (
        max(
            [max(d.keys()) for d in relation_dicts]
            + [max(d.values()) for d in relation_dicts]
        )
        + 1
    )
    result = np.full(
        (len(relation_dicts) + 1, 2 * window_size + 1, max_n_samples),
        -1,
        dtype=np.int32,
    )
    reverse_relation_dicts = [invert_dict(d) for d in relation_dicts]
    for i in range(result.shape[0]):
        for j in range(window_size):
            result_index = (window_size) + (j + 1)
            if i + j + 1 >= len(relation_dicts):
                result[i, result_index] = np.full(max_n_samples, -1, dtype=np.int32)
            else:
                mapping = np.arange(max_n_samples)
                for k in range(j + 1):
                    mapping = np.array(
                        [relation_dicts[i + j].get(n, -1) for n in mapping]
                    )
                result[i, result_index] = mapping

        for j in range(0, -window_size, -1):
            result_index = (window_size) + (j - 1)
            if i + j - 1 < 0:
                result[i, result_index] = np.full(max_n_samples, -1, dtype=np.int32)
            else:
                mapping = np.arange(max_n_samples)
                for k in range(np.abs(j) + 1):
                    mapping = np.array(
                        [reverse_relation_dicts[i + j - 1].get(n, -1) for n in mapping]
                    )
                result[i, result_index] = mapping

    return result


@numba.njit()
def build_neighborhood_similarities(graphs_indptr, graphs_indices, relations):
    result = np.zeros(relations.shape, dtype=np.float32)
    center_index = (relations.shape[1] - 1) // 2
    for i in range(relations.shape[0]):
        base_graph_indptr = graphs_indptr[i]
        base_graph_indices = graphs_indices[i]
        for j in range(relations.shape[1]):
            if i + j - center_index < 0 or i + j - center_index >= len(graphs_indptr):
                continue

            comparison_graph_indptr = graphs_indptr[i + j - center_index]
            comparison_graph_indices = graphs_indices[i + j - center_index]
            for k in range(relations.shape[2]):
                comparison_index = relations[i, j, k]
                if comparison_index < 0:
                    continue

                raw_base_graph_indices = base_graph_indices[
                    base_graph_indptr[k] : base_graph_indptr[k + 1]
                ].copy()
                base_indices = relations[i, j][raw_base_graph_indices]
                base_indices = base_indices[base_indices >= 0]
                comparison_indices = comparison_graph_indices[
                    comparison_graph_indptr[comparison_index] : comparison_graph_indptr[
                        comparison_index + 1
                    ]
                ]
                comparison_indices = comparison_indices[
                    in1d(comparison_indices, relations[i, j])
                ]

                intersection_size = intersect1d(base_indices, comparison_indices).shape[
                    0
                ]
                union_size = union1d(base_indices, comparison_indices).shape[0]

                if union_size > 0:
                    result[i, j, k] = intersection_size / union_size
                else:
                    result[i, j, k] = 1.0

    return result


def get_nth_item_or_val(iterable_or_val, n):
    if iterable_or_val is None:
        return None
    if type(iterable_or_val) in (list, tuple, np.ndarray):
        return iterable_or_val[n]
    elif type(iterable_or_val) in (int, float, bool, None):
        return iterable_or_val
    else:
        raise ValueError("Unrecognized parameter type")


PARAM_NAMES = (
    "n_neighbors",
    "n_components",
    "metric",
    "metric_kwds",
    "n_epochs",
    "learning_rate",
    "init",
    "min_dist",
    "spread",
    "set_op_mix_ratio",
    "local_connectivity",
    "repulsion_strength",
    "negative_sample_rate",
    "transform_queue_size",
    "angular_rp_forest",
    "target_n_neighbors",
    "target_metric",
    "target_metric_kwds",
    "target_weight",
    "unique",
)


def set_aligned_params(new_params, existing_params, n_models, param_names=PARAM_NAMES):
    for param in param_names:
        if param in new_params:
            if type(existing_params[param]) in (list, tuple, np.ndarray):
                existing_params[param] = existing_params[param] + (new_params[param],)
            else:
                if new_params[param] != existing_params[param]:
                    existing_params[param] = (existing_params[param],) * n_models + (
                        new_params[param],
                    )

    return existing_params


@numba.njit()
def init_from_existing_internal(
    previous_embedding, weights_indptr, weights_indices, weights_data, relation_dict
):
    n_samples = weights_indptr.shape[0] - 1
    n_features = previous_embedding.shape[1]
    result = np.zeros((n_samples, n_features), dtype=np.float32)

    for i in range(n_samples):
        if i in relation_dict:
            result[i] = previous_embedding[relation_dict[i]]
        else:
            normalisation = 0.0
            for idx in range(weights_indptr[i], weights_indptr[i + 1]):
                j = weights_indices[idx]
                if j in relation_dict:
                    normalisation += weights_data[idx]
                    result[i] += (
                        weights_data[idx] * previous_embedding[relation_dict[j]]
                    )
            if normalisation == 0:
                result[i] = np.random.uniform(-10.0, 10.0, n_features)
            else:
                result[i] /= normalisation

    return result


def init_from_existing(previous_embedding, graph, relations):
    typed_relations = numba.typed.Dict.empty(numba.types.int32, numba.types.int32)
    for key, val in relations.items():
        typed_relations[np.int32(key)] = np.int32(val)
    return init_from_existing_internal(
        previous_embedding,
        graph.indptr,
        graph.indices,
        graph.data,
        typed_relations,
    )


class AlignedUMAP(BaseEstimator):
    def __init__(
        self,
        n_neighbors=15,
        n_components=2,
        metric="euclidean",
        metric_kwds=None,
        n_epochs=None,
        learning_rate=1.0,
        init="spectral",
        alignment_regularisation=1.0e-2,
        alignment_window_size=3,
        min_dist=0.1,
        spread=1.0,
        low_memory=False,
        set_op_mix_ratio=1.0,
        local_connectivity=1.0,
        repulsion_strength=1.0,
        negative_sample_rate=5,
        transform_queue_size=4.0,
        a=None,
        b=None,
        random_state=None,
        angular_rp_forest=False,
        target_n_neighbors=-1,
        target_metric="categorical",
        target_metric_kwds=None,
        target_weight=0.5,
        transform_seed=42,
        force_approximation_algorithm=False,
        verbose=False,
        unique=False,
    ):

        self.n_neighbors = n_neighbors
        self.metric = metric
        self.metric_kwds = metric_kwds

        self.n_epochs = n_epochs
        self.init = init
        self.n_components = n_components
        self.repulsion_strength = repulsion_strength
        self.learning_rate = learning_rate
        self.alignment_regularisation = alignment_regularisation
        self.alignment_window_size = alignment_window_size

        self.spread = spread
        self.min_dist = min_dist
        self.low_memory = low_memory
        self.set_op_mix_ratio = set_op_mix_ratio
        self.local_connectivity = local_connectivity
        self.negative_sample_rate = negative_sample_rate
        self.random_state = random_state
        self.angular_rp_forest = angular_rp_forest
        self.transform_queue_size = transform_queue_size
        self.target_n_neighbors = target_n_neighbors
        self.target_metric = target_metric
        self.target_metric_kwds = target_metric_kwds
        self.target_weight = target_weight
        self.transform_seed = transform_seed
        self.force_approximation_algorithm = force_approximation_algorithm
        self.verbose = verbose
        self.unique = unique

        self.a = a
        self.b = b

    def fit(self, X, y=None, **fit_params):
        if "relations" not in fit_params:
            raise ValueError(
                "Aligned UMAP requires relations between data to be " "specified"
            )

        self.dict_relations_ = fit_params["relations"]
        assert type(self.dict_relations_) in (list, tuple)
        assert type(X) in (list, tuple, np.ndarray)
        assert (len(X) - 1) == (len(self.dict_relations_))

        if y is not None:
            assert type(y) in (list, tuple, np.ndarray)
            assert (len(y) - 1) == (len(self.dict_relations_))
        else:
            y = [None] * len(X)

        # We need n_components to be constant or this won't work
        if type(self.n_components) in (list, tuple, np.ndarray):
            raise ValueError("n_components must be a single integer, and cannot vary")

        self.n_models_ = len(X)

        self.mappers_ = [
            UMAP(
                n_neighbors=get_nth_item_or_val(self.n_neighbors, n),
                min_dist=get_nth_item_or_val(self.min_dist, n),
                n_epochs=get_nth_item_or_val(self.n_epochs, n),
                repulsion_strength=get_nth_item_or_val(self.repulsion_strength, n),
                learning_rate=get_nth_item_or_val(self.learning_rate, n),
                spread=get_nth_item_or_val(self.spread, n),
                negative_sample_rate=get_nth_item_or_val(self.negative_sample_rate, n),
                local_connectivity=get_nth_item_or_val(self.local_connectivity, n),
                set_op_mix_ratio=get_nth_item_or_val(self.set_op_mix_ratio, n),
                unique=get_nth_item_or_val(self.unique, n),
                n_components=self.n_components,
                metric=self.metric,
                metric_kwds=self.metric_kwds,
                low_memory=self.low_memory,
                random_state=self.random_state,
                angular_rp_forest=self.angular_rp_forest,
                transform_queue_size=self.transform_queue_size,
                target_n_neighbors=self.target_n_neighbors,
                target_metric=self.target_metric,
                target_metric_kwds=self.target_metric_kwds,
                target_weight=self.target_weight,
                transform_seed=self.transform_seed,
                force_approximation_algorithm=self.force_approximation_algorithm,
                verbose=self.verbose,
                a=self.a,
                b=self.b,
            ).fit(X[n], y[n])
            for n in range(self.n_models_)
        ]

        if self.n_epochs is None:
            n_epochs = 200
        else:
            n_epochs = self.n_epochs

        window_size = fit_params.get("window_size", self.alignment_window_size)
        relations = expand_relations(self.dict_relations_, window_size)

        indptr_list = numba.typed.List.empty_list(numba.types.int32[::1])
        indices_list = numba.typed.List.empty_list(numba.types.int32[::1])
        heads = numba.typed.List.empty_list(numba.types.int32[::1])
        tails = numba.typed.List.empty_list(numba.types.int32[::1])
        epochs_per_samples = numba.typed.List.empty_list(numba.types.float64[::1])

        for mapper in self.mappers_:
            indptr_list.append(mapper.graph_.indptr)
            indices_list.append(mapper.graph_.indices)
            heads.append(mapper.graph_.tocoo().row)
            tails.append(mapper.graph_.tocoo().col)
            epochs_per_samples.append(
                make_epochs_per_sample(mapper.graph_.tocoo().data, n_epochs)
            )

        rng_state_transform = np.random.RandomState(self.transform_seed)
        regularisation_weights = build_neighborhood_similarities(
            indptr_list,
            indices_list,
            relations,
        )
        first_init = spectral_layout(
            self.mappers_[0]._raw_data,
            self.mappers_[0].graph_,
            self.n_components,
            rng_state_transform,
        )
        expansion = 10.0 / np.abs(first_init).max()
        first_embedding = (first_init * expansion).astype(
            np.float32,
            order="C",
        )

        embeddings = numba.typed.List.empty_list(numba.types.float32[:, ::1])
        embeddings.append(first_embedding)
        for i in range(1, self.n_models_):
            next_init = spectral_layout(
                self.mappers_[i]._raw_data,
                self.mappers_[i].graph_,
                self.n_components,
                rng_state_transform,
            )
            expansion = 10.0 / np.abs(next_init).max()
            next_embedding = (next_init * expansion).astype(
                np.float32,
                order="C",
            )
            anchor_data = relations[i][window_size - 1]
            left_anchors = anchor_data[anchor_data >= 0]
            right_anchors = np.where(anchor_data >= 0)[0]
            embeddings.append(
                procrustes_align(
                    embeddings[-1],
                    next_embedding,
                    np.vstack([left_anchors, right_anchors]),
                )
            )

        seed_triplet = rng_state_transform.randint(INT32_MIN, INT32_MAX, 3).astype(
            np.int64
        )
        self.embeddings_ = optimize_layout_aligned_euclidean(
            embeddings,
            embeddings,
            heads,
            tails,
            n_epochs,
            epochs_per_samples,
            regularisation_weights,
            relations,
            seed_triplet,
            lambda_=self.alignment_regularisation,
            move_other=True,
        )

        for i, embedding in enumerate(self.embeddings_):
            disconnected_vertices = (
                np.array(self.mappers_[i].graph_.sum(axis=1)).flatten() == 0
            )
            embedding[disconnected_vertices] = np.full(self.n_components, np.nan)

        return self

    def fit_transform(self, X, y=None, **fit_params):
        self.fit(X, y, **fit_params)
        return self.embeddings_

    def update(self, X, y=None, **fit_params):
        if "relations" not in fit_params:
            raise ValueError(
                "Aligned UMAP requires relations between data to be " "specified"
            )

        new_dict_relations = fit_params["relations"]
        X = check_array(X)

        self.__dict__ = set_aligned_params(fit_params, self.__dict__, self.n_models_)
        self.n_models_ += 1

        new_mapper = UMAP(
            n_neighbors=get_nth_item_or_val(self.n_neighbors, self.n_models_),
            min_dist=get_nth_item_or_val(self.min_dist, self.n_models_),
            n_epochs=get_nth_item_or_val(self.n_epochs, self.n_models_),
            repulsion_strength=get_nth_item_or_val(
                self.repulsion_strength, self.n_models_
            ),
            learning_rate=get_nth_item_or_val(self.learning_rate, self.n_models_),
            spread=get_nth_item_or_val(self.spread, self.n_models_),
            negative_sample_rate=get_nth_item_or_val(
                self.negative_sample_rate, self.n_models_
            ),
            local_connectivity=get_nth_item_or_val(
                self.local_connectivity, self.n_models_
            ),
            set_op_mix_ratio=get_nth_item_or_val(self.set_op_mix_ratio, self.n_models_),
            unique=get_nth_item_or_val(self.unique, self.n_models_),
            n_components=self.n_components,
            random_state=self.random_state,
            transform_seed=self.transform_seed,
        ).fit(X, y)

        self.mappers_ += [new_mapper]

        # TODO: We can likely make this more efficient and not recompute each time
        self.dict_relations_ += [invert_dict(new_dict_relations)]

        if self.n_epochs is None:
            n_epochs = 200
        else:
            n_epochs = self.n_epochs

        indptr_list = numba.typed.List.empty_list(numba.types.int32[::1])
        indices_list = numba.typed.List.empty_list(numba.types.int32[::1])
        heads = numba.typed.List.empty_list(numba.types.int32[::1])
        tails = numba.typed.List.empty_list(numba.types.int32[::1])
        epochs_per_samples = numba.typed.List.empty_list(numba.types.float64[::1])

        for i, mapper in enumerate(self.mappers_):
            indptr_list.append(mapper.graph_.indptr)
            indices_list.append(mapper.graph_.indices)
            heads.append(mapper.graph_.tocoo().row)
            tails.append(mapper.graph_.tocoo().col)
            if i == len(self.mappers_) - 1:
                epochs_per_samples.append(
                    make_epochs_per_sample(mapper.graph_.tocoo().data, n_epochs)
                )
            else:
                epochs_per_samples.append(
                    np.full(mapper.embedding_.shape[0], n_epochs + 1, dtype=np.float64)
                )

        new_relations = expand_relations(self.dict_relations_)
        new_regularisation_weights = build_neighborhood_similarities(
            indptr_list,
            indices_list,
            new_relations,
        )

        new_embedding = init_from_existing(
            self.embeddings_[-1], new_mapper.graph_, new_dict_relations
        )

        self.embeddings_.append(new_embedding)

        rng_state_transform = np.random.RandomState(self.transform_seed)
        seed_triplet = rng_state_transform.randint(INT32_MIN, INT32_MAX, 3).astype(
            np.int64
        )
        self.embeddings_ = optimize_layout_aligned_euclidean(
            self.embeddings_,
            self.embeddings_,
            heads,
            tails,
            n_epochs,
            epochs_per_samples,
            new_regularisation_weights,
            new_relations,
            seed_triplet,
            lambda_=self.alignment_regularisation,
        )

1	import numpy as np	1✔
2	import numba	1✔
3	from sklearn.base import BaseEstimator	1✔
4	from sklearn.utils import check_random_state, check_array	1✔
5
6	from umap.sparse import arr_intersect as intersect1d	1✔
7	from umap.sparse import arr_union as union1d	1✔
8	from umap.umap_ import UMAP, make_epochs_per_sample	1✔
9	from umap.spectral import spectral_layout	1✔
10	from umap.layouts import optimize_layout_aligned_euclidean	1✔
11
12	INT32_MIN = np.iinfo(np.int32).min + 1	1✔
13	INT32_MAX = np.iinfo(np.int32).max - 1	1✔
14
15
16	@numba.njit(parallel=True)	1✔
17	def in1d(arr, test_set):	1✔
18	test_set = set(test_set)	1✔
19	result = np.empty(arr.shape[0], dtype=np.uint8)	1✔
20	for i in numba.prange(arr.shape[0]):	1✔
21	if arr[i] in test_set:	1✔
22	result[i] = True	1✔
23	else:
24	result[i] = False	1✔
25
26	return result	1✔
27
28
29	def invert_dict(d):	1✔
30	return {value: key for key, value in d.items()}	1✔
31
32
33	@numba.njit()	1✔
34	def procrustes_align(embedding_base, embedding_to_align, anchors):	1✔
35	subset1 = embedding_base[anchors[0]]	1✔
36	subset2 = embedding_to_align[anchors[1]]	1✔
37	M = subset2.T @ subset1	1✔
38	U, S, V = np.linalg.svd(M)	1✔
39	R = U @ V	1✔
40	return embedding_to_align @ R	1✔
41
42
43	def expand_relations(relation_dicts, window_size=3):	1✔
44	max_n_samples = (	1✔
45	max(
46	[max(d.keys()) for d in relation_dicts]
47	+ [max(d.values()) for d in relation_dicts]
48	)
49	+ 1
50	)
51	result = np.full(	1✔
52	(len(relation_dicts) + 1, 2 * window_size + 1, max_n_samples),
53	-1,
54	dtype=np.int32,
55	)
56	reverse_relation_dicts = [invert_dict(d) for d in relation_dicts]	1✔
57	for i in range(result.shape[0]):	1✔
58	for j in range(window_size):	1✔
59	result_index = (window_size) + (j + 1)	1✔
60	if i + j + 1 >= len(relation_dicts):	1✔
61	result[i, result_index] = np.full(max_n_samples, -1, dtype=np.int32)	1✔
62	else:
63	mapping = np.arange(max_n_samples)	1✔
64	for k in range(j + 1):	1✔
65	mapping = np.array(	1✔
66	[relation_dicts[i + j].get(n, -1) for n in mapping]
67	)
68	result[i, result_index] = mapping	1✔
69
70	for j in range(0, -window_size, -1):	1✔
71	result_index = (window_size) + (j - 1)	1✔
72	if i + j - 1 < 0:	1✔
73	result[i, result_index] = np.full(max_n_samples, -1, dtype=np.int32)	1✔
74	else:
75	mapping = np.arange(max_n_samples)	1✔
76	for k in range(np.abs(j) + 1):	1✔
77	mapping = np.array(	1✔
78	[reverse_relation_dicts[i + j - 1].get(n, -1) for n in mapping]
79	)
80	result[i, result_index] = mapping	1✔
81
82	return result	1✔
83
84
85	@numba.njit()	1✔
86	def build_neighborhood_similarities(graphs_indptr, graphs_indices, relations):	1✔
87	result = np.zeros(relations.shape, dtype=np.float32)	1✔
88	center_index = (relations.shape[1] - 1) // 2	1✔
89	for i in range(relations.shape[0]):	1✔
90	base_graph_indptr = graphs_indptr[i]	1✔
91	base_graph_indices = graphs_indices[i]	1✔
92	for j in range(relations.shape[1]):	1✔
93	if i + j - center_index < 0 or i + j - center_index >= len(graphs_indptr):	1✔
94	continue	1✔
95
96	comparison_graph_indptr = graphs_indptr[i + j - center_index]	1✔
97	comparison_graph_indices = graphs_indices[i + j - center_index]	1✔
98	for k in range(relations.shape[2]):	1✔
99	comparison_index = relations[i, j, k]	1✔
100	if comparison_index < 0:	1✔
101	continue	1✔
102
103	raw_base_graph_indices = base_graph_indices[	1✔
104	base_graph_indptr[k] : base_graph_indptr[k + 1]
105	].copy()
106	base_indices = relations[i, j][raw_base_graph_indices]	1✔
107	base_indices = base_indices[base_indices >= 0]	1✔
108	comparison_indices = comparison_graph_indices[	1✔
109	comparison_graph_indptr[comparison_index] : comparison_graph_indptr[
110	comparison_index + 1
111	]
112	]
113	comparison_indices = comparison_indices[	1✔
114	in1d(comparison_indices, relations[i, j])
115	]
116
117	intersection_size = intersect1d(base_indices, comparison_indices).shape[	1✔
118	0
119	]
120	union_size = union1d(base_indices, comparison_indices).shape[0]	1✔
121
122	if union_size > 0:	1✔
123	result[i, j, k] = intersection_size / union_size	1✔
124	else:
125	result[i, j, k] = 1.0	×
126
127	return result	1✔
128
129
130	def get_nth_item_or_val(iterable_or_val, n):	1✔
131	if iterable_or_val is None:	1✔
132	return None	1✔
133	if type(iterable_or_val) in (list, tuple, np.ndarray):	1✔
134	return iterable_or_val[n]	×
135	elif type(iterable_or_val) in (int, float, bool, None):	1✔
136	return iterable_or_val	1✔
137	else:
138	raise ValueError("Unrecognized parameter type")	×
139
140
141	PARAM_NAMES = (	1✔
142	"n_neighbors",
143	"n_components",
144	"metric",
145	"metric_kwds",
146	"n_epochs",
147	"learning_rate",
148	"init",
149	"min_dist",
150	"spread",
151	"set_op_mix_ratio",
152	"local_connectivity",
153	"repulsion_strength",
154	"negative_sample_rate",
155	"transform_queue_size",
156	"angular_rp_forest",
157	"target_n_neighbors",
158	"target_metric",
159	"target_metric_kwds",
160	"target_weight",
161	"unique",
162	)
163
164
165	def set_aligned_params(new_params, existing_params, n_models, param_names=PARAM_NAMES):	1✔
166	for param in param_names:	1✔
167	if param in new_params:	1✔
168	if type(existing_params[param]) in (list, tuple, np.ndarray):	×
169	existing_params[param] = existing_params[param] + (new_params[param],)	×
170	else:
171	if new_params[param] != existing_params[param]:	×
172	existing_params[param] = (existing_params[param],) * n_models + (	×
173	new_params[param],
174	)
175
176	return existing_params	1✔
177
178
179	@numba.njit()	1✔
180	def init_from_existing_internal(	1✔
181	previous_embedding, weights_indptr, weights_indices, weights_data, relation_dict
182	):
183	n_samples = weights_indptr.shape[0] - 1	1✔
184	n_features = previous_embedding.shape[1]	1✔
185	result = np.zeros((n_samples, n_features), dtype=np.float32)	1✔
186
187	for i in range(n_samples):	1✔
188	if i in relation_dict:	1✔
189	result[i] = previous_embedding[relation_dict[i]]	1✔
190	else:
191	normalisation = 0.0	1✔
192	for idx in range(weights_indptr[i], weights_indptr[i + 1]):	1✔
193	j = weights_indices[idx]	1✔
194	if j in relation_dict:	1✔
195	normalisation += weights_data[idx]	1✔
196	result[i] += (	1✔
197	weights_data[idx] * previous_embedding[relation_dict[j]]
198	)
199	if normalisation == 0:	1✔
200	result[i] = np.random.uniform(-10.0, 10.0, n_features)	1✔
201	else:
202	result[i] /= normalisation	1✔
203
204	return result	1✔
205
206
207	def init_from_existing(previous_embedding, graph, relations):	1✔
208	typed_relations = numba.typed.Dict.empty(numba.types.int32, numba.types.int32)	1✔
209	for key, val in relations.items():	1✔
210	typed_relations[np.int32(key)] = np.int32(val)	1✔
211	return init_from_existing_internal(	1✔
212	previous_embedding,
213	graph.indptr,
214	graph.indices,
215	graph.data,
216	typed_relations,
217	)
218
219
220	class AlignedUMAP(BaseEstimator):	1✔
221	def __init__(	1✔
222	self,
223	n_neighbors=15,
224	n_components=2,
225	metric="euclidean",
226	metric_kwds=None,
227	n_epochs=None,
228	learning_rate=1.0,
229	init="spectral",
230	alignment_regularisation=1.0e-2,
231	alignment_window_size=3,
232	min_dist=0.1,
233	spread=1.0,
234	low_memory=False,
235	set_op_mix_ratio=1.0,
236	local_connectivity=1.0,
237	repulsion_strength=1.0,
238	negative_sample_rate=5,
239	transform_queue_size=4.0,
240	a=None,
241	b=None,
242	random_state=None,
243	angular_rp_forest=False,
244	target_n_neighbors=-1,
245	target_metric="categorical",
246	target_metric_kwds=None,
247	target_weight=0.5,
248	transform_seed=42,
249	force_approximation_algorithm=False,
250	verbose=False,
251	unique=False,
252	):
253
254	self.n_neighbors = n_neighbors	1✔
255	self.metric = metric	1✔
256	self.metric_kwds = metric_kwds	1✔
257
258	self.n_epochs = n_epochs	1✔
259	self.init = init	1✔
260	self.n_components = n_components	1✔
261	self.repulsion_strength = repulsion_strength	1✔
262	self.learning_rate = learning_rate	1✔
263	self.alignment_regularisation = alignment_regularisation	1✔
264	self.alignment_window_size = alignment_window_size	1✔
265
266	self.spread = spread	1✔
267	self.min_dist = min_dist	1✔
268	self.low_memory = low_memory	1✔
269	self.set_op_mix_ratio = set_op_mix_ratio	1✔
270	self.local_connectivity = local_connectivity	1✔
271	self.negative_sample_rate = negative_sample_rate	1✔
272	self.random_state = random_state	1✔
273	self.angular_rp_forest = angular_rp_forest	1✔
274	self.transform_queue_size = transform_queue_size	1✔
275	self.target_n_neighbors = target_n_neighbors	1✔
276	self.target_metric = target_metric	1✔
277	self.target_metric_kwds = target_metric_kwds	1✔
278	self.target_weight = target_weight	1✔
279	self.transform_seed = transform_seed	1✔
280	self.force_approximation_algorithm = force_approximation_algorithm	1✔
281	self.verbose = verbose	1✔
282	self.unique = unique	1✔
283
284	self.a = a	1✔
285	self.b = b	1✔
286
287	def fit(self, X, y=None, **fit_params):	1✔
288	if "relations" not in fit_params:	1✔
289	raise ValueError(	×
290	"Aligned UMAP requires relations between data to be " "specified"
291	)
292
293	self.dict_relations_ = fit_params["relations"]	1✔
294	assert type(self.dict_relations_) in (list, tuple)	1✔
295	assert type(X) in (list, tuple, np.ndarray)	1✔
296	assert (len(X) - 1) == (len(self.dict_relations_))	1✔
297
298	if y is not None:	1✔
299	assert type(y) in (list, tuple, np.ndarray)	×
300	assert (len(y) - 1) == (len(self.dict_relations_))	×
301	else:
302	y = [None] * len(X)	1✔
303
304	# We need n_components to be constant or this won't work
305	if type(self.n_components) in (list, tuple, np.ndarray):	1✔
306	raise ValueError("n_components must be a single integer, and cannot vary")	×
307
308	self.n_models_ = len(X)	1✔
309
310	self.mappers_ = [	1✔
311	UMAP(
312	n_neighbors=get_nth_item_or_val(self.n_neighbors, n),
313	min_dist=get_nth_item_or_val(self.min_dist, n),
314	n_epochs=get_nth_item_or_val(self.n_epochs, n),
315	repulsion_strength=get_nth_item_or_val(self.repulsion_strength, n),
316	learning_rate=get_nth_item_or_val(self.learning_rate, n),
317	spread=get_nth_item_or_val(self.spread, n),
318	negative_sample_rate=get_nth_item_or_val(self.negative_sample_rate, n),
319	local_connectivity=get_nth_item_or_val(self.local_connectivity, n),
320	set_op_mix_ratio=get_nth_item_or_val(self.set_op_mix_ratio, n),
321	unique=get_nth_item_or_val(self.unique, n),
322	n_components=self.n_components,
323	metric=self.metric,
324	metric_kwds=self.metric_kwds,
325	low_memory=self.low_memory,
326	random_state=self.random_state,
327	angular_rp_forest=self.angular_rp_forest,
328	transform_queue_size=self.transform_queue_size,
329	target_n_neighbors=self.target_n_neighbors,
330	target_metric=self.target_metric,
331	target_metric_kwds=self.target_metric_kwds,
332	target_weight=self.target_weight,
333	transform_seed=self.transform_seed,
334	force_approximation_algorithm=self.force_approximation_algorithm,
335	verbose=self.verbose,
336	a=self.a,
337	b=self.b,
338	).fit(X[n], y[n])
339	for n in range(self.n_models_)
340	]
341
342	if self.n_epochs is None:	1✔
343	n_epochs = 200	1✔
344	else:
345	n_epochs = self.n_epochs	×
346
347	window_size = fit_params.get("window_size", self.alignment_window_size)	1✔
348	relations = expand_relations(self.dict_relations_, window_size)	1✔
349
350	indptr_list = numba.typed.List.empty_list(numba.types.int32[::1])	1✔
351	indices_list = numba.typed.List.empty_list(numba.types.int32[::1])	1✔
352	heads = numba.typed.List.empty_list(numba.types.int32[::1])	1✔
353	tails = numba.typed.List.empty_list(numba.types.int32[::1])	1✔
354	epochs_per_samples = numba.typed.List.empty_list(numba.types.float64[::1])	1✔
355
356	for mapper in self.mappers_:	1✔
357	indptr_list.append(mapper.graph_.indptr)	1✔
358	indices_list.append(mapper.graph_.indices)	1✔
359	heads.append(mapper.graph_.tocoo().row)	1✔
360	tails.append(mapper.graph_.tocoo().col)	1✔
361	epochs_per_samples.append(	1✔
362	make_epochs_per_sample(mapper.graph_.tocoo().data, n_epochs)
363	)
364
365	rng_state_transform = np.random.RandomState(self.transform_seed)	1✔
366	regularisation_weights = build_neighborhood_similarities(	1✔
367	indptr_list,
368	indices_list,
369	relations,
370	)
371	first_init = spectral_layout(	1✔
372	self.mappers_[0]._raw_data,
373	self.mappers_[0].graph_,
374	self.n_components,
375	rng_state_transform,
376	)
377	expansion = 10.0 / np.abs(first_init).max()	1✔
378	first_embedding = (first_init * expansion).astype(	1✔
379	np.float32,
380	order="C",
381	)
382
383	embeddings = numba.typed.List.empty_list(numba.types.float32[:, ::1])	1✔
384	embeddings.append(first_embedding)	1✔
385	for i in range(1, self.n_models_):	1✔
386	next_init = spectral_layout(	1✔
387	self.mappers_[i]._raw_data,
388	self.mappers_[i].graph_,
389	self.n_components,
390	rng_state_transform,
391	)
392	expansion = 10.0 / np.abs(next_init).max()	1✔
393	next_embedding = (next_init * expansion).astype(	1✔
394	np.float32,
395	order="C",
396	)
397	anchor_data = relations[i][window_size - 1]	1✔
398	left_anchors = anchor_data[anchor_data >= 0]	1✔
399	right_anchors = np.where(anchor_data >= 0)[0]	1✔
400	embeddings.append(	1✔
401	procrustes_align(
402	embeddings[-1],
403	next_embedding,
404	np.vstack([left_anchors, right_anchors]),
405	)
406	)
407
408	seed_triplet = rng_state_transform.randint(INT32_MIN, INT32_MAX, 3).astype(	1✔
409	np.int64
410	)
411	self.embeddings_ = optimize_layout_aligned_euclidean(	1✔
412	embeddings,
413	embeddings,
414	heads,
415	tails,
416	n_epochs,
417	epochs_per_samples,
418	regularisation_weights,
419	relations,
420	seed_triplet,
421	lambda_=self.alignment_regularisation,
422	move_other=True,
423	)
424
425	for i, embedding in enumerate(self.embeddings_):	1✔
426	disconnected_vertices = (	1✔
427	np.array(self.mappers_[i].graph_.sum(axis=1)).flatten() == 0
428	)
429	embedding[disconnected_vertices] = np.full(self.n_components, np.nan)	1✔
430
431	return self	1✔
432
433	def fit_transform(self, X, y=None, **fit_params):	1✔
434	self.fit(X, y, **fit_params)	×
435	return self.embeddings_	×
436
437	def update(self, X, y=None, **fit_params):	1✔
438	if "relations" not in fit_params:	1✔
439	raise ValueError(	×
440	"Aligned UMAP requires relations between data to be " "specified"
441	)
442
443	new_dict_relations = fit_params["relations"]	1✔
444	X = check_array(X)	1✔
445
446	self.__dict__ = set_aligned_params(fit_params, self.__dict__, self.n_models_)	1✔
447	self.n_models_ += 1	1✔
448
449	new_mapper = UMAP(	1✔
450	n_neighbors=get_nth_item_or_val(self.n_neighbors, self.n_models_),
451	min_dist=get_nth_item_or_val(self.min_dist, self.n_models_),
452	n_epochs=get_nth_item_or_val(self.n_epochs, self.n_models_),
453	repulsion_strength=get_nth_item_or_val(
454	self.repulsion_strength, self.n_models_
455	),
456	learning_rate=get_nth_item_or_val(self.learning_rate, self.n_models_),
457	spread=get_nth_item_or_val(self.spread, self.n_models_),
458	negative_sample_rate=get_nth_item_or_val(
459	self.negative_sample_rate, self.n_models_
460	),
461	local_connectivity=get_nth_item_or_val(
462	self.local_connectivity, self.n_models_
463	),
464	set_op_mix_ratio=get_nth_item_or_val(self.set_op_mix_ratio, self.n_models_),
465	unique=get_nth_item_or_val(self.unique, self.n_models_),
466	n_components=self.n_components,
467	random_state=self.random_state,
468	transform_seed=self.transform_seed,
469	).fit(X, y)
470
471	self.mappers_ += [new_mapper]	1✔
472
473	# TODO: We can likely make this more efficient and not recompute each time
474	self.dict_relations_ += [invert_dict(new_dict_relations)]	1✔
475
476	if self.n_epochs is None:	1✔
477	n_epochs = 200	1✔
478	else:
479	n_epochs = self.n_epochs	×
480
481	indptr_list = numba.typed.List.empty_list(numba.types.int32[::1])	1✔
482	indices_list = numba.typed.List.empty_list(numba.types.int32[::1])	1✔
483	heads = numba.typed.List.empty_list(numba.types.int32[::1])	1✔
484	tails = numba.typed.List.empty_list(numba.types.int32[::1])	1✔
485	epochs_per_samples = numba.typed.List.empty_list(numba.types.float64[::1])	1✔
486
487	for i, mapper in enumerate(self.mappers_):	1✔
488	indptr_list.append(mapper.graph_.indptr)	1✔
489	indices_list.append(mapper.graph_.indices)	1✔
490	heads.append(mapper.graph_.tocoo().row)	1✔
491	tails.append(mapper.graph_.tocoo().col)	1✔
492	if i == len(self.mappers_) - 1:	1✔
493	epochs_per_samples.append(	1✔
494	make_epochs_per_sample(mapper.graph_.tocoo().data, n_epochs)
495	)
496	else:
497	epochs_per_samples.append(	1✔
498	np.full(mapper.embedding_.shape[0], n_epochs + 1, dtype=np.float64)
499	)
500
501	new_relations = expand_relations(self.dict_relations_)	1✔
502	new_regularisation_weights = build_neighborhood_similarities(	1✔
503	indptr_list,
504	indices_list,
505	new_relations,
506	)
507
508	new_embedding = init_from_existing(	1✔
509	self.embeddings_[-1], new_mapper.graph_, new_dict_relations
510	)
511
512	self.embeddings_.append(new_embedding)	1✔
513
514	rng_state_transform = np.random.RandomState(self.transform_seed)	1✔
515	seed_triplet = rng_state_transform.randint(INT32_MIN, INT32_MAX, 3).astype(	1✔
516	np.int64
517	)
518	self.embeddings_ = optimize_layout_aligned_euclidean(	1✔
519	self.embeddings_,
520	self.embeddings_,
521	heads,
522	tails,
523	n_epochs,
524	epochs_per_samples,
525	new_regularisation_weights,
526	new_relations,
527	seed_triplet,
528	lambda_=self.alignment_regularisation,
529	)

lmcinnes / umap / #516

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous