Cantorian Sets: "Beyond Infinity - An expedition to the outer limits of the mathematical universe" by Eugenia Cheng

“If this be not that you look for, I have no more to say, but bid Bianca farewell for ever and a day.”

In “The Taming of the Shrew” by William Shakespeare (quoted by Cheng in the book)

Eugenia Cheng starts by saying right at the beginning of the book, "Infinity is not a number," and I think it really helps to get that misconception out of the way at the start. As soon as we one gets past that hurdle the rest is just a piece of cake.

As pointed out numerous times by Cheng, Cantor is the accepted authority on this, but are there alternatives?

Cantor Infinities

Key Idea: You can put the even numbers in one-to-one correspondence with the whole numbers and say that this demonstrates they have the same cardinality.

1->2

2->4

3->6

...

This shows that the set of whole numbers is the same size as the set of even numbers.

This seems counter-intuitive - and it's usually a real challenge to anyone encountering it for the first time, but if you do accept this then all sorts of deep and interesting mathematics follow. The way I think about this is, it's not a natural property, it's not a statement about the world*; it's Cantor's definition of infinity, let's go along with it and see what happens.

Non-Cantor Infinities?

But what about the intuitive (naive, even) point that that in between the even numbers you have the odd numbers, therefore the set of even numbers is smaller than the set of whole numbers?

2, 4, 6, 8, 10, …

is obviously smaller than

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

Therefore, the set of whole numbers is obviously bigger than the set of even numbers.

There's a hidden assumption that if I add an element to a set then the set gets bigger. That seems like a reasonable assumption to me. Are there "non-Cantor infinities"? To understand current thinking on infinities one must understand Cantor, but maybe one should also consider alternatives.

What Cheng proposed is nothing new in the field of number theory dealing with Infinity: “The general question is: How should we compare the size of infinities? So far, we have decided that the real numbers are unaccountable, that is, that there is no possible way to match them up precisely with the natural numbers because some real numbers are doomed to be omitted. Intuitively this means that there must be ‘more’ real numbers than natural numbers, but what could this possibly mean if they’re both infinite? Some infinities are bigger than others – how is that possible, seeing as infinity is already infinitely big? Isn’t it the biggest thing that there is? How can anything be bigger that it? Just like questions of the soul, everlasting life, and whether or not I’m fat, this comes down to definitions.

The way to dealt with infinities is the following: Start with a simpler question. How do you determine if two finite sets are equal in size? The basic process is to place the two sets in one to one correspondence.  This is key to answering the question about infinities. I know that I have the same number of fingers as toes because I can pair them up with none left over. I know that I have more ears than noses because when I attempt to pair them up I find I make one pair, say nose paired with left ear, and have one ear left over. Now this "one to one correspondence" sounds a bit of an odd process - after all why not simply count each set? The reason is because for infinite sets you cannot count them. But even for infinite sets you can still apply the very basic process of placing it in one to one correspondence.

And as Cheng so ably demonstrates, this can be done for some infinities such as the integers, the prime numbers, the rational numbers so they are equal in size, but fails for others like the integers and the reals. The mathematical proof is quite far more rigorous than that, but the key idea is that simple.

Take the Hilbert Hotel Paradox which Cheng uses throughout the book (bear with me; I’m going to rephrase Cheng here). You have an infinite amount of rooms in your hotel. An infinite amount of people turn up. You fit them one per room. Fine. Then a new person turns up demanding a solo room. How to fit them in? Easy. Move the person from room 1 into room 2, the one who was in 2 into 3, and so on. Infinite amount of people, infinite amount of rooms, all have a room, but now room 1 is free. Infinity + 1 = infinity. Then an infinite amount of new people turn up. They also demand solo rooms. How to fit them in? Easy. Move the person from room 1 into room 2. From room 2 into room 4. From room 3 into room 6. Now you have an infinite amount of odd numbered rooms free. Infinity x 2 = infinity.

So far so good.

But imagine trying to count up all the possible fractions. Someone gives you an infinite list of numbers where the decimal points go off to infinity. You start numbering them; the first one is no. 1, the second is no. 2, and so on. And you do it. You number them all, 1 to infinity.

