[HN Gopher] Google researcher, long out of math, cracks devilish...
___________________________________________________________________
Google researcher, long out of math, cracks devilish problem about
sets
Author : kentricon
Score : 237 points
Date : 2023-01-03 19:43 UTC (3 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| acctant wrote:
| > He also worked with a textbook by his side so he could look up
| formulas he'd forgotten. "You'd think someone who comes up with a
| great result shouldn't have to consult Chapter 2 of Elements of
| Information Theory, but I did," Gilmer said.
|
| Always enjoy seeing this sentiment reaffirmed. Funny that Gilmer
| states it in a somewhat self surprised tone.
|
| Rings of the Einstein quote:
|
| "[I do not] carry such information in my mind since it is readily
| available in books. He also said, "...The value of a ...
| education is not the learning of many facts but the training of
| the mind to think."
| mkoubaa wrote:
| I do not carry such information in my mind since it is readily
| available on stack overflow
| apricot wrote:
| Without needing to commit many facts to memory, one
| nevertheless needs to know which facts are known, and how to
| get to them if need be. Otherwise all the time will be spent
| reinventing the wheel.
| [deleted]
| mturmon wrote:
| Chapter 2 of that excellent book by Cover and Thomas is the
| roundup of all the definitions of entropy, relative entropy,
| mutual information, etc.
|
| I think it's the first place I ever saw the "Information
| Diagram" (https://en.wikipedia.org/wiki/Information_diagram)
| which is a Venn-like diagram that really helps to remember all
| these relationships.
| mandmandam wrote:
| The _vast_ majority of academic "achievement" measures are
| centered on tests which entirely disallow looking things up.
|
| Especially in poorer public schools, learning is modeled as
| recitation. It's awfully sad. Most students are lucky if they
| get one or two teachers that break that mold.
| jobs_throwaway wrote:
| "The value of a ... education is not the learning of many facts
| but the training of the mind to think."
|
| While anyone with a (good) STEM education knows this to be
| obviously true, its frightening how many people go through 16+
| years of formal schooling where they mostly do rote
| memorization and regurgitation.
| tester457 wrote:
| We can thank the academic system and Goodhart's Law for that.
|
| We measure students with tests, but all we get are people
| good at taking tests and rote memorization.
|
| Maybe if we had a better way to access actual learning but
| are teachers even paid enough to truly care?
| bobkazamakis wrote:
| >Maybe if we had a better way to access actual learning but
| are teachers even paid enough to truly care?
|
| There's no incentive to pay teachers more; system is
| working as designed. Those students aren't giving short-
| term quarterly gains.
| jobs_throwaway wrote:
| Tests have their place though. The more rigorous maths
| exams I took in school were some of the most intellectually
| challenging things I did in school. If written correctly,
| they require you to apply the things you've learned in
| novel ways, or to combine the topics you've studied in new
| ways. Problem is, IME there's very few professors/teachers
| qualified and devoted enough to develop those sorts of
| exams, and as soon as you try to 'scale' it by centralizing
| the test creation, you run into the same issue of students
| simply learning for the test.
| Someone wrote:
| I think math is somewhat special in that it isn't about
| solving specific problems, but about learning to
| recognize patterns, and that the tests don't check
| whether they know the patterns, but whether they can
| apply those patterns to problems that they need not even
| have ever seen.
|
| In many other disciplines applying what students learned
| to things they've never seen before isn't really
| possible.
|
| For example, you can teach students what factors were
| needed to start the Industrial Revolution and why, but
| then, to answer "why didn't the Industrial Revolution
| start in the 1750s in South America?" students would have
| to know about South America in the 1600s. If they don't,
| all they can answer is "it must be because not all of the
| prerequisites foo, bar, baz, ... were available, but I
| wouldn't know which one(s)".
|
| Because of that, that question isn't better than the dull
| "why did the Industrial Revolution start where and when
| it started?", the answer to which can be learned by rote
| learning.
| jobs_throwaway wrote:
| You make a good point. I believe that there are ways to
| get students outside of maths to apply what they've
| learned to things they haven't seen before, though it
| won't be as novel or challenging as a maths exam. In
| history for example, you could have students analyze
| primary sources they've never encountered, which would
| require them to apply their knowledge of the context to
| something novel. Definitely more challenging than in STEM
| though.
| anonymousDan wrote:
| Writing a hard/challenging exam is not difficult. The
| problem is most bad or even average students will fail.
| The tricky part is striking a balance such that the good
| students feel pushed, and the weaker students still have
| a chance to demonstrate they at least engaged and
| understand the basics.
| adamisom wrote:
| I think it's mainly that STEM majors are smarter, and
| thinking is hard slash unmotivating.
|
| Of course any non-STEM field has geniuses, but our
| impressions--like the parent's--are formed from averages, and
| STEM majors are smarter on avg.
| triyambakam wrote:
| > its frightening how many people go through 16+ years of
| formal schooling where they mostly do rote memorization and
| regurgitation.
|
| That's how most education is structure, though. Unless your
| point is simply that, though it reads as if you're blaming
| the student.
| jobs_throwaway wrote:
| Students do share some of the blame, at least once you get
| to high school and university level. No one forces
| (university) students to take easy courses that don't
| require rigor. As long as people are willing to shell out
| full-price tuition for a degree that doesn't require you to
| do more than rote memorization and regurgitation, schools
| will continue to facilitate it.
| agar wrote:
| The article title has been revised to more accurately reflect the
| researcher's position (and removes the AI ambiguity): "Google
| Researcher, Long Out of Math, Cracks Devilish Problem About Sets"
|
| Should the title of this HN entry be updated accordingly?
| dang wrote:
| Ok, done. Thanks!
| warrenmiller wrote:
| "long out of math"? he did his Ph.D. in 2015. - surely 7 years
| is not that long! :)
| thethirdone wrote:
| > "Mike said, 'Justin, you're going to get me thinking about this
| problem again and I don't want to do that,'" said Gilmer.
|
| This is a very relatable feeling. I often find myself getting
| trapped into thinking about problems I am unlikely to solve.
| jihadjihad wrote:
| Reminds me of the multi-armed bandit problem, where Allied
| scientists considered it to be so intractable that they
| proposed dropping it over Germany so their scientists would
| waste their time on it.
| [deleted]
| LAC-Tech wrote:
| Just do what I do, focus on easy problems! Doesn't take that
| long but you feel great anyway.
| marktangotango wrote:
| > This is a very relatable feeling. I often find myself getting
| trapped into thinking about problems I am unlikely to solve.
|
| I have this problem as well. The most disturbing thing is
| retracing old paths to dead ends without realizing it. Here I
| mean internal mental models, but also applies to previously
| known results I just wasn't familiar with, and don't turn up
| unless specific phrases are known.
| tills13 wrote:
| I find it's a cruel trick people, usually inadvertently, play
| on me at work: "when you've got a sec can you look at x?"
|
| There's a portion of my brain that's immediately hijacked and
| starts thinking about the problem whether I'm actively working
| on it or not.
|
| Happens to me for work problems outside of work, too. I'll just
| be chilling in the shower or something and suddenly I'm
| thinking about a work problem.
|
| Maybe one day I'll retire from programming and do something
| less theoretical e.g. driving a semi.
| [deleted]
| chris_overseas wrote:
| The obligatory XKCD https://xkcd.com/356/
| tpurves wrote:
| Damn you! Now all I can think about is that xkcd problem.
| hgsgm wrote:
| Bad idea. Don't drive and derive. You'll be driven to
| distraction and crash.
| moritonal wrote:
| Yep, same. About once a year I get sucked for a day or so into
| the Noita Eye Messages puzzle
| (https://noita.fandom.com/wiki/Eye_Messages).
| thomasahle wrote:
| Paper link: https://arxiv.org/abs/2211.09055
|
| Abstract:
|
| We show that for any union-closed family F\subseeq
| 2^[n],F[?]{[?]}, there exists an i[?][n] which is contained in a
| 0.01 fraction of the sets in F. This is the first known constant
| lower bound, and improves upon the O(log_2(|F|)^{-1}) bounds of
| Knill and Wojick. Our result follows from an information
| theoretic strengthening of the conjecture. Specifically, we show
| that if A,B are independent samples from a distribution over
| subsets of [n] such that Pr[i[?]A]<0.01 for all i and H(A)>0,
| then H(A[?]B)>H(A).
| [deleted]
| naillo wrote:
| The title makes it sound like an AI solved it but he's just a
| programmer who normally works on AI that happens to have solved
| it.
| [deleted]
| kataklasm wrote:
| > (i.e. clickbait)
|
| It is not clickbait just because you interpreted it wrongly.
| The AI in the title only aims to demonstrate his state of out-
| group in regards to math.
| rkp8000 wrote:
| Always cool to see unexpected applications of information theory,
| especially outside of probabilistic contexts.
|
| A related toy example that comes to mind is the puzzle where
| you're given 12 metal balls and told that one of them is either
| heavier or lighter than the rest. You're then given a
| balance/scale and instructed to figure out which ball is
| different and whether it is heavier or lighter using the balance
| a maximum of three times to weigh different combinations of
| balls.
|
| Part of the reason this is solvable is because there are 12x2=24
| different possibilities (or log2(24) = 4.58 bits) for the ball
| ID/weight and 27=3x3x3 possible outcomes (or log2(27) = 4.75
| bits) for the weighing process (left heavier, right heavier, or
| equal in each use). Thus, there's a chance the weighing sequence
| could convey the ball ID/weight. If there were 14 balls, however,
| then you would require log(28) = 4.81 bits of information to
| specify the ball ID/weight, so the puzzle would be unsolvable,
| since there wouldn't be enough information available in the
| weighing sequence to specify the ball ID/weight.
| koolba wrote:
| The 12-ball problem is a fun one and IMO the key revelation is
| that you do not need to determine whether the ball is lighter
| or heavier (which isn't possible anyway). Just which ball is
| different than the rest. It's a great exercise in decision
| trees as you change your strategy based on total information,
| not just the most recent step.
|
| It's also fun to scale the problem from 3 balls up to see how
| the solution evolves.
| hgsgm wrote:
| Scale down first! Interesting patterns start from 0 and 1.
| thaumasiotes wrote:
| >> you're given 12 metal balls and told that one of them is
| either heavier or lighter than the rest. You're then given a
| balance/scale and instructed to figure out which ball is
| different and whether it is heavier or lighter using the
| balance a maximum of three times
|
| > The 12-ball problem is a fun one and IMO the key revelation
| is that you do not need to determine whether the ball is
| lighter or heavier (which isn't possible anyway).
|
| Huh?
| vgb2k18 wrote:
| If I'm reading this [0] right, the heavier/lighter factor
| can be determined within 3 weightings... [0]
| https://suresolv.com/brain-teaser/find-fake-ball-
| among-12-id...
| thaumasiotes wrote:
| Of course it can. There are 24 possible states and you
| get enough information to uniquely identify one of 27
| states. This was already stated in the root comment.
|
| I'm confused how the response to "you must identify
| whether the odd ball is heavier or lighter" can be "the
| key to this is realizing you don't need to know whether
| the odd ball is heavier or lighter, which is good because
| that's impossible anyway".
| geenew wrote:
| There's an episode of Columbo with a similar problem, expressed
| as: there are a number of bags. Each bag contains many gold
| coins. The gold coins weigh 1 ounce each. However, one bag
| contains fake coins, which appear the same as the real coins,
| but have a slightly different weight - 1.1 ounces per coin. You
| have a scale, which you can only use once, and you must find
| the bag with the fake coins.
|
| The solution is: Take one coin from the first bag, two coins
| from the second bag, three coins from the third bag, etc. Weigh
| all of the selected coins at the same time to get a total
| weight. Subtract from the total weight the triangular number of
| the number of bags[1], in ounces. The remainder, divided by
| 0.1, will be the number of the bag with the fake coins.
|
| [1] eg, for three bags, 1 + 2 + 3 = 6
| SideQuark wrote:
| I once made a cool solution to this problem using information
| theory, in particular coding theory.
|
| The usual solution uses the fact there are 3 places to put
| items: left scale, off scale, and right scale. Then those
| solutions do if/then cases to juggle items around to find the
| mis-weighted ball.
|
| My solution numbered the balls in base 3, then did four
| weighings with no if/thens,. The weightings each gave a base 3
| result: left, balance, right. This formed the digits of the
| mis-weighted ball.
|
| The idea is to make an error correcting code in base 3, and use
| the "weighings" as the correction matrix to isolate the bad
| "bit".
|
| This idea generalizes to solve a massive range of find the odd
| item(s) problems.
| polishdude20 wrote:
| Can you explain how you weigh the balls? How many do you
| weigh at a time and how do you decide which ones to weigh?
| I'm trying to follow your solution but I'm confused about
| this one thingn
| hgsgm wrote:
| That's clever! If you get an "equal" result from the scale,
| then you can put those balls on the scale with the unknown
| ones, so you can maintain symmetry in the weighings.
| jacquesm wrote:
| That is a beautiful solution, wow. I'm just floored by you
| coming up with that, it is so utterly out of the box.
| andrewljohnson wrote:
| I always thought of bit boards in the same way, wow moment.
| actually_a_dog wrote:
| It is a beautiful solution, but it's not _terribly_ out of
| the box. It 's similar to generating all subsets of a set
| of N items by iterating through the integers 0..2^N - 1 and
| checking to see which bits are set.
| thaumasiotes wrote:
| As stated, it's not a solution at all - it uses four out
| of three possible weighings.
| bornfreddy wrote:
| GPT, how do I prove that...?
| [deleted]
| kibwen wrote:
| Similarly, I assumed from the headline that he had used the AI
| to help him determine the proof.
|
| As for using AIs as mathematical proof helpers, I threw it the
| following softball and can't say that mathematicians should be
| too worried just yet:
|
| _> > Please prove that the first decimal digit of pi is 3._
|
| _> The value of pi is an irrational number, which means that
| it has an infinite number of decimal digits that do not repeat
| in a pattern. It is not possible to prove that any particular
| decimal digit is the first decimal digit of pi, because the
| decimal representation of pi is infinite and does not repeat.
| However, the first few decimal digits of pi are widely accepted
| to be 3.14, so the first decimal digit of pi is generally
| assumed to be 3._
___________________________________________________________________
(page generated 2023-01-03 23:00 UTC)