Edit on GitHub

starplast.optimize

Searching the space of maps, rather than enumerating it.

search.search walks a grid. A grid is honest and it does not scale: adding t-SNE, four clustering algorithms and HDBSCAN's real parameters takes the existing sweep from a few hundred configurations to a few hundred thousand, at ten seconds each. The space has to be searched rather than listed.

Why hill climbing and not gradient descent

There is no gradient. The score is "how much biology does this configuration find", which runs an embedding and a clustering and a pile of statistics to produce one number -- it is not differentiable in min_cluster_size, and half the coordinates are categorical (which blocks, which algorithm), where a derivative is not merely unavailable but undefined.

What IS available is that the space is mostly SMOOTH IN THE ORDINAL COORDINATES: 25 neighbours and 30 neighbours give similar maps, and if 30 beat 25 then 40 is worth trying before 5 is. That is the property hill climbing exploits, and it is the honest analogue of following a gradient here -- take a step along one coordinate, keep it if the score improved, and give up on that coordinate when it does not. Categorical coordinates are enumerated instead, which is what "no gradient" means in practice.

Two things are added because plain hill climbing has two known failures.

Restarts. A hill climber finds the top of whatever hill it started on. Several starts from different corners of the space, keeping the best, is the cheapest defence and the standard one.

Caching. The neighbourhoods of successive steps overlap heavily, and the same configuration is proposed over and over. Every evaluation is stored under its own key, so the second visit is free -- which in practice roughly halves a run. The embedding is cached separately from the clustering, because most steps change only the clustering and re-running UMAP for those would be the whole cost of the search for none of the information.

What it optimises

Whatever it is told to. evaluator builds the three that matter: recovery of a held-out label (the old objective, which measures trust), guilt by association, and layer disagreement (the two from discovery, which measure yield). They pull in different directions and are meant to -- a map tuned until it recovers compartment perfectly is often a map that has found nothing new, and seeing that trade-off is the point of being able to optimise for either.

SPACE = {'method': ['umap', 'tsne', 'pca'], 'scaling': ['rank', 'robust', 'zscore'], 'n_components': [2, 3], 'n_neighbors': [5, 10, 15, 25, 40, 60, 100], 'min_dist': [0.0, 0.05, 0.1, 0.25, 0.5, 0.8], 'perplexity': [5.0, 15.0, 30.0, 50.0, 80.0], 'algorithm': ['hdbscan', 'kmeans', 'agglomerative', 'dbscan'], 'min_cluster_size': [5, 10, 15, 25, 40, 60, 100, 150], 'min_samples': [None, 3, 5, 10, 20], 'cluster_selection_epsilon': [0.0, 0.1, 0.25, 0.5, 1.0], 'cluster_selection_method': ['eom', 'leaf'], 'n_clusters': [6, 10, 15, 25, 40, 60], 'linkage': ['ward', 'average', 'complete'], 'eps': [0.25, 0.5, 0.75, 1.0, 1.5]}

ORDINAL = {'n_clusters', 'min_samples', 'n_neighbors', 'cluster_selection_epsilon', 'eps', 'min_dist', 'perplexity', 'min_cluster_size', 'n_components'}

EMBEDDING_KEYS = ('blocks', 'method', 'scaling', 'n_components', 'n_neighbors', 'min_dist', 'perplexity')

RELEVANT = {'n_neighbors': <function <lambda>>, 'min_dist': <function <lambda>>, 'perplexity': <function <lambda>>, 'min_cluster_size': <function <lambda>>, 'cluster_selection_epsilon': <function <lambda>>, 'cluster_selection_method': <function <lambda>>, 'min_samples': <function <lambda>>, 'eps': <function <lambda>>, 'n_clusters': <function <lambda>>, 'linkage': <function <lambda>>}

def key(config: dict) -> tuple:

A configuration reduced to what actually affects the answer, for the cache.

Irrelevant coordinates are dropped rather than included: with min_dist in the key, a t-SNE at min_dist 0.1 and the same t-SNE at 0.5 are two cache entries for one computation, and the cache stops working exactly when the search starts moving between methods.

def spec_of(config: dict, seed: int = 42) -> starplast.embedding.EmbeddingSpec:

The embedding half of a configuration, as a recipe.

def cluster_kw(config: dict) -> dict:

The clustering half, as keyword arguments clustering.cluster understands.

def neighbours(config: dict, space: dict = None, block_pool=()) -> list:

Every configuration one step from this one.

One step means one coordinate moved by one place along its ordering, or set to any other value where it has no ordering, or one block added to or removed from the map. Moving one coordinate at a time is what makes the walk interpretable afterwards -- the path from the start to the winner reads as a series of decisions, each with the score that justified it.

def random_start(rng, space: dict = None, block_pool=()) -> dict:

Somewhere in the space, chosen without reference to anywhere already looked at.

def climb( evaluate, start: dict, space: dict = None, block_pool=(), restarts: int = 2, max_evaluations: int = 120, seed: int = 42, on_step=None, should_stop=None, log=<built-in function print>) -> pandas.DataFrame:

Walk uphill from start, restart when stuck, and return everywhere it looked.

evaluate takes a configuration and returns (score, extras) -- extras is whatever the caller wants carried into the results table, typically the labels and the findings behind the score.

Returns the whole visited set rather than the winner, in the order it was visited, with the restart and step number. A search that returns only its best configuration cannot be audited: the second-best configuration and how far behind it came is the difference between a real optimum and a lucky one.

MODES = ('guilt', 'disagreement', 'conjunction', 'both', 'recovery', 'auprc', 'auroc', 'knn')

def evaluator( nodes: pandas.DataFrame, mode: str = 'guilt', layers=(), against=(), seed: int = 42, log=<built-in function print>):

Build the scoring function for one of the three questions, with its embeddings cached.

mode "recovery" -- how well a held-out label comes back. Measures whether the map can be trusted, and answers nothing about whether it is useful. mode "guilt" -- how much the map predicts about genes nobody has measured (discovery.guilt). mode "disagreement" -- how many categories the map splits along a second measurement (discovery.disagreement). against names the second layers. mode "conjunction" -- combinations of two categorical layers that the map resolves beyond either margin alone (discovery.conjunction). against names the second layers. mode "auprc" / "auroc" / "knn" -- the ranking metrics from metrics. These ask "how good a shortlist would this map give me for each category", which is the question guilt by association actually asks, and unlike the partition scores they cannot be won by merging everything into one cluster. "knn" scores the EMBEDDING alone, with no clustering involved, which is what to optimise first when the clustering is the thing that keeps going wrong. mode "both" -- the sum, for when the question is "find me anything".

Every mode records every other metric alongside its own score. The cost is a few milliseconds against an embedding that took thirty seconds, and it means a run optimised for one thing can be re-read against another afterwards instead of being run again.

def block_pool(nodes: pandas.DataFrame) -> list:

Which feature blocks this table can actually offer, in a stable order.