Then that someone plays a trick. The first set of decimals are like this:

0.11111...

0.2222...

0.3333...

0.4444...

0.6745969...

What they do is change one number in the decimal expansion. They change the first digit of no. 1, the second digit of no. 2, the third digit of no. 3. And so on to infinity. You've now got a number that starts 0.23451..., which is different in at least one digit to every single one that you've numbered to infinity.

You can't add it to the list. Your list of fractions is therefore bigger than your infinity.

This is therefore a second, bigger, infinity than the one of all counting numbers. The infinity of counting numbers is called aleph-null; that of all fractions as well (real numbers) is called R. And you can take this further into ever more mind-boggling and inexplicable higher levels of infinity. If you can prove there are any infinities in between these two, or even that there are no infinities between these two, you would get lots of buns from the mathematical community.

What about the primes which Cheng barely mentions? First, the number of primes is the same as the number of normal (natural) numbers (which is also the same as the number of perfect squares). This is because they can be put into a one-to-one correspondence like this:

1.............. 1st prime number.............. 1 squared (1)

2.............. 2nd prime number............ 2 squared (4)

3.............. 3rd prime number............. 3 squared (9)

4.............. 4th prime number............. 4 squared (16)

...

1000........ 1000th prime number....... 1000 squared (1,000,000)

...

Billion....... Billionth prime number.... 1 billion squared

...

