Showing posts with label complexity. Show all posts
Showing posts with label complexity. Show all posts

Saturday, November 7, 2020

How they handle multi-episode stories in a TV series

Related to: Expecting Short Inferential Distances (yes, linking LW is still a thing).

Below are some remarks I've made in scattered form in several forums, but I thought I'd collect them here.

Problem: A TV series will run for many episodes, and the writers will want to build up a storyline over many of them, which is necessary for a satisfying payoff. But viewers don't necessarily watch it all at once and keep the whole thing in their heads.

I call this the "narrative equivalent" of expecting short inferential distances (see the link above) -- just as people are used to an explanation not requiring a lot of steps, they don't expect a given scene or episode to need a lot of previous viewing to understand.

So, how do writers solve this problem? Here are the four general ways, with examples (feel free to offer more TV series for a category!):

A) Don't bother #1: Each episode is self-contained.

This is known as the "episodic" approach, as opposed to serial. Each episode can be understood without knowing anything about the preceding episodes, so there's no need to worry about this problem at all.

Examples: Star Trek (at least the original or TNG), South Park, The Simpsons (earlier seasons)

Downside: It's hard to feel investment when you know nothing will matter, that things will just return to where they were at the end. It also limits how much build-up (and corresponding payoff) the story can have.

B) Don't bother #2: It's the viewers' job to keep up.

Each episode just assumes you have the entire previous history in your head, maybe with some small reminders of previous relevancies for assistance.

Example(s): Game of Thrones

Downside: It only works for really devoted fans who will binge the whole thing and try on their own to stay up to speed.

C) Formal recaps

You've seen them: the narrator says, "Previously, on [this TV series]...", and then you get enough short clips to establish the relevant context for current episode.

Examples: 24 (after season 1), Battlestar Galactica, Burn Notice

Downside: A lot of people don't like them and think they're cheesy. (I've never understood this mentality, but there it is.) It also may force you to reveal what things from previous episodes will be relevant, taking away their surprise when revealed. There is a slight break in immersion since you have to go "out of the world" for them.

D) In-world recaps

Same as the previous, except you're not taken "out of the world" to do it; instead, there is a scene, within the story, that doubles as exposition of the things a formal recap would cover.

Examples: Breaking Bad, Bojack Horseman

Downside: It heavily constrains how you write the story and forces in pointless scenes that shatter immersion because they're retelling things -- and more slowly! -- the characters should know.

Well, there you have it. That about summarizes the different ways writers handle (or avoid handling) long storylines!

Friday, May 24, 2013

"I added your numbers, and I have no idea what they are."

So it turns out there's a thesis arguing that polynomial-time, fully homomorphic encryption is possible. (Link is to the dumbed-down -- but still journal-published -- version that mortals like me are capable of understanding.)

It's hard to understate the significance of this. This means that it's possible for you to give someone your data in encrypted form, and for them to execute arbitrary operations and give it back to you, without ever knowing what the data is. That is, they transform an input ciphertext to and output ciphertext such that when you decrypt the output, you have the answer to your query about the data, but at no point did they decrypt it or learn what was inside.

In other words: "I just calculated the sum of the numbers you gave me, but I have no idea what the sum is, nor what any of the numbers are."

If it sounds impossible, it's not because you misunderstand it, but because that kind of thing shouldn't be possible -- how can you perform arbitrary operations on data without learning something about it? Sure, maybe there are edge cases, but a rich, Turing-complete set?

It would mean that "the cloud" can ensure your privacy, while *also* doing useful operations on your data (as the author, Craig Gentry, goes at great length to emphasize).

As best I can tell from the paper, here's the trick, and the intuition why it's possible:

1) The computation must be non-deterministic -- i.e. many encrypted outputs correspond to the correct decrypted output. This is the key part that keeps the computation provider from learning about the data.

2) The output must be fixed size, so you have a sort of built-in restriction of "limit to the first n bytes of the answer".

3) It does require a blowup in the computational resources expended to get the answer. However, as noted above, it's only a polynomial blowup. And thanks to comparative advantage, it can still make sense to offload the computation to someone else, for much the same reason that it makes sense for surgeons to hire secretaries even when the surgeon can do every secretarial task faster. (Generally, when the provider's opportunity cost of performing the task is less than yours.)

4) Finally, to be fully homomorphic -- capable of doing every computation, not just a restricted set of additions and such -- the encrypted computation has to find a way around the buildup of "noise" in the computation, i.e. properties of the output that put it outside the range of what can be decrypted (due to exceeding the modulus of the operation needed to extract the output). And to do that, in turn, its operation set must be sufficient to perform its own decryption.

I'm only about halfway through the paper, but it's been really enlightening to get the intuition behind why this kind of thing can work.

Friday, June 10, 2011

Explaining – not setting – Bitcoin straight

Okay, I had some spare time last night, so I figured I’d sit down and write up an explanation of some of Bitcoin’s workings. The chief problem in explaining this to the layman is that, as a prerequisite, you need to understand the basics of public key cryptography (aka asymmetric cryptography), which, for the average person, is quite a tall order in itself. But since I’m the master at this kind of thing, here’s how I would put it:

