Computer Studies

machine learning

supervised learning

unsupervised learning

clustering

dimensionality reduction

semisupervised learning

pca (principal component analysis):

this is the first dimensionality reduction method you should try.

mds (multidimensional scaling): if you have data consisting of a bunch of pairwise 'similarities' or 'dissimilarities' between objects, and you want to turn this into 2-D positions of those objects, perhaps for purposes of visualization, you can use MDS

(classical) mds, if given as input a set of similarities which were computed as Euclidean distances in some space, will give the same result as pca

todo

computer studies

virtual machines (VMs)

todo

eg xen eg java

version control

todo

eg git, mercurial

https://en.m.wikipedia.org/wiki/Simulation_preorder

Working thru the equivalence between the ordinary form and the relational composition form in http://wayback.archive.org/web/20160207193211/https://en.m.wikipedia.org/wiki/Simulation_preorder#Formal_definition (note: you need to know the definition relational composition for that; see below)

One of the thing to do when you are trying to understand some abstract math statement is to make it more concrete by converting it to an if/then implication and adding variables to it, choosing variable names so that names denoting 'the same type of thing' are near each other in the alphabet (where how you decide what the most important 'type' of each variable is is context-dependent), and these groupings of variables into 'similar types of things' are far from each other, and the ordering of the variables in the alphabet matches the ordering in the concept, if any.

R^{-1}\,; \overset{\alpha}{\rightarrow}\quad {\subseteq}\quad \overset{\alpha}{\rightarrow}\,; R^{-1}

Can be converted into an if/then statement via the definition of \subseteq. The above statement means

\forall (x,y), if:

(x, y) \in (R^{-1}\,; \overset{\alpha}{\rightarrow})

, then:

(x, y) \in p(\overset{\alpha}{\rightarrow}\,; R^{-1})b

or to put it on one line:

\forall x,y ((x, y) \in (R^{-1}\,; \overset{\alpha}{\rightarrow}) \to (x, y) \in \overset{\alpha}{\rightarrow}\,; R^{-1})

We chose the variables x,y because we don't yet have an intuition for what the relevant 'types' of things are, and x,y,z is just our default.

Next we unpack the relational composition, ';':

\forall x,y ((\exists q1 s.t. (x, q1) \in R^{-1} and (q1,y) \in \overset{\alpha}{\rightarrow}) \to (\exists q2 s.t. (x, q2) \in \overset{\alpha}{\rightarrow} and (q2,y) \in R^{-1}))

We chose the variable q1, q2 because we want to keep it separate from x,y, so we don't want to just use z or w. 'q' is good for \exists variables because it is a 'Q'uestion mark or 'Q'uery. We used q1 and q2 to keep the two 'q's separate in our head even though they don't have the same scope, so technically we would have been permitted to use 'q' for both of them.

Next we unpack the R^{-1}:

\forall x,y ((\exists q1 s.t. (q1, x) \in R and (q1,y) \in \overset{\alpha}{\rightarrow}) \to (\exists q2 s.t. (x, q2) \in \overset{\alpha}{\rightarrow} and (y, q2) \in R))

Next we forget about the \forall x,y at the beginning (treat it as implicit), and change the domain-specific stuff to English:

(\exists q1 s.t. q1 is simulated by x and there is a transition from q1 to y) \to (\exists q2 s.t. there is a transition from x to q2 and y is simulated by q2)

Now we change the variable names. We are trying to understand simulation, so we are trying to understand the relationship between a state and its simulating state, so we choose our variable names so that the variables denoting 'ordinary' states are near each other in the alphabet, and the variables denoting 'simulating' states are near each other in the alphabet, but the ordinary and simulating variables are far from each other in the alphabet. We'll choose a,b,c,... for 'ordinary' states and p,q,r,... for 'simulating' states (being aware that this is a false dichotomy; we have never been told that it is impossible for one state to be both 'ordinary' and 'simulating' eg to be the simulator of one other state, but to be itself simulated by yet another other state). Also, an important ordering in the problem is the state transition ordering, so we will try to choose a and b so that a \overset{\alpha}{\rightarrow} b, and p and q so that p \overset{\alpha}{\rightarrow} q.

q1 is simulated by x, so we want to rename 'q1' to either 'a' or 'b' and rename 'x' to 'p' or 'q'. There is a transition from q1 to y, so we want 'y' to be the same type of thing as 'q1', so rename 'y' to either 'a' or 'b', and we want 'q1' to come before 'y' in the alphabet. So rename 'q1' to 'a' and rename 'y' to 'b', and 'x' to either 'p' or 'q' (see the next paragraph).

Similarly, there is a transition from x to q2, so we want 'x' and 'q2' to be the same type of thing and we want 'x' to come before 'q2' in the alphabet, and y is simulated by q2, so we want 'y' to be either 'a' or 'b' and 'q2' to be either 'p' or 'q'. We have already chosen to rename 'y' to 'b', so rename 'y' to 'b' and 'x' to 'p' and 'q2' to 'q'.

So now we have

(\exists a s.t. a is simulated by p and there is a transition from a to b) \to (\exists q s.t. there is a transition from p to q and b is simulated by q)

