AlgorithmsProgrammingScheme

Scheme in 33 Miniatures

This weekend I was trying to wake my old brain up by looking and the clever and mind-bending problems from my graduate school. I have really gotten excited about Madhur Tulsi‘s Mathematical Toolkit class — as a “data scientist”/”machine learning engineer” (I sometimes wonder what these designations mean — heck I just am grateful to have been able to work on A.I. with all its challenges and contradictions for a couple of decades) I find myself treasuring the notes and exercises.

One gem that I found is the text Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra by Jiřì Matoušek. This is full of memorable tricks and insights that leverage linear algebra. While the text is mostly about proofs, I used some of the algorithms presented discussions do some Lisp programming this weekend.

I started off with the first two miniatures on Fibonacci numbers — the first presenting a fast method to get the nth Fibonacci number and the second which is probably not so fast is yet elegant in that it presents a function to compute Fibonacci numbers.

So first, I wanted to re-awaken my Lisp programming brain. Racket is definitely one of the more innovative Lisp languages to have emerged over the last 10 years. You can think of Racket as a package that provides a collection of Lisp-languages, among them standard Scheme — a paired down Lisp dialect.

The first implementation achieves O(logn) running time by using exponentiation by squaring. This is achieved by first realizing that the Fibonacci recurrence can be written in terms of a matrix polynomial \begin{pmatrix} F_(n+1)\\ F_(n)\end{pmatrix} = M^n \begin{pmatrix} 1\\ 0\end{pmatrix} where M = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}. I hadn’t known this but n is a power of 2 we can compute the M^n by repeatedly squaring M and then the case where n is odd is taken care of by a multiply. I’m guessing that the core exponentiation routine would use this (or a faster method) anyway, but still interesting to consider.

So first to see if a quick exponentiation by squaring does against the method provided in the racket math/matrix package. Here’s my quick recursive method, based on the tail recursive method in the wikipedia article

;;identity
(define one-matrix (matrix [[1 0] [0 1]]))
;;recursive exponentiation by squaring
(define (exp-by-squaring x n)
   (letrec
    (
     [exp-by-squaring-aux
       (lambda (y x n)
         (cond
          [(= n 0) y]
          [(= n 1) (matrix* y x)]
          [(= (modulo n 2) 0)
            (exp-by-squaring-aux y (matrix* x x) (/ n 2))]
          [else
            (exp-by-squaring-aux
             (matrix* y x) (matrix* x x) (/ (- n 1) 2))]))])
    (exp-by-squaring-aux one-matrix x n)))

And here is a quick running time analysis

> (time (dotimes (x 1000) (exp-by-squaring (matrix [[1 1 ] [1 0]]) 100)))
cpu time: 793 real time: 802 gc time: 175
> (time (dotimes (x 1000) (matrix-expt (matrix [[1 1 ] [1 0]]) 100)))
cpu time: 143 real time: 144 gc time: 36
>

Looks like I’m better off with the library — although curious to know what the library implementation is.

So sticking with the matrix-expt library function:

;;;-- Miniature 1: Fibonacci Numbers, Quickly
(define one-zero-matrix (matrix [[1 0]]))

(define fib-matrix (matrix [[1 1 ] [1 0]]))

(define (fast-fib n)
 ;;; Fast method of computing nth fibonnaci number
 (let* (
         [m-expt (matrix-expt fib-matrix n)]
         [idx0 0]
         [idx1 1]
         [prod (matrix* one-zero-matrix m-expt )]
        )
    (matrix-ref prod idx0 idx1 )))

Now here’s an old-school tail recursive implementation

;;; Old school fib
(define (os-fib n)
 (letrec ([os-fib-helper 
            (lambda (n a b)
             (cond
              [(= n 0) b]
              [else
                (os-fib-helper (- n 1) b (+ a b) )]))])
         (cond
           [(= n 0) 0]
           [(= n 1) 1]
           [else
             (os-fib-helper (- n 2) 1 1)])))

Now let’s look at how they compare.

> (time (dotimes (x 10000) (fast-fib 100)))
cpu time: 2554 real time: 2612 gc time: 617
> (time (dotimes (x 10000) (os-fib 100)))
cpu time: 41 real time: 41 gc time: 11

Wow. Maybe we’ll have to go to type checked racket to see any gains there!

Typed racket claims to get more of a boost in performance by using type hints. Here is the typed version of the fast Fibonacci