First, to get something out of the way: nothing in Bitcoin is actually encrypted. Rather, it works, and works robustly, without centralization, specifically because all transactions are visible. The privacy comes in how the entities trading the coins are referred to in this transaction database, purely by their Bitcoin address (a string of numbers and letters, like 1mVQtx6rn…), which is like one of those supposed Swiss bank accounts you hear about that are only known by a number. (So yes, if you publicly and believably reveal that, "Hey, I own address 152zpfu5b20gh29...!", then people can see what you do via the address 152zpfu...) So rather than anonymous, Bitcoin is best described as pseudonymous (sue-DONN-i-MUS).

The reason that you need to know the basics of public key cryptography, rather, is that a lot of its "primitives" (building blocks) are used in Bitcoin, and the protocols used are heavily studied by professional cryptographers.

First primitive: public key-based digital signatures

How do you accomplish signatures in a digital world, where anyone can put any data on any storage medium? Like a physical signature, a digital one needs to meet the following characteristics:

A) Proof of identity: only you can produce your signature, so seeing your signature is proof that you endorse what you signed.
B) Non-repudiation: after giving your signature, you can't plausibly deny having signed it.
C) Non-transferability: your signature on Document1 can't be "moved" to a different Document2, implying your endorsement of the latter

Quite surprisingly, you can accomplish these goals with a kind of signature in the digital world. Here's the trick: you generate a keypair -- a "public key" and a corresponding "private key". You keep the private key secret, and tell everyone in the world your public key. You then use a "public key algorithm" (PKA) that takes as an input:

1) the message, M1, that you want to sign
2) your private key, SK1

and outputs a signature, SIG1. PKAs are designed so that computing this algorithm and generating this signature is quick and easy.

Then, if someone wants to verify that you really did sign message M1, they just verify that a certain mathematical relationship (corresponding to the particular PKA used) holds among your public key (which, remember, they know), your message M1, and your signature SIG1. Again, this process is designed to be quick and easy for the verifier.

So, how does this provide the desired qualities A through C above? A and B are satisfied by the fact that it is extremely difficult and time-consuming to produce SIG1 *unless* you know the private key SK1. (Inferring the private key from the public key is likewise too time-consuming to be finished anytime in the next few centuries.) So, the fact that you were able to (quickly) compute SIG1 is proof that you hold the private key corresponding to the public key, AND that (with a few caveats) you chose to use that key to generate the signature for M1.

This protocol satisfies criterion C (non-transferability) because, as you recall, SIG1 is partly a function of the message itself. This means that your signature will be different for each message you could conceivably want to sign. So someone can't take SIG1 and cite it as proof that you signed a different message M2 -- because the protocol's specified mathematical relationship will *not* hold for {M2, SIG1, public key} -- it will only hold for {M1, SIG1, Bob's public key}. To "forge" a signature, they would need to produce {M2, SIG2, Bob's public key}. But like I said above, it's way too hard for them to figure out what SIG2 would be unless they know your private key.

I'm deliberately leaving off the specific algorithms used for such systems so that this does not become unbearably long. Suffice to say, there are algorithms that accomplish this, and they mainly rely on modular arithmetic and prime numbers. I will only add that the class of function needed to produce such a PKA is known as a "trapdoor one-way function". That is any function f(x) such that:

- Given x, it's easy to compute f(x).
- Given a value V equal to f(x) for some unknown x, it's hard to find an x such that f(x) = V. (i.e., it's hard to invert f)
- But, if you know a specific piece of information particular to f, called the "trapdoor knowledge" (in the exposition above, this is the part played by the private key), it is *easy* to invert f

What role do public key signatures play in Bitcoin? They are used to prove to the network that the owner of address A1 (A1 also functioning as a public key!) really did authorize the transfer of certain coins to the next address. Other nodes in the network, in turn, are able to easily verify that the owner of A1 signed off on the transfer by checking that the mathematical relationship I mentioned above holds among the A1 public key, the message indicating the transfer, and the signature on the transfer. And if this relationship doesn't hold, the other nodes (per the Bitcoin protocol) ignore the purported transfer, acting like it didn't exist, and refuse to tell other nodes about it.

Second primitive: (cryptographically secure) hash functions

A hash function (in cryptography) is a function that takes an input of any length, and deterministically computes a fixed-length output based on it, such that the relationship between input and output "seems random", and there's no quicker way to compute the output, or otherwise learn *anything *about what the output will look like, than to churn through the hash function itself. I will make this make a bit more sense. For simplicity, call the input to a hash function its "preimage", and the output of a hash function its "digest" (the output is also referred to as the checksum or the [digital] fingerprint).

An example of a (weak) hash function most people are familiar with is the kids' game where you find out your "Star Wars" name or your "stage name” by doing something like, "Take the first syllable of the street where you grew up, and add on the last syllable of your middle name, plus the first syllable of where you were born." This name is a hash of all that data about yourself.