Note that our desire to cleanly separate types of states into ordinary and simulating could have failed, or our implicit assumption that ordinaries transition to ordinaries and simulatings transition to simulatings could have failed, so we got lucky here in that it was possible to keep the 'a's and 'b's separate from the 'p's and 'q's. But even if that separation had failed, trying to keep them separate and failing would have improved our intuition about the domain.

Now we change the voice of the first 'simulated by' verb from passive to active, because p is universally quantified and a is only existentially quantified, so p is the thing that exists 'first' in our thinking here; for the same reason, we leave the second 'simulated by' in passive voice:

(\exists a s.t. p simulates a and there is a transition from a to b) \to (\exists q s.t. there is a transition from p to q and b is simulated by q)

now we rephrase 'exists a s.t.' and 'exists q s.t.' into a different English construction, that moves it later into the phrasing, after the introduction of 'p':

(p simulates some a and there is a transition from a to b) \to (there is a transition from p to some q and b is simulated by q)

And \to is read 'implies', so:

If p simulates some a, and there is a transition from a to b, then this implies that there is a transition from p to some q, and b is simulated by q.

Now we read over that English sentence a few times and try to get it's meaning. It may also be helpful to try to draw a diagram. In this case we come up with:

p -> q
|    |
a -> b

where edges on the horizonta axis ar 'transitions' and edges on the vertical axis are 'simulations' (the vertical edges have directionality too, but that's harder to draw so i didn't).

Reading the English sentence we can see it as instructions for constructing the diagram.

"..p simulates some a"

this describes:

p
|
a

"there is a transition from a to b"

a -> b

Putting the last two together and adding in the if/then:

"If p simulates some a, and there is a transition from a to b, then ...": so if we see the fragment:

p
|
a -> b

"... then this implies that there is a transition from p to some q, and b is simulated by q"

then we may add the fragment:

p->q
   |
   b

In other words, if we see the fragment

p
|
a -> b

then we may complete the diagram to

p -> q
|    |
a -> b

Combining this with our suspicion about what the intuition of 'simulates' might be supposed to mean, we might hazard a guess that the idea is that the bottom is the 'real world' and the top is the 'simulation' and when we see a transition on the bottom, there must then be a top transition to 'mirror' the bottom one. And indeed looking back on both the English and the diagram representation, we see that this is the case: when we see a transition on the bottom, in the 'ordinary' states, and we know that there is a 'simulating' state simulating the source of that transition, then the 'simulating' state must 'mirror' that transition 'within the simulation' ie on the top of the diagram.

blockchains

The purpose of the blockchain is to be a shared append-only data structure. There are a number of nodes who have copies of what is supposed to be exactly the same data (but see below). The nodes are all constantly telling each other what they believe to be the most up-to-date version of the data. The purpose of the blockchain is to support a consensus-finding algorithm by which the nodes may start out disagreeing on the contents of the most recent few blocks in the log, but eventually converge to a consensus, at least for relatively old blocks.

This convergence occurs even if some of the nodes are evil or faulty or out-of-touch, provided that these bad nodes control less than 50% of the total computing power of all of the nodes (for 'proof-of-work' style blockchains).

How do the nodes decide which version of the chain is 'right' when there is disagreement? You might think you could do this by having the nodes vote, but if each node got one vote, then it would be too easy for someone to create a million fake nodes to game the vote. Proof-of-work blockchains are sort of like a vote where the number of "votes" that each computer gets is proportional to its computational power ("hashing power" or hashpower). There are other styles of blockchains, such as "proof-of-stake", in which the number of "votes" is proportional to something other than computational power.

In more detail:

First, watch this video before reading the rest: https://anders.com/blockchain/ (alternate link: https://www.youtube.com/watch?v=_160oMzblY8 ).

Now, let's imagine that some of the nodes are evil (or maybe just faulty, or maybe just out-of-touch), and want to try to change past data and get the other nodes to accept their fake history (the "fake chain").

When any node notices that some other nodes are saying different things (proposing different chains), it prefers to believe in whichever chain is longer (this is a slight simplification, actually it's accumulated difficulty).

Many of the nodes are constantly accepting new data and 'mining' new blocks to append to the end of the real chain. They are doing this as fast as they can. The problem of finding a new hash for new blocks is embarrassingly parallel, so if there are 1000 nodes in the network they can mine about 1000x as fast as one node (however, the protocol is constantly adjusting the difficulty (the number of prefix zeros required in the hash) to ensure that on average the blockchain is getting longer at a fixed rate).

If the evil nodes want to change something far back in history, they're going to have to try to mine a whole bunch of new blocks before the fake chain gets as long as the real chain. Recall that the other nodes will reject the fake chain as long as they are aware of another chain which is longer. But while the evil nodes are trying to catch up, the good nodes are also going to be trying to mine new blocks to append to the end of the real chain.

Assuming there are more good nodes than evil ones (or rather, that the total computing power of the good nodes is greater than the total computing power of the evil ones), on average the speed that the evil nodes can mine new blocks is slower than the speed that the real chain is getting longer.

Therefore the rule that the longest chain is the right one works.

Now, through random chance it's always possible for the evil chain to get lucky and mine a block much faster than the good chain. But if it alters something deep in history, then in order to catch up, it would have to get lucky in this way many times in a row; the chance of that happening decreases geometrically with the number of blocks it is behind. Therefore, you can be very confident that a block deep in the chain won't be altered.