;;; -- Miniature 1: Fibonacci Numbers, Quickly (with type hints)
(: one-zero-matrix (Matrix Integer))
(define one-zero-matrix (matrix [[1 0]]))

(: fib-matrix (Matrix Integer))
(define fib-matrix (matrix [[1 1 ] [1 0]]))

(: fast-fib (-> Integer Integer))
(define (fast-fib n)
 ;;; Fast method of computing nth fibonnaci number
 (let* 
  (
   [m-expt (matrix-expt fib-matrix n)]
   [idx0 : Integer 0]
   [idx1 : Integer 1]
   [prod : (Matrix Any) (matrix* one-zero-matrix m-expt )]
  )
  (cast (matrix-ref prod idx0 idx1 ) Integer)))

;;Hacky runner to allow my bootleg benchmark
(: run-fast-fib-100 (-> Integer Integer))
(define (run-fast-fib-100 n)
  (dotimes (x n)
   (fast-fib 100))
 n)
> (time (run-fast-fib-100 10000))
cpu time: 689 real time: 728 gc time: 251
- : Integer
10000
> (time (run-fast-fib-100 10000))
cpu time: 672 real time: 733 gc time: 244
- : Integer
10000
> (time (run-fast-fib-100 10000))
cpu time: 704 real time: 750 gc time: 267
- : Integer
10000
> (time (dotimes (x 10000) (os-fib 100)))
cpu time: 28 real time: 28 gc time: 0
> (time (dotimes (x 10000) (os-fib 100)))
cpu time: 31 real time: 30 gc time: 0
> (time (dotimes (x 10000) (os-fib 100)))
cpu time: 35 real time: 35 gc time: 0
>

About an order of magnitude better, but still order of magnitude worse than the iterative version though. Better off sticking with the simple iteration.

Now in the second miniature, Matoušek derives a numeric expression for the nth Fibonacci number by solving a system of linear equations that follow from the recurrence. This is F_n = 1/\sqrt{5} \left[ \right( (1 + \sqrt{5})/2 \left) ^n - \right( (1 - \sqrt{5})/2 \left) ^n \right]

;;; -- Miniature 2: Fibonacci Numbers, the Formula(: root-five Real) 
(define root-five (sqrt 5.0)) 

(define inv-root-five (/ 1.0 root-five)) 

(define first-tau-root (/ (+ 1.0 root-five) 2.0)) 

(define second-tau-root (/ (- 1.0 root-five) 2.0)) 