So - and this is counter-intuitive - there are not "more natural numbers" than there are primes or perfect squares because for any natural number, you can match it to a prime or perfect square. This is a peculiar property of infinite series like this - that you can put them on a one-to-one correspondence with a subset [It's also possible to order the rational numbers (fractions) like this. So, the number of factions - 1/2, 3/4, 7/8, etc. - is the same as the number of natural numbers. Again, counter-intuitive.]

However, there are still different sizes of infinity. In fact, there are an infinite number of sizes of infinity. These are called Aleph-Null, Aleph-One, Aleph-Two, etc, (and there are also sizes of infinity that fall outside this series). There are Aleph-Null natural numbers, Aleph-Null primes, Aleph-Null perfect squares, Aleph-Null fractions/rational numbers. There are more than Aleph-Null real numbers though (real numbers include irrational numbers like pi or the square root of two that cannot be expressed as a fraction).

In the 19th century, Georg Cantor showed how to compare the sizes of sets, including infinite sets, by putting the elements of the sets into one-to-one correspondence. Here you can think of a set as just a collection of objects, e.g. numbers. For example, in the finite case, you can put the elements of the sets {1,2,3} and {4,5,6} into 1-to-1 correspondence, or pair them off, showing they are the same size: 1<->4, 2<->5, 3<->6. You might say you could just count the elements in both sets and see that they are the same size, but the action of counting is in fact putting the objects being counted into one-to-one correspondence with the counting numbers, if you think about it.

One can think of finite examples where one can prove two large sets are the same size without having to count them. E.g., at a mass wedding of Moonie couples, if there are no men and women left over in the stadium then we know there are an equal number of men and women i.e. the men and women have been put into a (romantic) one-to-one correspondence, so the set of men is the same size as the set of women, but we don't know the size.

In the infinite case, we can't count the elements of the sets but, like with the Moonies, if an infinite set can be put into one-to-one correspondence with the infinite set of counting numbers or natural numbers, namely {1,2,3,4,5,6,7, etc.} then we consider it the same "size" as the set of natural numbers and we say that infinite set is "countable". Note that strict subsets of the natural numbers can be as "big" as the set of natural numbers. e.g. the set of even numbers {2,4,6,8,10, etc.} is missing half the natural numbers but is countable. To see this, you need to put the even numbers in one-to-one correspondence with all the natural numbers. This is easily done: 1<->2, 2<->4, 3<->6, 4<->8, 5<->10 etc. It can be proved that every even number will be in this list (just divide it by 2 to find its partner). Therefore, the set of even numbers is the same size as the set of natural numbers and so is countable. 

You provide two infinite sets of numbers in your question. The set of primes was proved infinite by Euclid, and the normal numbers or composite numbers are simply made by multiplying the primes together and so the set of composite numbers is also infinite. The set of primes and the set of composites are subsets of the natural numbers. The natural numbers have a natural ordering, namely, 1<2 1-to-1="" 1="" 2="" a="" also="" and="" any="" are="" argument="" as="" be="" biggest="" both="" by="" can="" composite="" composites="" correspondence="" countable.="" countable="" each="" etc.="" for="" idea="" in="" into="" is="" it="" makes="" match="" matching="" natural="" nbsp="" next="" number="" numbers:="" numbers="" of="" other.="" p="" prime="" primes="" put="" same="" sense="" set="" size="" smallest="" so="" subset.="" subset="" taking="" the="" then="" therefore="" used="" we="" with="">

Cantor also proved that the set of real numbers (all the finite and infinite decimal numbers e.g. 2, 4.5, PI, sqrt(2), etc.) cannot be put into one-to-one correspondence with the natural numbers and is therefore uncountable. (see: https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument). So, in some sense the infinity of real numbers is "bigger" than the infinity of natural numbers. This answers one’s other question: there are many degrees of infinity.

The confusing part is this. If I have a bag of all the natural numbers and take natural numbers out one at a time in the order 1,2,3,4,5, etc., then whatever natural number you may come up with, however big, I will eventually draw it from the bag given enough time. The point is that the same is not true of the real numbers. If you have a bag of all the real numbers and take real numbers out one at a time, in whatever order, I can build a real number (in fact many real numbers) as you do this which you will probably never draw out of the bag. This is shown by Cantor's diagonal argument also used by extensible by Cheng.

The question then is: who cares if there are different size infinities? Well, the set of real numbers, which Cantor showed to be uncountable, is required for calculus which is crucial to physics, engineering, applied maths, etc. And in fact, some mathematicians are sceptical of these ideas about infinity and try to prove calculus theories using only finite maths.

Also, Cantor considered the obvious question: is there an intermediate infinity strictly between the infinity of the natural numbers and the infinity of the real numbers in size? Cantor conjectured that there was no such intermediate infinity and this is known as the Continuum Hypothesis or CH. Cantor apparently went insane trying but failing to prove it. In the 20th century, Gödel and Cohen showed that CH can neither be proved nor disproved from the accepted foundations of mathematics, which explains why Cantor couldn't prove it - it's not provable nor is it disprovable! So, CH is an example of a mathematical statement which is undecidable, and is part of the crisis in the foundations of mathematics. 

This is one of the top experts in the field, Hugh Woodin, explaining the current state of play in this crisis:

In an ironic faint echo of Cantor's descent into insanity over a century ago, in this talk Woodin says that 15 years earlier he believed CH was false, and now he believes it true!

How bad is this mess in Maths? Well, to prove that arithmetic (+,-,x,/) is consistent i.e. that you won't end up with contradictions, you need to first build a bigger system than arithmetic in which you can prove the consistency of arithmetic. But you then can't prove the consistency of the bigger system without building an even bigger system, and so on. So, it's theoretically possible that a primary school child doing their sums could end up proving 0=1, which is clearly a contradiction. No mathematician believes this will happen, but no-one can prove it won't currently. The video shows the lengths mathematicians have gone to try to resolve this issue.

Cheng's book is what you need to study first before you can get an idea of what the video is about, although the talk is considered as aimed at the layperson.

It's when Cheng started tackling Calculus and the infinitesimal small that things started going downhill.  What happened to Newton and Leibniz???

Machine Learning Made Easier (or NOT!): "The Master Algorithm" by Pedro Domingos

Published September 22nd 2015.

How can one become an expert in ML? All one needs is a basic background in (multivariate) Calculus, Linear Algebra, and Probability. ML is math. If one wants to understand the techniques, one has to understand the math. No shortcut. If one wants to start looking into the field of ML, this book is for you. If not, stay well clear.

My background is in computer science and software engineering and I've been interested in ML since I can remember. In 2013 I took Andrew NG's ML class at Stanford University (for those of you who want to dive into stuff like this here are mynotes of the class; while learning the needed math can look daunting at first it is actually quite fun once you get into it), and I was never literally the same…After that I made some Python coding to get a feel for the real thing, which I’m still doing to this day.

Humans ARE machines, albeit biologically-based. Billions of highly interconnected neurons receiving sensory input, lots of internal feedback, and signals that go out to motors, etc. Emotions, feelings, consciousness, are all just “concepts” we've constructed through a mixture of self-introspection and communicating with other self-introspecting machines (humans).

Some questions important to me in the field of ML:

"How does one simulate emotional pain input and response in a robotic system?"

Simulation is not the goal, (Searle was sort of right, but I don't think any simulation would ever pass the Turing test anyway). But we will (eventually) build a real machine, with billions of interconnecting self-modifiable neurons, then we take a screw driver and poke it in a sensor and ask it if that hurt. Assuming we've wired up some vocal system, it will scream "YES!".

"What is the true purpose of emotions in human beings?"

Emotion is just our own thoughts, with some extra chemical feedback thrown in, resulting in what we call 'feelings' (anger, elation, euphoria, depression, etc). The machine we build will claim to have all these, and who are we (as external observers) to argue with it? When it sticks a probe into an electrical socket, it will hurt, and after a just a few trials, it will probably avoid it because the negative pain outweighs the curiosity.

"How does the animal-like instinctive brain and the emotional brain aid or hinder the logical learning brain?"

This division (and hence any resulting interaction) is a contrivance. But I think the point you are raising can be addressed with a simple: all aspects (neurological firing patterns) are interconnected with multiple levels of feedback loops etc. Everything affects everything. This is basically how our brains are wired up.

"How would creating a human like self-thinking/self-evolving device such as a humanoid robot effect society and morality?"

How does creating a human (self-evolving child) such as a humanoid effect society and morality? As most responsible parents will say, one has to train and teach the child to choose good behaviours over bad. A robot-creator could use moral stories, time-out, spanking (poking that screwdriver), or whatever method is in vogue in their time/culture. There's no end to the methods humans have created to choose from.

If one just drops the idea that humans have any mystical “thing” inside them (mind, soul, consciousness, whatever) and realizes that humans are just machines and nothing more, (albeit extremely complicated and marvelous), then real AI is just a technical problem. We've just not built it yet.

Domingo’s book gives us several ML algorithms/paradigms without delving into the math. I understand why the author did this but I can't say I agree with the approach. It is important to realize that this book is not an easy one, despite being devoid of math. In order to “understand” ML, one will need to understand the math behind all the algorithms. Having said that, it is not really a gentle introduction to the topic.

One of the topics that didn’t get much exposure in Domingo’s book was “can we use ML to vectorize?” Genetic programming should be the “tool” to use to create code to vectorize. In Domingo’s book thus topic did not get much exposure time.  Genetic algorithms may be able to learn such algorithms... just as you may be able to measure the width of your bookcase with a super-high-resolution, super-powered GPS-type system.  It doesn't make it the best tool: use a measuring tape!  The amount of time it would take a genetic algorithm to learn to be as effective as some of the recipes we have learned here is very long, I suspect.  So finding someone who knows what they're doing will still be a more effective strategy than getting a genetic algorithm system and just waiting and hoping it will work.  And, even then, ML expertise will be valuable in ensuring the genetic algorithm is not overfitting to training data, in tweaking it so it will reach a better solution faster, without falling into local optima.  Finally, there is well-understood mathematical theory behind the algorithms we learn.  There are proofs about how long each algorithm will take, how effective each is, how well it will scale to large data, and other aspects.  The results of genetic algorithms will only have one property: the genetic algorithm that produced it says "Trust me!  It works (as far as I know)!”

I was expecting to see more stuff on search engines, but that didn’t happen. I think Domingos thought it was a very specialized topic to approach in a book of this kind. The thing about search engines that is really interesting is that people are constantly trying to manipulate them to get their sites to rank. For this reason the ML algorithms have to be incredible complex so they can not only show the best results logically but also work out what sites are the sites which seem too good, but are actually very clever spam. I'm pretty sure that there must be a fair bit of ML going on in that. Just the amazing accuracy of the spelling correction in Google alone is pretty impressive. I thinks it's at least 20 times better than at working out my clumsy keyboard mashings. Hyperlinking is also a major factor in how they rank pages and this is one of the most manipulated and spammed areas of the internet. Check out pagerank on Wikipedia. They must use tons of ML to detect patterns of links and work out if they are natural or not. Thing is the algorithm is so good it's not really worth manipulating but it's very interesting to learn about.

Jason Brownlee released a preview of his new book titled “Clever Algorithms: Statistical Machine Learning Recipes”. The beauty of this book is that it is all about code. Each chapter tackles a particular machine learning algorithm. For each algorithms he gives a strategy, heuristic and usage code implementation in R programming language. According to the author: “Implementing ML algorithms is difficult. Algorithm descriptions may be incomplete, inconsistent, and distributed across a number of papers, chapters and even websites. This can result in varied interpretations of algorithms, undue attrition of algorithms, and ultimately bad science. This book is an effort to address these issues by providing a handbook of algorithmic recipes drawn from the field of Machine Learning, described in a complete, consistent, and centralized manner. These standardized descriptions were carefully designed to be accessible, usable, and understandable. An encyclopedic algorithm reference, this book is intended for research scientists, engineers, students, and interested amateurs. Each algorithm description provides a working code example in R.” He has written another book title “Clever Algorithms: Nature-Inspired Programming Recipes” in which code is in Ruby. This ruby code is actual implementation code of the algorithm. Both of his books are free for online viewing and are a goldmine for anyone looking for actual code.

Does simplifying the material to suit a mass audience actually help them to learn/get acquainted, or give them just enough knowledge to be dangerous?  Simply put... it's ML, it's complex, and it's inherently mathematical. As an introduction it was medium-high, and Prof. Domingos has done an admirable job explaining the concepts, but it still felt too breezy and tended to emphasize at times (perhaps erroneously), that knowing how to turn the knobs and when to turn them is sufficient and in some way the 'stuff' of ML anyhow so let’s not bother with the mathy bits. I can't say I entirely agree, but I am grateful for the experience and hope that the focus going forward for these kind of books is more rigour, i.e., a better balance between applying the ideas and understanding what drives them. 

But what are we really seeing here? I mean, what kind of people are interested in ML?  Developers, scientists, engineers, etc. These are the kind of people who are generally always learning. As a group, we most likely chose our careers because we enjoy learning so much. Contrast our group with just walking down the street and asking randomly selected people questions like: how many non-fiction books have you read lately? What new things have you learned in the last week? And how old are you? Would the percentages be anything like our group? Would we see any correlation between age and learning? (Now I'm curious)

But for us here, I think we are all pretty much addicted to learning, and will be for the rest of our lives, and as such, present a lot of bias that makes it harder to query for correlations like age and learning...

NB1: Disclaimer. Pedro Domingos is a fellow-countryman of mine, working at The University of Washington in the field of Computer Science & Engineering.

NB2: Unfortunately, some math skills are an absolute requirement to fully appreciate this book, in my opinion.  The good news, is that you don't need calculus to apply ML techniques like linear regression, neural networks, SVMs, etc.  Algebra, basic linear algebra, and descriptive statistics will take you a long way toward your goal.

In my opinion, here are 4 core skills necessary to learn basic machine learning techniques well enough to apply in your job:

1) Linear algebra.  There are some online courses and inexpensive books that can help.  You must understand basic matrix options like inner product, transpose, and inverse.  There was a Coursera course last July called Coding the Matrix that would help you understand how linear algebra is applied to problems. I think it's still available offline.

2) Basic probability and statistics.  There are a couple of online classes at Udacity.  You need to understand descriptive statistics (mean, standard deviation), and probability.  These skills are necessary for understanding linear regression, and almost everything yet to come in a ML class.

3) Programming skills.

4) Algorithms.  I think one of the hardest parts of this field is translating the algorithms that are expressed in mathematical form (like Professor Ng's cost functions, etc.) to code.  If you don't have a math background, then it's easy to be intimidated by this.  I've found that breaking the math down as much as possible helps.  It takes time, practice, and persistence.  I don't think there's any class that teaches this as a specific skill - it's just something you have to work on.

NB3: ML = Machine Learning; AI = Artificial Intelligence.