Wednesday, 31 December 2014

selection with and without replacement

Selection without replacement
Often, we want to selects K items at random from a pool of N items, without replacement.  That means we select the first item at random, remove it from the pool, put it aside, then take out the second from the remaining N–1 items, and so on.  This is different from selection with replacement, where we do not remove the selected items from the pool, so we are always selecting from N items, and may select the same item more than once.

An example of selection with replacement is forming a random string by selecting from a bag containing several balls, each marked with a unique character of the relevant alphabet.  The first character in the string is that on the first ball drawn.  The ball is replaced, the bag shaken, and a second ball drawn to produce the second character, and so on.  Clearly the same ball may be drawn more than once in this process, so characters can repeat.  If instead we drew without replacement, we would instead get a string where each character appeared at most once (since each ball in the bag has a unique character), and the string length would be limited by the number of balls in the bag.

In Python, we cam implement choice with replacement readily, using the random module.
# choose K from N, with replacement
import random

K = 6
N = 16
bag = range(0,N-1)

draw = []
for i in range(0,K):
    draw += [random.choice(bag)]
    
print draw 
Running this gives results like
[6, 2, 6, 1, 5, 5]
and
[1, 0, 0, 4, 9, 9]
In fact, choosing several items without replacement is so common, the numpy module extends choice() to take an extra argument
# choose K from N, with replacement
import numpy

K = 6
N = 16
bag = range(0,N-1)

draw = numpy.random.choice(bag,K)
print draw 
Running this gives results like
array([12,  1, 11,  4, 10, 10])

How to choose without replacement?

We could keep choosing with replacement, checking that we have no duplicates, until we have enough unique choices.  But this is very inefficient, particularly when K is close to N, as finding that last unique choice is unlikely! It also doesn’t extend to the case where there are duplicate items in the bag, as it is not possible to tell whether a drawn item has been drawn before, or is merely the same as one that has been drawn before.

We could explicitly remove the item from the bag each time. In Python, we can implement choice with replacement, choosing at random as before, but now explicitly removing the item from the bag, too.
# choose K from N, without replacement
import random

K = 6
N = 16
bag = range(0,N-1)

draw = []
for i in range(0,6):
    item = random.choice(bag)
    draw += [item]
    bag.remove(item)
    
print draw, bag
Running this gives results like
[3, 13, 7, 9, 11, 2] [0, 1, 4, 5, 6, 8, 10, 12, 14]
and
[4, 3, 5, 14, 11, 9] [0, 1, 2, 6, 7, 8, 10, 12, 13]
There are no duplicates in the list, and the chosen items are removed from the bag.

Iterations usually feel non-Pythonic, unless over something necessarily temporal.  Here the iterative solution arises from the temporal nature of the description: draw a ball, then another, then another.  But is there another way: can I just draw all K items all together in a single handful? Can we remove the iteration?

To draw a handful, it seems I need to make several random choices from my neatly ordered list in the bag.  But actually, the point of a bag is that all the items are jumbled up.  This is the clue: jumble up the list, then take a handful from that jumble.

So, we can randomly permute (jumble) the items in the bag, and then take the first K elements (handful) of that permutation:
# choose K from N, without replacement
import numpy

K = 6
N = 16
bag = range(0,N-1)

draw = numpy.random.permutation(bag)[0:K].tolist()
print draw 

This gives us what we want. (The tolist() is there to convert the numpy result from an array back to a list, and is needed only if you want a list rather than an array).  Different runs give different permutations, and hence different handfuls (initial slices).  I used this technique to choose the K random input nodes to each of the N nodes in my random boolean network example (although it is hidden deep in the calculation of Con).

The bag doesn’t have to be a simple list of numbers: it can be a list of anything we want to choose from.  Let’s say we have an N×N grid, and want to choose K distinct positions, that is, K coordinates without replacement. We can create a bag of coordinates (here using a list comprehension), permute them, and slice the front off, thus:
# choose K from N, without replacement
import numpy

K = 6
N = 4
bag = [ [i,j] for i in range(0,N)  for j in range(0,N) ]
print bag

