Not that I have the free time to take on another project, but there's a part of me that wants to do a thorough exploration of argmax and write up what I find, if only as notes. Math-y and science-y people take it for granted; search engines prefer telling you about the numpy function of that name. But it turns out argmax has (what I think are) interesting subtleties.

Here's one. If you're given a function, you can treat argmax of that function as a set-valued function varying over all subsets of its domain, returning a subset--the argmaxima let's call them--of each subset. argmax x∈S f(x) is a subset of S, for any S that is a subset of the function f's domain. Another way to think of this is that argmax induces a 2-way partitioning of any such input set S into those elements that are in the argmax, and those that are not.

Now imagine you have some way of splitting any subset of some given set into two pieces, one piece containing the "preferred" elements and the other piece the rest, separating the chaff from the wheat if you will. It turns out that in a large variety of cases, given only a partitioning scheme like this, you can find a function for which the partitioning is argmax of that function. In fact you can say more: you can find a function whose codomain is (a subset of) some n-dimensional Euclidean space. You might have to relax the definition of argmax slightly (but not fatally) to make this work, but you frequently can (1). It's not obvious this should be true, because the partitioning scheme you started with could be anything at all (as long as it's deterministic--that bit's important). That's one thing that's interesting about this observation.

Another, deeper reason this is interesting (to me) is that it connects two concepts that superficially look different, one being "local" and the other "global". This notion of partitioning subsets into preferred/not preferred pieces is sometimes called a "solution concept"; the notion shows up in game theory, but is more general than that. You can think of it as a local way of identifying what's good: if you have a solution concept, then given a set of things, you're able to say which are good, regardless of the status of other things you can't see (because they're not in the set you're considering). On the other hand, the notion of argmax of a function is global in nature: the function is globally defined, over its entire domain, and the argmax of it tells you the (arg)maxima over the entire domain.

In evolutionary computation and artificial life, which is where I'm coming from, such a function is often called an "objective" (or "multiobjective") function, sometimes a "fitness" function. One of the provocative conclusions of what I've said above for these fields is that as soon as you have a deterministic way of discerning "good" from "bad" stuff--aka a solution concept--you automatically have globally-defined objectives. They might be unintelligible, difficult to find, or not very interesting or useful for whatever you're doing, but they are there nevertheless: the math says so. The reason this is provocative is that every few years in the evolutionary computation or artificial life literature there pops up some new variation of "fitnessless" or "objective-free" algorithms that claim to find good stuff of one sort of another without the need to define objective function(s), and/or without the need to explicitly climb them (2). The result I'm alluding to here strongly suggests that this way of thinking lacks a certain incisiveness: if your algorithm has a deterministic solution concept, and the algorithm is finding good stuff according to that solution concept, then it absolutely is ascending objectives. It's just that you've chosen to ignore them (3).

Anyway, returning to our friend argmax, it looks like it has a kind of inverse: given only the "behavior" of argmax of a function f over a set of subsets, you're often able to derive a function g that would lead to that same behavior. In general g will not be the same as f, but it will be a sibling of sorts. In other words there's an adjoint functor or something of that flavor hiding here! This is almost surely not a novel observation, but I can say that in all my years of math and computer science classes I never learned this. Maybe I slept through that lecture!

#ComputerScience #math #argmax #SolutionConcepts #CoevolutionaryAlgorithms #CooptimizationAlgorithms #optimization #EvolutionaryComputation #EvolutionaryAlgorithms #GeneticAlgorithms #ArtificialLife #InformativeDimensions



(1) If you're familiar with my work on this stuff then the succinct statement is: partial order decomposition of the weak preference order induced by the solution concept, when possible, yields an embedding of weak preference into ℝ^n for some finite natural number n; the desired function can be read off from this (the proofs about when the solution concept coincides with argmax of this function have some subtleties but aren't especially deep or hard). I skipped this detail, but there's also a "more local" version of this observation, where the domain of applicability of weak preference is itself restricted to a subset, and the objectives found are restricted to that subdomain rather than fully global.

(2) The latest iteration of "open-endedness" has this quality; other variants include "novelty search" and "complexification".

(3) Which is fair of course--maybe these mystery objectives legitimately don't matter to whatever you're trying to accomplish. But in the interest of making progress at the level of ideas, I think it's important to be precise about one's commitments and premises, and to be aware of what constitutes an impossible premise.