Ciro Santilli @cirosantilli 40

Given a bunch of points in $n$ dimensions, PCA maps those points to a new $p$ dimensional space with $p\le n$.

$p$ is a hyperparameter, $p=1$ and $p=2$ are common choices when doing dataset exploration, as they can be easily visualized on a planar plot.

The mapping is done by projecting all points to a $p$ dimensional hyperplane. PCA is an algorithm for choosing this hyperplane and the coordinate system within this hyperplane.

The hyperplane choice is done as follows:

www.sartorius.com/en/knowledge/science-snippets/what-is-principal-component-analysis-pca-and-how-it-is-used-507186 provides an OK-ish example with a concrete context. In there, each point is a country, and the input data is the consumption of different kinds of foods per year, e.g.:so in this example, we would have input points in 4D.

The question is then: we want to be able to identify the country by what they eat.

Suppose that every country consumes the same amount of flour every year. Then, that number doesn't tell us much about which country each point represents (has the least variance), and the first PCA axes would basically never point anywhere near that direction.

Another cool thing is that PCA seems to automatically account for linear dependencies in the data, so it skips selecting highly correlated axes multiple times. For example, suppose that dry codfish and olive oil consumption are very high in Portugal and Spain, but very low in Germany and Poland. Therefore, the variation is very high in those two parameters, and contains a lot of information.

However, suppose that dry codfish consumption is also directly proportional to olive oil consumption. Because of this, it would be kind of wasteful if we selected:since the information about codfish already tells us the olive oil. PCA apparently recognizes this, and instead picks the first axis at a 45 degree angle to both dry codfish and olive oil, and then moves on to something else for the second axis.

We can see that much like the rest of machine learning, PCA can be seen as a form of compression.

Project Euler problems typically involve finding or proving and then using a lemma that makes computation of the solution feasible without brute force. There is often an obvious brute force approach, but the pick problem sizes large enough such that it is just not fast enough, but the non-brute-force is.

As such, they live in the intersection of mathematics and computer science.

news.ycombinator.com/item?id=7057408 which is mega high on Google says:

In many cases, the efficient solution involves dynamic programming.

There are also a set of problems which are very numerical analysis in nature and require the approximation of some real number to a given precision. These are often very fiddly as I doubt most people can prove that their chosen hyperparameters guarantee the required precision.

Many problems ask for solution modulo some number. In general, this is only so that C/C++ users won't have to resort to using an arbitrary-precision arithmetic library and be able to fit everything into uint64 instead. Maybe it also helps the judge system slightly having smaller strings to compare. The final modulos usually don't add any insight to the problems.

Bibliography:

A Turing machine decider is a program that decides if one or more Turing machines halts of not.

Of course, because what we know about the halting problem, there cannot exist a single decider that decides all Turing machines.

E.g. The Busy Beaver Challenge has a set of deciders clearly published, which decide a large part of BB(5). Their proposed deciders are listed at: discuss.bbchallenge.org/c/deciders/5 and actually applied ones at: bbchallenge.org.

But there are deciders that can decide large classes of turing machines.

Many (all/most?) deciders are based on simulation of machines with arbitrary cutoff hyperparameters, e.g. the cutoff space/time of a Turing machine cycler decider.

The simplest and most obvious example is the Turing machine cycler decider