draw = numpy.random.permutation(bag)[0:K].tolist()
print draw 
Running this gives results like
[[0, 0], [0, 1], [0, 2], [0, 3], [1, 0], [1, 1], [1, 2], [1, 3], [2, 0], [2, 1], [2, 2], [2, 3], [3, 0], [3, 1], [3, 2], [3, 3]]
[[0, 3], [1, 3], [3, 2], [2, 3], [3, 3], [3, 1]]
and there are our random positions!  That feels more Pythonic to me.

Tuesday, 30 December 2014

Kindling thoughts

Jo Walton has got an e-book reader.


That means I should think about it again, since her previous review was one of the things that put me off last time I was considering it.



For all my social networking posts, see my Google+ page

bonnet frost (or, frost on the hood)

We haven't used the car for about three days, and remarkably beautiful long fronds of frost have slowly grown on it.  It seemed a pity to disturb it this morning.  But we needed to shop.


Monday, 29 December 2014

paint the sky with stars

Sunset tonight caught a con trail crossing some clouds, painting the sky with a huge asterisk.

sunset, 16:19 GMT

comprehending comprehensions

One of the features of Python I really like, and am using more and more, is its list comprehension.  This allows the items in a list to be manipulated as a whole, rather than having to explicitly iterate over them.

The basic form of a list comprehension is
[ expr for item in list ]
where expr is an expression in the variable item.

For example, let’s say I have heard that the term x3x, where x is an integer, is always divisible by 3.  Before trying to prove (or disprove!) this, I want to have a quick look at a few examples to check there isn’t a really simple counter-example.  I can write:
>>> [ x * x * x - x for x in range(-4,10) ]
[-60, -24, -6, 0, 0, 0, 6, 24, 60, 120, 210, 336, 504, 720]
Well, that looks plausible, but maybe my mental arithmetic isn’t too hot, and I need confirmation that all those numbers really are divisible by 3.

A list comprehension has an optional condition, returning only the (expression of) the items where the condition is true.
[ expr for item in list if cond ]
A few of the integers not divisible by 3 are:
>>> [ x for x in range(-4,10) if x%3 != 0 ]
[-4, -2, -1, 1, 2, 4, 5, 7, 8]
Are any of the cubic expressions not divisible by 3?
>>> [ x for x in range(-4,10) if (x * x * x - x)%3 != 0 ]
[]
Okay, so it’s probably worth having a shot at the proof then.

Of course, comprehensions aren’t limited to lists of numbers.  Let’s say I have a list of strings, and want to get a list of the lengths of the long strings (more than 5 characters long, say).
>>> animals = [ 'cat', 'dog', 'horse', 'elephant', 'meerkat', 'ox']
>>> [ len(s) for s in animals ]
[3, 3, 5, 8, 7, 2]
>>> [ s for s in animals if 5 < len(s) ]
['elephant', 'meerkat']
>>> [ len(s) for s in animals if 5 < len(s) ]
[8, 7]

List comprehensions can be applied to nested lists, too. I might have a list of lists, let’s say a list of a list of animal and of planets (why not?).
>>> planets = [ 'Mercury', 'Venus', 'Earth', 'Mars', 'Jupiter', 'Saturn', 'Uranus', 'Neptune', 'Pluto']
>>> big_list = [ animals, planets ]
>>> big_list
[['cat', 'dog', 'horse', 'elephant', 'ox'], ['Mercury', 'Venus', 'Earth', 'Mars', 'Jupiter', 'Saturn', 'Uranus', 'Neptune', 'Pluto']]
(I’m sorry, but as far as I’m concerned, Pluto is indeed a planet.)

I can get a list of the lengths of all the long strings:
>>>[ s for lst in big_list for s in lst ]
['cat', 'dog', 'horse', 'elephant', 'meerkat', 'ox', 'Mercury', 'Venus', 'Earth', 'Mars', 'Jupiter', 'Saturn', 'Uranus', 'Neptune', 'Pluto']
>>>[ len(s) for lst in big_list for s in lst ]
[3, 3, 5, 8, 7, 2, 7, 5, 5, 4, 7, 6, 6, 7, 5]
>>>[ len(s) for lst in big_list for s in lst if 5 < len(s) ]
[8, 7, 7, 7, 6, 6, 7]
This way, I can process the nested lists as one big flattened list.

