import inspect
import numpy as np
import numba
from sklearn.base import BaseEstimator
from sklearn.utils import check_array
from umap.sparse import arr_intersect as intersect1d
from umap.sparse import arr_union as union1d
from warnings import warn
from umap.umap_ import (
COMPATIBILITY_LAYOUT_DEFAULT_WARNING,
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.bool_)
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()}
def relation_lut(d, n_samples):
"""Materialize a relation dict as a lookup array: lut[key] = value, else -1.
Keys and values are bounded by n_samples (see expand_relations), so an
array of length n_samples covers every entry and turns each dict.get(n, -1)
into a C-level gather instead of a Python-level lookup.
"""
lut = np.full(n_samples, -1, dtype=np.int32)
if d:
keys = np.fromiter(d.keys(), dtype=np.int64, count=len(d))
vals = np.fromiter(d.values(), dtype=np.int64, count=len(d))
lut[keys] = vals
return lut
def chain_relation_lut(lut, mapping):
"""Apply one relation step: mapping[i] -> lut[mapping[i]], propagating -1.
Mirrors `np.array([d.get(n, -1) for n in mapping])` where negative sentinels
(and missing keys) map to -1, but with masked fancy indexing in C.
"""
nxt = np.full(mapping.shape, -1, dtype=np.int32)
valid = mapping >= 0
nxt[valid] = lut[mapping[valid]]
return nxt
@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,
)
# Precompute each relation (and its inverse) as a lookup array once, so the
# windowed chaining below uses C-level gathers instead of Python dict.get.
luts = [relation_lut(d, max_n_samples) for d in relation_dicts]
reverse_luts = [relation_lut(invert_dict(d), max_n_samples) 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, dtype=np.int32)
for k in range(j + 1):
mapping = chain_relation_lut(luts[i + k], 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, dtype=np.int32)
for k in range(0, j - 1, -1):
mapping = chain_relation_lut(reverse_luts[i + k - 1], 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
n_samples = relations.shape[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]
# relations[i, j] is constant across k, so precompute once which
# comparison-model indices appear as values in it. This replaces the
# per-sample set(relations[i, j]) rebuild inside in1d (an
# O(n_samples) cost paid for every k) with an O(degree) membership
# lookup. A value >= n_samples can never appear in relations[i, j],
# so it maps to False, exactly matching in1d's set-membership result.
relation_row = relations[i, j]
present = np.zeros(n_samples, dtype=np.bool_)
for b in range(n_samples):
v = relation_row[b]
if v >= 0:
present[v] = True
for k in range(n_samples):
comparison_index = relation_row[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 = relation_row[
raw_base_graph_indices[raw_base_graph_indices < n_samples]
]
base_indices = base_indices[base_indices >= 0]
comparison_indices = comparison_graph_indices[
comparison_graph_indptr[comparison_index] : comparison_graph_indptr[
comparison_index + 1
]
]
comparison_mask = np.empty(comparison_indices.shape[0], dtype=np.bool_)
for idx in range(comparison_indices.shape[0]):
c = comparison_indices[idx]
if c < n_samples:
comparison_mask[idx] = present[c]
else:
comparison_mask[idx] = False
comparison_indices = comparison_indices[comparison_mask]
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, str):
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",
"nearest_neighbor_backend",
)
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 isinstance(existing_params[param], list):
existing_params[param] = existing_params[param] + [new_params[param]]
elif isinstance(existing_params[param], tuple):
existing_params[param] = existing_params[param] + (new_params[param],)
elif isinstance(existing_params[param], np.ndarray):
existing_params[param] = np.append(
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,
)
[docs]
class AlignedUMAP(BaseEstimator):
"""Jointly embed a sequence of related datasets with aligned UMAP layouts.
Each dataset is modelled with its own UMAP fuzzy graph. The embeddings are
then optimized together, with an additional regularisation term that keeps
related points (given by ``relations`` in :meth:`fit`) close to each other
across neighbouring datasets.
Most parameters have the same meaning as for :class:`umap.UMAP` and may be
given either as a single value or as a list/tuple with one value per
dataset (``n_neighbors``, ``n_epochs``, ``min_dist``, ``spread``,
``learning_rate``, ``repulsion_strength``, ``negative_sample_rate``,
``local_connectivity``, ``set_op_mix_ratio``, ``unique`` and
``nearest_neighbor_backend``).
Parameters
----------
n_neighbors, n_components, metric, metric_kwds, min_dist, spread, \
low_memory, set_op_mix_ratio, local_connectivity, repulsion_strength, \
negative_sample_rate, transform_queue_size, a, b, random_state, \
angular_rp_forest, target_n_neighbors, target_metric, target_metric_kwds, \
target_weight, transform_seed, force_approximation_algorithm, verbose, unique:
As for :class:`umap.UMAP`; used to build each dataset's fuzzy graph.
n_epochs: int or list of int (optional, default None)
Number of optimization epochs. The joint layout runs for the largest
value; ``None`` uses 200.
learning_rate: float or list of float (optional, default 1.0)
Initial learning rate of the aligned optimization.
alignment_regularisation: float (optional, default 1e-2)
Strength of the term that pulls related points together across
neighbouring datasets.
alignment_window_size: int (optional, default 3)
How many neighbouring datasets on each side are regularised towards
each other.
compatibility_layout: bool or None (optional, default None)
Whether to build the per-dataset graphs and spectral initializations
exactly as umap-learn 0.5.x did. ``None`` currently means ``True`` and
emits a ``FutureWarning``; the default will change to ``False`` in a
future release. Seeded ``compatibility_layout=True`` fits reproduce
0.5.x results.
nearest_neighbor_backend: str or list of str (optional, default "auto")
Nearest-neighbor backend for each dataset; see :class:`umap.UMAP`.
init, recursive_coarsening_ratio:
Forwarded to the per-dataset :class:`umap.UMAP` models, but they do
not affect ``embeddings_``: the aligned layout is always initialised
from spectral embeddings and optimized with the established aligned
optimizer. Layout-only options of :class:`umap.UMAP` (``optimizer``,
``init_rescale``, negative-sampling controls and so on) are therefore
not exposed here.
Attributes
----------
embeddings_: list of arrays of shape (n_samples_i, n_components)
The aligned embedding of each dataset.
mappers_: list of UMAP
The fitted per-dataset models providing the fuzzy graphs.
"""
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,
recursive_coarsening_ratio=4,
verbose=False,
unique=False,
nearest_neighbor_backend="auto",
compatibility_layout=None,
):
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.recursive_coarsening_ratio = recursive_coarsening_ratio
self.nearest_neighbor_backend = nearest_neighbor_backend
self.compatibility_layout = compatibility_layout
self.verbose = verbose
self.unique = unique
self.a = a
self.b = b
def __setstate__(self, state):
super().__setstate__(state)
# Fill parameters added after the model was pickled with their defaults;
# fitted pre-0.6 models always used the legacy pipeline.
for name, parameter in inspect.signature(
AlignedUMAP.__init__
).parameters.items():
if name != "self" and name not in self.__dict__:
setattr(self, name, parameter.default)
if "embeddings_" in self.__dict__ and "_compatibility_layout" not in (
self.__dict__
):
self._compatibility_layout = True
def _resolve_compatibility_layout(self):
if self.compatibility_layout is None:
warn(COMPATIBILITY_LAYOUT_DEFAULT_WARNING, FutureWarning, stacklevel=3)
return True
if not isinstance(self.compatibility_layout, (bool, np.bool_)):
raise ValueError("compatibility_layout must be True, False, or None")
return bool(self.compatibility_layout)
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"
)
assert type(fit_params["relations"]) in (list, tuple)
# Copy so that update() does not append to the caller's list
self.dict_relations_ = list(fit_params["relations"])
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._compatibility_layout = self._resolve_compatibility_layout()
if self.n_epochs is None:
self.n_epochs = 200
# n_epochs can be given per model, but the models are laid out together,
# so optimise the joint layout for the largest number of epochs
n_epochs = int(np.max(self.n_epochs))
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),
init=self.init,
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,
recursive_coarsening_ratio=self.recursive_coarsening_ratio,
nearest_neighbor_backend=get_nth_item_or_val(
self.nearest_neighbor_backend, n
),
verbose=self.verbose,
a=self.a,
b=self.b,
compatibility_layout=self._compatibility_layout,
).fit(X[n], y[n])
for n in range(self.n_models_)
]
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_:
graph_coo = mapper.graph_.tocoo()
indptr_list.append(mapper.graph_.indptr)
indices_list.append(mapper.graph_.indices)
heads.append(graph_coo.row)
tails.append(graph_coo.col)
epochs_per_samples.append(make_epochs_per_sample(graph_coo.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,
compatibility_layout=self._compatibility_layout,
)
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,
compatibility_layout=self._compatibility_layout,
)
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"]
assert isinstance(new_dict_relations, dict)
X = check_array(X)
self.__dict__ = set_aligned_params(fit_params, self.__dict__, self.n_models_)
if not hasattr(self, "_compatibility_layout"):
# Models fitted before 0.6 always used the legacy pipeline.
self._compatibility_layout = True
# 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")
if self.n_epochs is None:
self.n_epochs = 200
# The layout update runs for the new model's number of epochs
n_epochs = get_nth_item_or_val(self.n_epochs, self.n_models_)
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_),
init=self.init,
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,
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,
recursive_coarsening_ratio=self.recursive_coarsening_ratio,
nearest_neighbor_backend=get_nth_item_or_val(
self.nearest_neighbor_backend, self.n_models_
),
verbose=self.verbose,
a=self.a,
b=self.b,
compatibility_layout=self._compatibility_layout,
).fit(X, y)
self.n_models_ += 1
self.mappers_ += [new_mapper]
self.dict_relations_ += [new_dict_relations]
window_size = fit_params.get("window_size", self.alignment_window_size)
new_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 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_regularisation_weights = build_neighborhood_similarities(
indptr_list,
indices_list,
new_relations,
)
# TODO: We can likely make this more efficient and not recompute each time
inv_dict_relations = invert_dict(new_dict_relations)
new_embedding = init_from_existing(
self.embeddings_[-1], new_mapper.graph_, inv_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,
)