Avoiding the Adjective Fallacy
betterexplained.com
betterexplained.com
Every time I'm asked about big-O in a job interview, I'm asked to recite the formal rules of the notation, rather than demonstrate how to use the resulting insight to make the code better. Just because I don't know the formal rules of how to calculate Big-O they assume I can't write any code that scales.
Its like a teacher assuming a student can't speak english because he can't recite the adjective order chart from memory.
In Isaac Asimov's biography he mentions taking some intelligence test (perhaps in the Army?) that checked for familiarity with advertising slogans. Sure, there was probably a correlation there, but know we realize that's fundamentally dumb.
I guess I am saying don't underestimate the importance of rigor in knowing precise definition of mathematical notations.
On the other hand plenty of people can memorize that a lookup in a BST is O(log n) without understanding what that actually means. If you can explain that a balanced BST grows in height by powers of two without actually using the phrase "log n" then that's more impressive than the person who does rote memorization without understanding what it actually means.
So in the case of arrays, since we do not need to read A[0] and A[1] to access A[2], it makes more sense to say it is an O(1) operation.
Another example is arithmetic. Addition and multiplication are considered O(1) operations for many algorithms even though multiplication is slower than addition. At a lower level, addition could be considered O(log n), since the binary representation of numbers has O(log n) bits of input. But the abstraction of addition as an O(1) operation is more useful at a higher level.
Also in Big-O, we drop everything but the major term, so accessing element 0 may be O(1.0001) while accessing element 20 is O(1.0003), they are both still considered O(1).
This is purely my takeaway from my undergrad algorithms class, so it may not be entirely accurate. Please correct me if I am wrong or misleading.
On to the larger point: O(1) does not mean "twice as fast as O(2)". It means "does not take longer depending on how many elements there are". That is, if I have an algorithm that takes twice as long as an O(1) algorithm, the slower algorithm is still O(1). We do not care about constant factors when dealing with big-O notation.
Accessing an array is O(1). What do you have to do to access an array element? You have to take the size of an array element, and multiply it by the index of the element, and add the starting address of the array, and access the memory at that address. That's O(1), because it does not depend on the number of elements in the array.
In contrast, accessing an element in a linked list is O(N). You have to start at the beginning of the list, and keep getting the next element until you get to the one you want. On average, that takes N/2 operations for a list of N elements. But we don't care about constant factors like 1/2 in big-O notation, so accessing an element of a list is O(N).
But if I want to insert an element into the middle of a linked list, and I already have a pointer to the place where I want to insert it, that insertion is only O(1). I have to change swap some pointers around (2 or 4, depending on whether it's a singly- or doubly-linked list). But that doesn't depend on the size of the list. Whereas if I want to insert an element into the middle of an array, I have to move all the elements after the inserted item, which is an average of N/2 items, which means that operation is O(N).
This is a completely inadequate explanation of big-O, but I hope it's enough to clear things up at least a bit for you...
[Edit: fixed italics.]
Here is the key insight I was missing. Thank you very much!
Now, if the number of times you had to access the memory in order to retrieve the data in the array depended on how big the array was, then you'd have O(N). An array is specifically designed so you only have to go to memory twice, first to get the memory address stored at X position in the array, then to retrieve the information stored on that position.
A linked list, as described in a sibling comment, actually does have to do this. You trade easy accessibility for other properties.
Ditto for the steps to do register operations and any of the other machine language instructions. The time can vary, but not as a function of the size of the input. So it's still constant time.
To answer your immediate question, the "general computation model" assumes constant memory access time. It's hand-wavy, but at least it's consistent.
The bigger problem is that for hashtables, even under ideal, non-physical assumptions, you still can't logically derive O(1), because there are unavoidable, inherent computations you have to do as the hashtable gets arbitrarily large. Either you a) adapt the hash function to have a bigger output, or b) you allow values to stack up in each output slot. a) is log(n), b) is n.
I don't know anyone who could read the hashtable implementation, without knowing the "right" answer, who would reasonably say "oh, that's O(1), obviously".
I wondered about hashtables too. I was actually teaching someone about them recently and had to re-read some CS stuff for it, and in the process I realized that the O(1) access for hashtables doesn't make any sense in the light of explanations I know.
So it turns out that the answer is complicated and in CS curriculum they just handwave you through. It sucks, to be honest, and it's the one thing that always annoyed me about formal education - far too often the teacher/professor stated something as a fact and provided a "proof" with so much confidence that I sort-of assumed it must be so, and realized only months or years later (and after a lot of confusion) that I learned an approximation - maybe a smart one, with good reasons backing it up, but still just an approximation, with important caveats that were never even mentions.
It sorts of make you wonder how much do you really understand about things, even in STEM.
[0] - https://news.ycombinator.com/item?id=9808452
[1] - http://cs.stackexchange.com/questions/1643/how-can-we-assume...
I stated in my first reply that the growth rate is notated as a function of the size of the input. Big O is itself an approximation, you don't use it if you absolutely have to know all the other factors that don't vary on the size of the input. Such as if they vary on your memory architecture. In practice they tend not to matter, Big-O is sufficient for most purposes.
If you do need the detail, you remove the Big-O and write out your other factors so you can compare them to other algorithms at the right level of detail. There are also other notations you can use that convey other concepts, such as little-o, little-theta, big-theta. When you use a Landau symbol[1], as these are called, you're making an approximate statement by definition.
It's still perfectly fine to call array access O(1), even if your data is stored on Pluto, and it's Odysseus doing a space opera Odyssey for each retrieval, you're still only going there twice. Even if there are sub-algorithms that you are calling within the main one, you're still only calling them a constant number of times. If the first time you go to Pluto to get data it takes 6 months and the second time it takes 30 years, because of complications, it's still constant time.
If you were accessing a linked list stored on Pluto, then you're going to Pluto a number of times depending on how deep in the linked list your data is, assuming it's a dumb probe and it can't figure out where to go once it gets to Pluto and has to come back to earth to figure out what to do next. (go back to Pluto)
If it turns out retrieval time matters, or other factors besides the size of the input, then you can't approximate over them and Big-O ceases to be useful.
Given O(1) arithmatic, you should be able to use an O(1) hash function. At that point, you only have to deal with realocation as your tables grows without bound. You can solve that problem by using the 2n allocation method that gives us O(1) amortized appending to vectors.
Of course, you still need to make messy assumptions about randomness.
A hash function with 5 bits of output needs more operations than one with 2 bits of output.
Thanks everyone for chiming in and taking time to write your answers! I did know the general concepts behind O-notation, but no doubt I now understand it even better :).
In the same vein algorithmic complexity can be a fantastic first gentle introduction to theory and it's best when tied into writing algorithms in a data structures class. The same can be said about regexps for example - practical v theoretical aspects - or logic as applied with prolog (or even make) say.
The interesting thing (as seen in a comment below about arrays and constant big-O) is that often intuition goes against the the rigorous understanding - so it's best to have both. I suspect the same holds for language as well. For example etymology of word roots as well as actual writing using the words.
But in principle I agree with you. We need a bit of book learning to go with the "just start speaking" approach.
http://www.nthuleen.com/teach/grammar/adjektivendungenexpl.h...
I'm going to make a lame attempt to coin a term and call this the Arch Fallacy, which is when you look at your goal and assume anything not present in it is unnecessary to achieve it. A completed arch contains no supports within it, but you'll have a tough time building one without any.
Funny thing is on first reading, I didn't notice that at all and read it the way you meant. I only saw the typo on a second reading. Interesting autocorrect the brain does.
In any case I like your Arch Fallacy! I think I will use it.
I'll use it too, it's great and I don't recall any term for that particular error in thinking. I've already started spreading it (the name, not the error) among friends, hoping it will catch on.
Native speakers are taught some rules, but many are rarely taught unless a student has learning difficulties. The adjective ordering that OP mentions is a solid example. Others include aspiration of stops; voicing assimilation in words like "bets" and "beds"; the difference between "putting up" and "putting out"; why it's (sometimes) okay to say "Hey fucker" to your best friend, but not to your teacher; and the deletion of nominative arguments in subjunctive phrases.
Second language learners often (maybe always) find more rules useful, for several reasons. However, those who learn the language in highly rule-focused manner often have difficulty actually communicating in the same way that Computer Science professors are sometimes quite knowledgeable about CS theory, but unable to produce good code. Rules are good at telling you what not to do, but bad at helping you be creative.
I wouldn't say that one should learn in a rule-focused manner, but neither should one learn completely by example. A mix is best, even when your goal is to have the rules fall away in the end.
This page has a good video of the combined structure and the process of shifting the roadway load from the temporary bridge to the cables:
http://baybridgeinfo.org/projects/sas
The background image on the page is also nice, showing all three bridges together:
http://baybridgeinfo.org/sites/default/files/images/backgrou...
I'm using Duolingo now and after I'm finished with it I want to get some formal classes to (hopefully) get to a B1 level. I wouldn't call Duolingo immersion learning though -- they explicitly provide grammatical rules (unless you're using the mobile app which lacks some features) and it's very difficult and frustrating to try to do it with your intuition alone.
I also liked the explanation of cases and adjective endings from this site: http://yourdailygerman.com/learn-german-online-course/
As with music, math, programming, one does need a deep foundation to be good but also one needs to develop a feel by repeated effort so that your mind begins to recognize patterns.
(The correct answer is that people's hands aren't wide enough to deal with all twelve notes on the same level, and that particular subset of the notes contains a lot of consonant intervals and barely any dissonant ones.)
Doesn't that seem really stupid to you now or do you still support that stance? Refusing to learn the entire field of music because of one irrelevant detail is pretty appalling.
Similar logic puts some people off of Christianity - x is in the Bible, and we know the Bible is true because the Bible says it is true, therefore x is also true. Hmm. Someone who tries to sell you that logic is also either lying or wrong, now you can't trust either that person or the Bible.
There's a huge difference between "it's not worth our time to resolve this now" and "non-rigorous thought is okay, reality doesn't have to make sense, just do what the high-status people say, they're smarter".
[1] There's a practice in some groups to explicitly say "it works by magic" to avoid false understandings and to flag unresolved issues.
Yes, exactly.
Unless your parents are directing you, childhood is a random walk through the universe of creative possibility.
I had a similar experience with music instruction, everyone taught to the instrument and to the book of music, never any concepts of music theory even to the point of "What's with the sharps and flats over here by the squiggle? Why not put them where I can see them easier?" "Yeah, I don't know, it's kind of a pain, I just write them back in with pencil." "How do you write a new song?" "Oh, it's really hard, you have to be really smart like Beethoven. Don't worry about that, we have plenty of stuff to practice in the book."
Later, in self educating, I discovered key signatures, playing to those keys (and even improvising!), and that I don't have to think about sharps and flats except for accidentals and it makes so much goddamn sense, but no adult I had access to in childhood ever knew or at least none could explain something which was so fundamental, something that actually made music fun and allowed me to create a positive-feedback loop required for consistent practice.
Had I stood firmer on the grandparent's question, rejected instruction sooner (instead of just through confused burn-out), and begun to self educate sooner, I could have avoided wasting a lot of time.
My partner is quite musical though (formally trained), and she's help fill in a lot of the gaps. I'm at the point now where I can fiddle around with different chord progressions and get good-sounding melodies to come out on my own. I get inversions and how they work on the guitar, etc. It's quite cool and way more interesting to me than just learning songs from a book.
Organ keyboards originally had only the long keys (the white keys) because they only had the natural notes of the scale. The accidentals were added later as the short keys, and were added as short keys so you could still play as though they weren't there.
Piano keys are the same because they copied the keyboard from the harpsichord, which copied it from the organ.
The reason the long keys are in C is because a piano is naturally tuned to C. Tighten all the strings a bit to bring it up to D, and all the long keys will be in the key of D.
... briefly, before the piano implodes.
If you're asking "why is it tuned to C", it's probably because C is the key that historically was assigned the letters without any sharps or flats. There's no physical reason for this, it's just a convention (as opposed to, say, octaves, where each octave is half the frequency of the previous).
If you're asking why C got the letters without sharps or flats, I believe you have the Romans to blame for that. They did start with A for their scale without sharps or flats, but it was what we would now call "A minor". Which leaves C as the major scale.
Thanks for the comment, totally agree with moderation. My goal is to ask "Is the structure I'm providing helpful right now?".
There's an implicit assumption that "more structure is better" (especially in technical subjects that can be structured) because it seems official and defensible. It reminds me of many Wikipedia articles -- they grow in length (why not?) and become more precise (why not?) and you're left with a description inscrutable to a beginner.
Calculus, for example, gets my goat because we spend weeks on limits, continuity, L'Hospital's Rule, etc. so students can "properly" understand derivatives. (Never mind that Newton and Leibniz never used them and seemed to do ok.) Showing a circle non-rigorously transform into a triangle to measure its area (Archimedes) gets closer to the meaning of Calculus than a page of epsilons, deltas and tangent lines. One you have the idea, you put in the rigorous skeleton by showing how the formal rules describe the same result.
Appreciate the comment!
"Which little lady are you referring to? The old little lady, or the young "little lady" that is her five-year-old great granddaughter?"
Though order is a syntactic feature, the restrictions on adjective order are derived from semantics, which depend on context. They are not ruled out by the grammar, per se.
Therefore the rule which says it must be "little old lady" is plain wrong.
The fallacy consists of regarding incorrect or incomplete rules as the unvarnished truth which to learn from and imitate.
In "little old lady", "little" applies to "old lady", not "lady" alone.
Either way, the meaning is the same, because semantically, the actual attributes which "old" and "little" denote apply independently to the person indicated by "lady".
This is natural language. One contrived corner-case counter-example doesn't invalidate the general rule.
The problem with natural languages, and especially english, is that there aren't really any formal rules as there are in well-defined maths like algebras.
If there are no rules, how can you skip them?
What I've learned is that you can't teach any type of rule until all it's "prerequisite phenomena" has been experienced. Music education has a bias of more "doing" and experiencing and less "talking" about (or it should at least). So it has a keen way of turning ideas and concepts into action rather quickly. I think many other disciplines in school can learn a bit from how music is taught frankly: there is a very quick turnaround from concept to application/experience and therefore to emotional context of some sort, which really is the end goal to all learning. Why do you care about X?
So if a rule simply is an equation of some sort, or a statement of relationships, then the prerequisite phenomena is making sure every variable is defined within it; so that one can focus solely on the relationships within the objects instead of the undefined variables. This covers many different grounds depending on the style of the learner and the material at hand. Sometimes (rarely) words are enough (if you're building familiar rules into new rules and the experiential phenomena is all done in the mind "ah-ha!") and usually, a student needs to hear the sound of a major scale vs a minor scale and try to describe it with words before telling them what actually makes it sound different theoretically. And even then, there are different ways to explain it. If the student picked up major scales really well (prerequisite phenomena), I will use the modal approach to learning minor scales (it's the major scale but starting from a different note), if the student picks up the scale tones and is better with spacial relationships, they usually already talk about the differences between what they just played as a sharp/flat 6th or 7th scale tone. And there you have it, they've just instructed YOU how they think about a concept.
Music is a great example of how there is no single correct way to explain the theory. First off, music practice and artistic decisions always came first, the theory came later as people tried to understand and teach it. And it is the bias of educators to find a single correct way to understand it within themselves that leads to them only prescribing one way to do something (memorize this!). Teaching really is listening more than it is speaking.
It's deeply disingenuous to compare effortless biologically-determined learning to effortful general learning and think you can apply lessons from one to the other. Even in the example the OP picked, there's a reason that the learners drill the adjective order table, and it's because without the drill they will never learn it at all. Learning a language as a small child is a different process than learning the same language as a late teen or adult, and the results are very different. (Even so, I wouldn't bother instructing people in adjective order... if they do never learn it, it's no big loss.)
On a different, more technical note, OP doesn't quite understand what's going on in the example either. "Vietnamese spicy food" is perfectly standard English; the ordering there is determined by context. "Vietnamese spicy food" is a subset of spicy food, and will be used whenever it's being contrasted with other spicy food, whereas spicy Vietnamese food is a subset of Vietnamese food, and will be used whenever a contrast is drawn between spicy Vietnamese food and other Vietnamese food. (It's correct, however, that in the zero-context case, "spicy Vietnamese food" is preferred. In my analysis, that's more because people are likely to reify the concept of "Vietnamese food", which makes the phrase structure ("spicy" [adj] "Vietnamese food" [noun]) rather than ("spicy" [adj] "Vietnamese" [adj] "food" [noun]).)
Another science class anecdote - first year electronic engineering, the professor is showing us the derivation of transistor gain formula. He started from pretty much first principles, written out a huge formula, and then started to cross things out - "this in practice is close to 1 so we can ignore it", "in standard operating conditions this is pretty much zero" (and poof, half of the equation gone, multiplied by zero) - and kept going until he arrived at the standard I_c = βI_b. It gave me a new appreciation of just how much engineering is basically handwaving parts of reality away.
It's been said (citation needed) that phrases like "tick tock" and "see saw" are in those orders because it's a high or hard vowel before the low or soft (e.g. "tock tick" sounds weird). Maybe that is why "little old" lady sounds more correct to us? I don't know. But the article goes off to draw a parallel to mathematical intuition, and leaves the original grammar problem unresolved, in my opinion.
Incidentally, I usually _really_ like the Better Explained articles.
The adjective order rules are interesting in that we have to reverse-engineer them from our brains, but aren't consciously aware of them. It's apparently an area of ongoing research why certain orderings are correct. (Maybe there's something about the specificity of the adjective, where the more-specific items are closest to the subject.)
I think the higher-level concern is we can get tricked by thinking we need to consciously master the structure in order to be fluent, vs. letting our brain's pattern-matching skills do some of the heavy lifting.
I like the view that this is an open problem and an area of active research, much more than the more conventional, lay-person settling of the issue as "developed an ear for the language" and that's the end of it.
The impressive work of people like Steven Pinker and Chomsky (in his actual academic field) is to look very carefully at different ethnographic groups, and the larger cultures those groups are embedded in. By doing so, finding groups isolated enough or with a materially different context, such that they don't exhibit the same patterns.
The title of the article felt like a bait-and-switch, I guess. When I realized it was on betterexplained, it did make more sense that it was ultimately about mathematical reasoning. No worries!
That does make it different from mathematics, where there are reasons for the rules (you can't divide both sides of an equation by a value if that value might be zero, for example). But the point is more to suggest that it could be possible to make progress in carrying out and understanding mathematics without understanding some of the formal underlying rules beneath a concept. That seems like a valid point.
http://english.stackexchange.com/questions/1155/what-is-the-...
Formalizing it would be about as silly as formalizing which music sounds good.
(If that isn't what you mean, then what do you mean? That linguists should carry on, but not look for patterns and rules? Then what, instead?)
Also, what is a "linguistic construct" if we don't have formal rules? Whatever it is, wouldn't it be less ironic to call it a "speaking thingy"?
To say there are formal rules of language is a bit like saying there's only one culture that is fit to judge the acceptability of your words.
Saying the rules shouldn't exist is like saying Newton's laws shouldn't exist -- they are just patterns that someone has noticed.
While there seem to be exceptions to most rules proposed (because natural usage is complex), the rules are still fairly accurate for most cases.
So why do it? To make observations? Observations don't need formalization; just provide good statistics.
This is not the case for other cognitive skills, such as reading and (to our point) mathematics. My son cannot learn calculus simply by hanging out in my office. While our end goal may be the sort of effortless intuition in mathematics that we experience in parsing complicated sentences, the process of acquiring those two skills is of necessity widely divergent.
[0] - For things you learn to use all the time, or to leverage your cognitive process. The obvious exceptions are things you want to do with mindless precision, where the risk of guessing wrong is unacceptable. Compare public speaking to memorizing a poem, or guesstimating to doing explicit pen and paper arithmetics.
http://mysite.science.uottawa.ca/mnewman/LockhartsLament.pdf
I suspect what happens is that students forget some of the good basic ideas (or is that "basic good ideas" ;-) ) they were taught, and teachers fail to re-emphasize them to keep students on track, and so all they remember is the formal/abstract techniques they spent a login time struggling with. Painful experiences stick in our memort more than smooth easy experiences.
It's just memory, we recite timeworn phrases because that's what we hear over and over.
Non-native speakers use phrases that "sound wrong" only because they are synthesizing from principle or from their own language, and haven't heard the usual phrases over and over.
This is where rule-based language analysis runs aground.
So why, when someone shouts out "Look out for that robot purple tiny Mexican goat!" you would immediately peg them as not a native English speaker, but if they had said "Look out for that tiny purple Mexican robot goat!" you would not?
This is not a 'fixed phrase' thing. There are rules, you're just not consciously aware of them.
No, it does to a degree. The rules are inferred from observation and internalized, but not precisely. "little" before "old" is a rule, almost motoric. As a foreign speaker I agree that isn't a logical rule :)
edit: I guess, the author is looking for the term heuristic (a general rule that is right often enough, but not precise nor complete).
So everyone has a different spidey sense.
Until you get into regional dialects and slang.
It only sounds off if you are accustomed to reading correct English. I do a lot of reading, and I think that is what developed my ear for phrases which are 'incorrect'.
I can't tell you what a participle or things like that are because I haven't been formally trained, but I can tell you which sentence from a list is the correct one.
I hear some people talk and I'll shake my head as I hear them slaughter the English language, but then I realize they probably don't do a lot of reading and didn't get far and school and that's just how their peers talk, as incorrect as it may be.
language is not something that's set in stone - it constantly changes. I would encourage you to be curios and try to learn something from others ways of speaking.
Something not matching your expectations / what is commonly seen as the 'right' way does not make it wrong.
IMHO judging people that don't read or didn't get far in school is plain wrong.
Such a poor headline.
Unless we grew up speaking a different language, or were born to people who didn't have English as their first language. My wife has been in the US since the age of 2 and speaks perfectly but she still has a few minor linguistic tics that a second-generation native speaker wouldn't, and is she shy if she comes across a word she's not sure how to pronounce or whose meaning is unclear.
Having taught English as a second language to people from a wide variety of backgrounds, I don't expect anyone to memorize the royal order of adjectives, but it's incredibly useful for them to know that there is an underlying system and to match patterns of adjectives from their reading material against it, or play games with it (like thinking deliberately wrong phrases such as 'old little lady' for comic value), or be able to refer to it if they're nervous about writing something. The same is true for people who miss out on a proper education because of domestic or socioeconomic problems and maybe come to literacy as adults, but never develop the total confidence of someone surrounded by language since birth. Incidentally, those of you who live in California may have noticed the public information campaign encouraging parents to talk and sing to children, especially babies and toddlers. Research indicates that this has a massive influence on brain development and subsequent success or failure in life. See http://www.economist.com/news/science-and-technology/2159692... for an overview.
So yeah, of course the best way to acquire language is to be in a linguistically rich environment, and just soak it up to develop an intuitive understanding that promotes linguistic creativity and wordplay, as opposed to studying it through formal methods and turning it into a philological exercise. But that does not mean that formalism is bad, or that we should conceal the existence of systematic structures from kids in case it will wreck their creativity or something - if for no other reason, than to spare them the waste of reinventing the wheel should they be inclined to adopt a formalist approach on their own initiative. It's very easy to handwave away such rigid-seeming pedagogical tools if you already enjoy the benefits of total fluency, but for those who do not enjoy the same advantages this is the equivalent of pulling up the ladder behind oneself and then critique the confused for poor listening skills.
I don't have a comment on the math part - I agree with the author that we ought to be open to using multiple learning techniques so that each student can find the best one, but I think he seriously underestimates the utility of formality. When I was 5 I thought chanting multiplication tables every day at school was a bit silly, but 40 years later I greatly appreciate the fact that I can handle everyday trivial math problems reflexively rather than needing to reach for a calculator, pencil and paper, or a mental script of how to perform the calculation. Repetitive drills and formal methods are not the best way to explain new concepts, but they are incredibly useful exercises to retain them and make the basic knowledge feel instinctive in later years.
I remember our English teacher giving us one single lesson on conjugation, and that was only because we were so confused by all the stuff about conjugating verbs in French class. Other than that I cannot remember us going near any kind of formal grammar.
edit - I just thought, it is also not that hard to construct a context in English where 'old little lady' can work.
I looked again at the little lady sitting across from me. At first, from her height, I had assumed her to be young. However now, looking closer, I could see she was a very old little lady indeed.
Calculus, by comparison, is built on firm rules about what you are allowed to do and what you can't, when cutting a shape up into pieces and rearranging them. The piece is arguing that it might be possible to make headway in calculus by just being exposed to usage, and the formal rules can be kept to later. That seems quite compelling.
Yep, I should have probably made that clear. Was more side commenting through the metaphor. In general, learning English like that works quite well, but then it throws you when you are then asked to conjugate the verb 'to be' in French class and nobody has ever asked you to ever conjugate a verb in English. You end up knowing how to use English, but do not learn the technical terminology required to dissect it.