But what if I didn’t want to flatten the list?  Well, since list comprehensions are themselves expressions, they can form the expression in a list comprehension!  Used this way, they maintain the structure of the original nesting.  So
>>>[ [s for s in lst] for lst in big_list ]
[['cat', 'dog', 'horse', 'elephant', 'meerkat', 'ox'], ['Mercury', 'Venus', 'Earth', 'Mars', 'Jupiter', 'Saturn', 'Uranus', 'Neptune', 'Pluto']]
>>>[ [len(s) for s in lst] for lst in big_list ]
[[3, 3, 5, 8, 7, 2], [7, 5, 5, 4, 7, 6, 6, 7, 5]]
>>>[ [len(s) for s in lst if 5 < len(s)] for lst in big_list ]
[[8, 7], [7, 7, 6, 6, 7]]
This approach becomes even more powerful when the list items are objects, and we need to operate on object attribute values.  Let’s assume that the list items above are not strings, but objects with a name attribute that is the relevant string.
>>>[ [s.name for s in lst if 5 < len(s.name)] for lst in big_list ] 
[['elephant', 'meerkat'], ['Mercury', 'Jupiter', 'Saturn', 'Uranus', 'Neptune']]
When using a list comprehension as an expression inside another comprehension in this way, we don’t need to have it as the top level expression.  Let’s assume that we want a list of numpy arrays of the lengths (maybe because we want to do numpy operations on the resulting lists, such as averaging the results).
>>> from numpy import *
>>>[ array([len(s.name) for s in lst if 5 < len(s.name)]) for lst in big_list ]
[array([8, 7]), array([7, 7, 6, 6, 7])]

List comprehensions are powerful, removing the need for explicit for loops that iterate over the list items.  This results in more compact, and efficient, code, and encourages thinking of lists as a whole.  Take care that the compact code remains comprehensible, however, especially with nested comprehensions.

And there are dictionary comprehensions, too.

Wednesday, 24 December 2014

film review: The Imitation Game

Alan Turing did seminal work in several fields – on the fundamental theory of computing, Artificial Intelligence (the Imitation Game of the title), biological morphogenesis – and contributed to several others – neural networks, the Reimann zeta function, the quantum Zeno effect, and more. One area I’m not aware of him having contributed to (although I may well be wrong!) is the Many Worlds interpretation of Quantum Mechanics. Which is a pity, as this movie is clearly set in an alternate reality.

In this alternate (or merely fictional) universe, Alan Turing [Benedict Cumberbatch] is a semi-autistic anti-social loner, who single-handedly, against the opposition of his co-workers, builds a giant computer that breaks the German Enigma code, so winning WWII, and then goes mad in Manchester, building another computer in his front room to recreate his schoolboy crush, Christopher.

Don’t get me wrong: this alternate universe story is well told, and is the basis of my “worth watching” rating. I very much enjoyed it, with its interleaved flashbacks between his schooldays, the WWII code-breaking, the Manchester incident, the complex relationships between the characters, and the celebration of intellectual prowess and of difference generally. But I enjoyed it only as an alternate world story. Don’t rely on anything here as historically accurate (the movie’s disclaimer basically says as much); there was a person called Alan Turing, he was gay, and he was involved in breaking the Enigma code during WWII, but that’s probably it. (Oh, and Euler is pronounced Oi-ler, not You-ler.) If you want a better shot at the reality, read the book this film is “based” on: Hodges’ The Enigma of Intelligence


For all my film reviews, see my main website.

film review: The LEGO Movie

Everything is Awesome


Emmett is a completely contented minifig, working on a massive construction project with his buddies, singing the company song, having a great life. But this all changes when he sees a strange woman searching the construction site. He follows her, falls down a hole, and gets attached to the Piece of Resistance. It seems he is the prophesied Special One, destined to save the world from the evil Lord Business. Mayhem ensues.

This is great fun, much more than just a movie-length toy advert (although it is that, too). It is full of verbal and visual wit, with clever little references all over the place, and even better if you know your Lego. It inevitably gets a bit saccharine at the end, with the “message” of not being inflexible. But since that message is rather confused (it is the Master Builders who can build “off piste” who are supposedly the heroes, yet Emmett and crew win the day by following the instructions to build a particular device the same as all the others), it can be safely ignored.