However, cryptographically-secure hash functions have to meet more stringent requirements. Like I said above, it must be really hard to make inferences about the relationships between classes of input and classes of outputs without actually grinding through the function for each input in the class. So, for example, you can't have a hash function where "small changes in the input (preimage) lead to small changes in the output (digest)". Rather, they are designed so that a tiny change in the preimage will *significantly *change the digest. More formally, cryptographically secure hash functions must meet the following characteristics:

- Given a digest, it's hard to find a preimage that hashes to that digest. This is called "[first] preimage resistance". (Note: because preimages can be any length and the hash length is fixed, there are an infinite number of preimages that hash to any given digest.)

- Given a preimage, it's hard to find another preimage that hashes to the same digest. This is called "second preimage resistance".

- It's generally hard to find *any* preimages (given or not), that hash to the same digest. Such instances are known as "collisions", and this trait is called, obviously, “collision resistance”.

(Exercise for the reader: how the Star Wars name game described above fail all of these?)

The function of hashes: in everyday data security, they serve the function of obscuring data in a way that limits its malicious uses. For example, websites don't actually store your password (if they know anything about security whatsoever). Rather, they store a *hash* of your password. That way, they can still verify you by password (Check: does the hash of the password given match the hash we have on record?), but if someone breaks into their database, all they get are the hashes. Because the hash function has first preimage resistance
(see above), the list is much less useful to the attacker because they have to accomplish the difficult task of finding preimages for the hashes they found.

Hashes are where the "miners" come into play: initial bitcoins are generated and allocated (and still are) based on who can solve a mathematical problem. That problem is similar to the one of breaking a hash function's (first) preimage resistance. But rather than having to find a preimage with a *specific* digest, the problem is to find a preimage whose hash is a *partial* match (for some specific number of digits) with a target digest string. So, it's like an easier version of breaking preimage resistance, though still requiring the ability to do lots of (parallel) calculations – because there is, by design, no shortcut to solving this but to try as many preimages as you can.

Anyway, that's about all for now, something for you to chew on and get some understanding of the whole thing. There’s still a lot left, but that should cover the pre-requisites.

Sunday, March 7, 2010

When you can't go back to sleep: thermodynamics

Did you miss my posting? Well, it's been one of those days when you wake up early and can't go back to sleep. My mind's running wild this morning, and I figured I'd make some good use out of it. (It is no longer early as of completing this post because of interruptions from a playful kitty.)

I'm going to continue the lesson about thermodynamics that last left off about a year ago, by discussing some more interesting implications of the idea that "energy per unit temperature" is a measure of degrees of freedom. You see, in the time since then, I read John S. Avery's book Information Theory and Evolution, which, as you might have inferred, discusses life from the perspective of that ever-so-useful field of information theory. He also applies it to cultural (often called "memetic") evolution.

The first interesting insight that this book alerted me to is about molar entropy. Some background: in your chemistry class, you might have learned about the Gibbs free energy of a reaction, ΔG, which is calculated from ΔH - TΔS, where H is the molar enthalpy (internal + flow energy per mole), T is absolute temperature, and S is the molar entropy. For a chemical reaction, you look up the molar enthalpies of the products and subtract off the enthalpies of the reactants. Then you do the same for molar entropies, multiplying by the absolute temperature at which the reaction takes place, and add them. A negative sign for ΔG means the reaction happens spontaneously (well, as long as there is an available pathway).

With that out of the way, what are the units for S? Most tables give them as J/K*mol (Joules per Kelvin per mole, or energy per unit temperature per quantity of molecules). But, as the last post in this series showed, energy per unit temperature measures degrees of freedom, which can also be expressed in bits. So, as Avery neatly derives on pages 81-82, you can also express molar entropy in bits per molecule. (The conversion factor is 1 J/K*mol = 0.1735 bits/molecule.) I find this a much more intuitive way to think about it, because it connects the concept of molar entropy to the underlying dynamic: how many bits of information (on average) do you need to specify a molecule's current state, beyond that which you know from the temperature?

Also, rather than having to empirically derive this value directly (either from reaction data or by integrating its specific heat capacity per unit temperature from 0 K to its current temperature), it can be inferred from the known properties of the molecule: its shape, size, and bond strength. The stronger ("stiffer") its bonds are, the lower the entropy of the molecule, because large deviations from its equilibrium configuration are less probable. (Diamond, with its very strong covalent bonds, has the incredibly low molar entropy of 0.24 bits per carbon atom at STP, meaning you need less than one bit of information to specify every four atoms.)

[ADDENDUM: Avery also adds that if you divide the Gibbs equation through by T, you can describe a reaction in terms of the "information lost", i.e., the greater number of degrees of freedom you have permitted by letting the reaction take place.]

By recognizing this interconnection between molecule properties and complexity (needing more information to fully specify = more complex), one sees more unity ("consilience") to the science as a whole: entropy and bond properties aren't just off in their own domains, but have a lawful relationship. Unfortunately, however, I haven't worked out how to derive entropy from stiffness of a degree of freedom, and I haven't found a text that does it either.

Next in the series: A discussion of Eric J. Chaisson's Cosmic Evolution: The Rise of Complexity in Nature, which proposes specific energy flux (energy flow through a system per unit mass) as a measure of complexity that is applicable to everything from stars to planets to life to vehicles to computer chips to culture.