3 ms·
I wonder if there's something going on similar to the Curse of Dimensionality: when we reduce to one dimension at a time, there's way more interior than surface
by 082349872349872 4y ago
I wonder if there's something going on similar to the Curse of Dimensionality: when we reduce to one dimension at a time, there's way more interior than surface, and we see overwhelming overlap; when we take the gestalt in all dimensions, there's way more surface than interior, and we see separable populations?
- thaumasiotes 4y agoThere's a similar phenomenon you might encounter in language: if you have a text, and you sample one random letter at a time from it, it turns out not to be very difficult to determine what language the text is written in. Does the letter 'i' exist in French? Does it exist outside French? Sure, but nevertheless you can rule French in or out based on how often you sample a letter and get 'i'. French uses the same 'i' as everyone else, but it uses it in its own distinctively French way. This is what makes it trivial to break substitution ciphers given a long enough ciphertext.
- ggm 4y agoI could believe this for romance languages. I'd need somebody to explain how this applies in ideograms and non-western languages, and what the outliers are, vowels vs consonant.
- thaumasiotes 4y ago1. Non-western languages. There are no differences; this is not a category of any interest. Urdu is a non-western language, except of course that it is, in a global sense, very closely related to French. (Why do you think we say "Indo-European"?) 2. Ideograms. The modern language that comes closest to using written ideograms is Japanese. But the language that comes closest to what you're probably thinking of is Mandarin Chinese, where every character is fairly rare. You have exactly the same options that you do with any other language: you could render the text into an alphabet of interest, or you can do your analysis on the symbols the text is originally written in. That second approach will make some questions much easier; if you sample a letter and get န်, you can be certain you're not reading French. It will make analyzing Chinese harder because character frequencies are so low. (see https://lingua.mtsu.edu/chinese-computing/statistics/char/list.php?Which=MO https://lingua.mtsu.edu/chinese-computing/statistics/char/li... - the most common character in written Chinese is 的 at 4.1% of all characters; the second most common accounts for an additional 1.6% of all characters. The top 152 characters collectively account for 50% of all text.) This will mean that codebreaking requires longer texts.† It won't have much effect on the problem of identifying the language by sampling unenciphered monograms from it; that stays easy, because the commonly used characters are highly informative even if e.g. you're comparing written Mandarin to written Cantonese. You'll probably need more samples (for an equally reliable judgment) than you would for a script that didn't have so many unique characters. † This problem is significant. Specific content words will all be rare, and we can't really expect a message, even a very long message, to discuss every possible topic at the same frequency that the corpus of written Chinese as a whole does. Even if we could expect that, the amount of ciphertext you'd need to reliably distinguish the 3100th-most common character in this corpus (酱 [noun, 'sauce'] representing 0.09% of all characters) from the 2494th-most common (娶 [verb, 'to marry a woman'] representing 0.19% of all characters) would be quite large.
- deleted 4y ago[deleted]
- Simon_O_Rourke 4y agoSame kind of thing works with counting the frequency of particular digits (n-digit analysis) in a given position for an integer or decimal. Especially for the higher order decimal digits there's a far-from-random distribution that you can use to infer whether there's been any tampering, given enough values to study.
- 082349872349872 4y agoTo understand the mechanism, imagine we accounted in binary instead of decimal. What are the odds the first digit of an entry is a 1?
- thaumasiotes 4y agoThat won't help you understand the mechanism. The reason the first digit of a binary number is 1 is just the anthropic principle. ("You can only observe things that exist.") That same observation will tell you that, just as the first nonzero digit of a binary number is zero 0% of the time, the first nonzero digit of a decimal number is zero 0% of the time. That is what it means to be a nonzero digit! But it won't tell you anything about why one possible digit might be more or less frequent than another possible digit. The mechanism is just multiplication. Suppose you have a quantity that increases by 20% every period. (Doesn't matter what the period is.) Let's start the quantity at 4 times 10 to the power of irrelevant. We'll consider the leading digit every period: 4 4 5 6 8 9 1 1 1 2 2 2 3 4 5 6 7 8 1 1 1 1 2 2 3 3 ... As you can see, we spend a lot more time with the amount of stuff we have being led by a 1 than we do with it being led by any other digit. Having our growth rate be less than one makes this easy to see by causing similar leading digits to occur next to each other, but the result will be the same for any growth rate. (You can see that it will be the same for any growth rate by considering that you can always match the observations of a system with the same observation period and a different growth rate by instead imagining a system with the same growth rate and a different observation period. But varying the observation period doesn't change the amount of time spent in any given quantity range.)
- 4y ago