It has been noted that there are rather few female characters (there’s the co-protagonist Wyldstyle/Lucy, Wonder Woman, a female construction worker, and some background characters), reflecting LEGO’s disappointing number of female minifigs overall, and it fails the Bechdel test. Wyldstyle is actually a reasonably strong figure, and it could be argued that it is she who “gets the guy” rather than the other way round. What I actually found most teeth-grinding was the ending, where the boy is “threatened” with having to play with his little sister, clearly a dreadful fate.

Despite these grumbles, overall this is a fun piece and wonderfully visualised of mind-candy, and I laughed out loud many times at the various visual jokes.

Good luck getting that song out of your head, though.

Everything is Awesome, Everything is cool when you’re part of a team


For all my film reviews, see my main website.




Tuesday, 23 December 2014

Joseph, Warrior of the 37th Century

Scalzi had me at the “demon worshippers vs Future Ninjas subplot”…


What if the angel is secretly a fallen angel, and the shepherds aren’t really shepherds at all, but a secret order of demon worshippers disguised as shepherds, who have been waiting for centuries, at the ready, to kidnap the savior foretold by prophecy at the moment of his birth, and the fallen angel is telling them so they can put their dark plan into action? Now, that makes sense!

That’s a nativity film I’d watch!



For all my social networking posts, see my Google+ page

merely resting

This is a dead parrot ... not.

The [Scottish SPCA] was called to the scene on Great Western Road in Aberdeen after what a driver believed to be a parrot was seen in the middle of the road.
However, when they got there they discovered it was a woolly hat.

duck ... rabbit ... parrot ... hat

Better to check, and be mistaken, than not to check at all.


For all my social networking posts, see my Google+ page

a picture window to dream of

WANT



Any of the murals, that is, not necessarily the furniture!






For all my social networking posts, see my Google+ page

Monday, 22 December 2014

pet food by post

I was trawling through the latest recommendations Amazon have for me, when I came across




The perils of low sample sizes, I thought: someone bought Grimm 3 and dog food in one order, so now Amazon thinks I want dog food.

A little later I saw




Oh, I thought, they bought bird food, too.

But wait!  This wasn't the Grimm-loving dog-owner, this was instead a Feist-loving bird watcher.

I’ve had some strange recommendations before, but this was just weird.

Sunday, 21 December 2014

solstice sunset

It’s just another solstice Sunday.

sunset, 16:03 GMT

sequestering carbon, several books at a time XXXVII

The latest batch:


Several other brown cardboard boxes have been arriving in the post, and shuffled off to various secret hiding places.  I expect them to reappear later in the week...

Tuesday, 16 December 2014

deleting birthdays

I just saw a birthday notification in my Google Calendar, about someone in my Google+ circles.  Getting rid of these annoying unasked-for entries requires a few clicks, as detailed below.


Thank you, Awesomely Techie!



For all my social networking posts, see my Google+ page

Monday, 15 December 2014

Strandbeest

I’ve seen pictures of Strandbeest before, but I didn’t realise they were huge, or that there are so many designs.




For all my social networking posts, see my Google+ page

Sunday, 14 December 2014

cycling to freedom

Here is a nice YouTube description of the “100 prisoners problem”, that seems on the face of it impossible, but where a clever mathematical result makes it feasible.


 



For all my social networking posts, see my Google+ page

Wednesday, 10 December 2014

language evolution

Queen photobombs selfie.

Three words that capture the moment – two of which didn’t even exist a few years ago!

Glasgow 2014: Queen ‘photo-bombs’ hockey players’ selfie

Also, I just used the words “queen” and “(photo)bomb” in an online search to find the article…


For all my social networking posts, see my Google+ page

Sunday, 7 December 2014

flickering aurorae

When I was younger, I thought aurorae were static, only having seen pictures in books. Then I discovered they moved. But these REAL TIME shots are awesome. Watch full screen!

 


(via Phil Plait, Bad Astronomy)

For all my social networking posts, see my Google+ page