(define (fib-root n) 
 ;;; Not so fast but fun ?
 (exact-round 
    (* inv-root-five 
     (- (expt first-tau-root n) (expt second-tau-root n))))

How does compare against an “old school” iterative version?

> (time (dotimes (x 10000) (fib-root 100)))
cpu time: 3 real time: 4 gc time: 0
> (time (dotimes (x 10000) (os-fib 100)))
cpu time: 27 real time: 28 gc time: 0

Well, that seems to best it. At least until we get further out in the sequence, where overflow gets to be an issue

> (time (dotimes (x 10000) (fib-root 1200)))
cpu time: 4 real time: 4 gc time: 0
> (time (dotimes (x 10000) (os-fib 1200)))
cpu time: 1271 real time: 1419 gc time: 293
> > (time (dotimes (x 10000) (fib-root 2000)))
. . exact-round: contract violation
 expected: rational?
 given: +inf.0
> (time (dotimes (x 10000) (os-fib 2000)))
cpu time: 2619 real time: 2893 gc time: 725

So we’ve got constant time with the analytic solution, we might loose the better performance once we get better precision. Interesting. I’ll hold it there for now and contemplate. It’s been a nice Scheme appetizer — a feel my inner Scheme brain re-awakening.

Social Justice

Reverence for the righteous

Several months ago I read Timothy Snyder’s award winning Black Earth, an important but difficult book on the horrific destruction of millions of lives in the “bloodlands” of Eastern Europe during the Second World War.

Despite the gravity of the book, there was a deep and eternal hope that I found in its stories of the ordinary and extraordinary Jews, Poles, Ukrainians — in other words people — coping with the unimaginable. The grandmother who hid and sheltered strangers, only to see them found out and killed; the farmer who kept three desperate sisters alive despite the risk of brutal death. The faith of saving your neighbor, standing with your neighbor, for years, sun up and sun down, despite the risk. Righteousness.

I read the book because I felt that I needed to keep awareness of the struggles that are now fading into history in mind — the people I knew who had faced that ghastly horror, breathed its stench and survived as testament have now left this realm. As I write this a mosque in Quebec has been attacked, Muslim brothers and sisters, children from Iran, survivors from Syria — people, human beings — are again being caught up in an echo of those dark times. I am, we are, all being called to account — again.

Snyder’s words are poignant:

In the darkest of times and places, a few people rescued Jews for what seems like no earthly reason. These tended to be people who in normal times might seem to take ethical and social norms a bit too literally, and whose fidelity to their expressed principles survived the end of the institutions that supported and defended them.

If these rescuers had anything in common beyond that, it was self-knowledge. When you know yourself, there is little to say.

The events of the last few months, of the last two days have been challenging. The thought of how to respond — whether to run, to shout, to cry, to detach, to pray — we are all gripped by a range of conflicting emotion and inclination.

I just try to hold the truth of those righteous souls in each moment and look for the self-knowledge to respond as a brother, a father, a friend, a fellow person.

BooksTravel

Books on a plane

Next week, the team I am on at Automattic is meeting up in Tel-Aviv to attend the NetSci X conference. There is so much to be excited about — the opportunity to spend 10 days with colleagues, the interesting talks on network theory and analysis, the opportunity to visit the holy sites of the Bahá’í faith and soak up the spiritual energy, the gift of spending days in some of humanity’s most ancient cities, and then the magic of the unexpected.

I am looking forward to experiencing and blogging about those adventures. I want to take time to discuss one of my favorite things to do on long plane rides — reading books that I have long had on my list and rarely get the chance to dive into.

img_1590

There is a Lonely Planet travel guide to Israel (maybe better for pre-travel reading? My colleague has hooked it up!), the memoir Seven Good Years by Etgar Keret who I’d enjoyed listening to on Fresh Air, Blood at the Root an analysis of one Georgia town’s painfully recent struggle with its history of racism, The Attention Merchants on the impacts of the behavioral advertising models that dominate the Internet, and Weapons of Math Destruction which I’d started but not finished. I have laid them out on the table tonight and thinking today about which one or two to take with me.

Usually it happens that a fellow traveler feels compelled to share something and I am all there to listen. On a journey back from Vancouver, a fellow traveller shared beautiful and haunting pictures she and her husband made of the botanical gardens around Vancouver.

I want to be open to all that can happen on this journey. But it is great to have books on the plane to share the ride.

Deep Learning

Remembering Tupac with (Neuro) Style

So I thought I would take the inaugural post on charlesearl.blog to commemorate the great dearly departed Tupac while also dipping my foot into Deep Learning Neural Style Transfer. What??

tupac-orig

Honoring you with style

Style transfer[1] is the AI that powers apps like Pikazo and Prisma — it extracts the style in from one image then re-images a second image in that style to create a third novel image.

When a deep neural network is trained to classify images, something really interesting happens. During the training process, the network is discovering features that can be used to accurately identify images — millions of images might be analyzed.  The feature-specific knowledge gets organized in a hierarchy. This knowledge is split across the layers of the network roughly according to complexity — the lower level layers tend to capture relations at the pixel level whereas the units in higher levels of the network capture the relations between abstract entities in the image.

In the neural original neural style paper [1] the authors use a pre-trained deep neural network in kind of the same way that a doctor uses an X-ray machine. That is, as an instrument that can discover structure not immediately apparent. While the doctor can get some idea of the condition of your bones by careful use of the X-ray source, the researchers use the network to extract both “style” and “abstract content” from the artwork and the photograph. In style transfer, spatial correlations between image features — explicitly defined by the Gram matrix — are used as a proxy for style. Cleverly reconstructed images corresponding to the output of each convolutional layer of the network are used as a proxy for abstract content.

Constructing the composite image then is a matter of overlaying the style (Gram matrix representation ) and content images for selected layers. Through some experimentation, the authors of the original algorithm [1] arrived a set of layers that seem to work best for style and content respectively. This is still an active area of experimentation. Prisma uses clever custom algorithms to speed the stylization process so those hip images can appear in your Facebook post in reasonable time.

After experimenting with a few implementations, I made some headway (given quirkiness with my NVIDIA 1060 graphics card and the various deep learning libraries ) with an implementation of neural style transfer by Justin Johnson at https://github.com/jcjohnson/fast-neural-style. It is further described in his paper[2].

Now on to the image making! Given that Tupac’s mother Afeni Shakur also passed away this year (her memorial in the New York Times is a stirring testament) I thought it would be appropriate to look at the art of the 1970’s Black Power movement as a source of style. The painting Revolutionary by Wadsworth Jarrell seems to capture the urgency of the lives that Afeni and Tupac lived.

revolutionary-by-wadsworth-jarrell

What an image! Both the rich structure of the image and the fact that I hadn’t come across many examples of the Black Arts movement work in style transfer seemed to make this especially gratifying project.

So here’s what I came up with.

style_transfer_revolution2

On the left are the original photos of Afeni Shakur (taken in the ’70s) and Tupac at the height of his art. On the right Revolutionary. The new images are in the center. To my naive eyes, the new image of Afeni works a bit better. Sorry Tupac. But the other thing that has me intrigued is the textures in Revolutionary. Jarrell has embedded a lot of symbolism: you can pick out “Black”, “Revolution”, “Unrest”, and “Black is Beautiful”  in the painting. Are these symbolic elements recognized at any layer in the network? There are clearly some interesting questions at the intersection of art, computer vision, and deep learning.

To end my post, I’m going to leave with an experiment based on  Romare Bearden‘s Train Whistle Blues. I think this works a little better for Tupac.

tupac_romare

Now I’m really interested in seeing how clever we can get with identifying interesting textures for the transfer.

[1] Gatys, Leon A., Alexander S. Ecker, and Matthias Bethge. A Neural Algorithm of Artistic Style(2015).

[2] Johnson, Justin, Alahi, Alexandre, and Fei-Fei, Li Perceptual Losses for Real-Time Style Transfer and Super-Resolution in The 14th European Conference on Computer Vision – Amsterdam, The Netherlands, ECCV 2016.

Scheme

Things to do in Scheme

I find that Oleg Kiselyov’s blog is a garden of delights for those of us who enjoy Lisp and Scheme. Each post seems like a timeless treasure on things to really know and appreciate about functional programming — maybe programming generally. I am still digesting his Monadic Programming in Scheme because I am still trying to grok Haskell.

As a kind of challenge for really taking his lessons to heart and mind, I wanted to assemble a list of things to write in scheme, perhaps with an eye toward thinking through modern type theory. Here is a beginning to the list

  • min-hash. A year or so ago was impressed that you can get very accurate duplicate detection with simple n-gram hash matching.
  • keras. Or rather a high-level language for composing deep neural networks. The keras functional interface still doesn’t seem quite functional to me.
  • automatic differentiation. The post Neural Networks, Types, and Functional Programming raises the interesting parallels between deep learning and functional programming. On looking further I discovered that there is more than one way to do backward differentiation. That is, there may be some useful efficiencies that both the machine learning and automatic differentiation communities might jointly discover.

So there’s a 15 minute start to the list! I’ll keep adding as I dive into things. In the meantime, there’s a lot in Kiselyov’s blog to catch up on.

BooksHistory

Granted

It seems that my last post set sparked a lot of questions in my mind about the Civil War era, it’s impact on my family, the repercussions upon Georgia, and how it is still being grappled with to this day.

There is a lot that I am still unpacking but I’ll start simple. For some reason I have been fascinated by Ulysses S. Grant since since sometime in grade school: at some point in the fifth grade I had written a play about a family of newly freed slaves encountering him on their way to a new existence in the north.

I encountered a biography, Grant by Jean Edward Smith which was fascinating in laying out many of the details of the Civil War I’d forgotten. He has a great story-telling style that seemed to make the intrigue of the early days of the Civil War jump out, and brought to life the way in which life in the 19th century seemed to straddle the complexities of a long ago time with our own.

I read a few chapters of it before returning it to the library, and then shortly a long awaited biography American Ulysses came out. Prescient. I vowed to complete this one end to end. As the politics of the 2016 US presidential election came to their head, I was reminded time and again, how far and how little progress the US has made confronting what I would simply call White supremacy. Several insights began to stand out as I continued reading the book.

  • One conclusion that one comes to is that the relative low ranking of Grant in terms of presidents seems in part due to the revisionist US history that unfolded after Reconstruction was abandoned. That is, objectively Grant stands out as an equal to LBJ and his predecessors as an aggressive advocate of civil and human rights. Yet after his time in office, the country effectively began to turn a blind eye to the racial violence and dis-enfranchisement of African Americans ( and Native Americans, and ethnic minorities ) that would envelop the South for a hundred years. I think the historians bought into this narrative.
  • The degree to which he evolved as a thinker on race and equality seems unparalleled in politics. These kinds of evolutions are certainly rare in US politics, the closest thing that I can think of in this evolution would be Robert Kennedy’s evolution from a critic of the 1960’s Civil Rights in his time as Attorney General to being an unqualified advocate at the time of his assassination.
  • Andrew Johnson’s impeachment seems to have really arisen over his refusal to enforce any of the Civil Rights measures passed in the immediate aftermath of the Civil War. This biography argues effectively that (Andrew) Johnson didn’t have any interest in African Americans having voting rights . To quote Johnson “to grant the privileges of citizenship to blacks would show prejudice against whites.” We still seem to be having the same zero sum game issues in 2016.
  • It is amazing to note his development of and unflinching support of the 14th and 15th amendments. To quote: “I will not hesitate to exhaust the powers thus vest for the purpose of securing to all citizens of the United States the peaceful enjoyment of the rights guaranteed to them by the Constitution and laws.”
  • Grant’s development of a real relationship with Mexico in dealings with Benito Juarez and Matias Romero — again remarkable for the “manifest destiny” era — again have lessons for today. I’m having a hard time conceptualizing how Grant would react to a fellow American Republican president building a wall to separate the two countries.

In sum the book was an odyssey of hope. The journey of a man who evolved from being indifferent to slavery to one of the architects of a multi-racial society is dramatic and pulled off with great story telling on White‘s part. Especially insightful and compelling are White’s narrative of the how Grant confronted the Ku Klux Klan. The gem of this story is how Grant pulled in an ex-Confederate from Georgia, Amos Akerman, who would champion civil rights as U.S. attorney general and as a lawyer in Georgia when he left the cabinet.

There is a quote, though antiquated, that White pulls out that seems to sum up what a real politics could be “Treat the negro as a citizen and a voter, as he is and must remain, and soon parties will be divided, not on the color line, but on principle. Then we shall have no complaint of sectional interference.” In essence when we are all free to express our voice, not threatened with removal or invisibility by our identity but included by our humanness, then governance can enter a civil space.

The way the book dealt with the fine details as well as the broad historical context is amazing. I appreciated his understanding of Grant as an introvert who was able to provide critical leadership to a country divided.

Finally it seems to me that it is another testament to Dr King’s quote: “The arc of the moral universe is long, but it bends towards justice.” When I first heard that quote, I’d no idea that it would take so long. I am learning patience.

 

 

 

AtlantaHistory

Bridges

Six years ago, I was trying to get a proposal off and my wife hooked me up with a few days of retreat time at a place called Banning Mills. It’s about an hour and half from Atlanta, but in many ways, rural Georgia has always seemed a world away.

Both of my grandfathers left small towns in the southeast — Covington, GA and Salem, AL — under a phenomenon I’ll just call “Klan duress”. Veiled and not-so veiled threats from powerful White men led them both to migrate to Atlanta before the 1920’s. So I acknowledge that I still have some biases to overcome.

Nevertheless, I was impressed by the beauty of the surrounding area. It claims a famous zip-line

zipline

and nearby there are exquisite views of the Chattahoochee that are priceless for their serenity

img_1145

The image that remains with me to this day is a placard that I saw on entering the resort’s  main building to check in. It is of a Black man, a very distinguished gentleman, taken in the 1850’s/60’s. I was shocked by it’s very existence — that in Carrol County there was Black who then and to this day occupies a position of honor.

img_1140-1

The gentleman was Horace King, an Oberlin-educated architect. He built many bridges throughout the southeast, in fact a bridge connecting Alabama and Georgia. Before the war broke out he had purchased his freedom using monies from his bridge building efforts with his owner John Godwin. He is responsible for this innovative fantastic staircase in the Alabama State Capital, was conscripted into building ships and defenses for the Confederacy, and was an active figure in the rebuilding of Alabama after the Civil War.

It was no small feat. According to the census data ( the visualizations developed by the Census Department during the pre-Tableau 1860’s is in itself a feat of imagination and an exemplar of good data design ), more than 40% of Georgia was enslaved at the time.

cwslave

Though the “invisibility” of the my African slave ancestors is acknowledged, the census data paints a picture of a similarly un-empowered White population getting by on subsistence farming.

The image I left Banning Mills with was of Mr King standing with the White, Black, and Native American bridge builders near a completed project. I’ve probably imagined that image — so far I’ve not been able to locate it despite generous help from Banning Mill’s owner and founder Donna King. But I believe the impact of his life captures that impression: that he created bridges in his lifetime and today that allow us to escape the received and limited narratives that constrain our ability to connect, to see, and to grow.

img_1149