AIAlgorithmsMachine Learning

Gödel, Incompletness, and AI

Kurt Gödel was one of the great logicians of the 20th century. Although he passed away in 1978, his work is now impacting what we can know about today’s latest A.I. algorithms.

Gödel’s most significant contribution was probably his two Incompleteness Theorems. In essence they state that the standard machinery of mathematical reasoning are incapable of proving all of the true mathematical statements that could be formulated. A mathematician would say that that the consistency (or ability to determine which of any two contradictory statements is true) of standard set theory (a collection of axioms know as Zermelo–Fraenkel set theory) is independent of ZFC. That is, there some true things which you just can’t prove with math.

In a sense, this is like the recent U.S. Supreme Court decision on political gerrymandering. The court ruled “that partisan gerrymandering claims present political questions beyond the reach of the federal courts”. Yeah, the court stuck their heads in the sand, but ZFC just has no way to tell truth from falsity in certain cases. Gödel gives mathematical formal systems a pass.

It now looks like Gödel has rendered his ruling on machine learning.

A lot of the deep learning algorithms that enable Google translate and self driving cars work amazingly well, but there’s not a lot of theory that explains why they work so well — a lot of the advances over the past ten years amount to neural network hacking. Computer scientists are actively looking at ways of figuring out what machines can learn, and whether there are efficient algorithms for doing so. There was a recent ICML workshop devoted to the theory of deep learning and the Simons Institute is running an institute on the theoretical foundations of deep learning this summer.

However, in a recent paper entitled Learnability can be undecidable Shai Ben-David, Amir Yehudayoff, Shay Moran and colleagues showed that there is at least one generalized learning formulation which is undecidable. That is, although the particular algorithm might learn to predict effectively, you can’t prove that it will.

They looked at a particular kind of learning that in which the algorithm tries to learn a function that maximizes the expected value of some metric. The authors chose as a motivating example the task picking the ads to run on a website, given that the audience can be segmented into a finite set
of user types. Using what amounts to server logs, the learning function has to output a scoring function that says which ad to show given some information on the user. The scoring function learned has to maximize the number of ad views by looking at the results of previous views. This kind of problem obviously comes up a lot in the real world — so much so that there is a whole class of algorithms Expectation Maximization that have been developed around this framework.

One of the successes of theoretical machine learning is realizing that you can speak about a learning function in terms of a single number called the VC dimension which is roughly equivalent to the number of classes the items that you wish to classify can be broken into. They also cleverly use the fact that machine learning is equivalent to compression.

Think of it this way. If you magically could store all of the possible entries in the server log, you could just look up what previous users had done and base your decision (which ad to show) based on what the previous user had done. But chances are that since many of the users who are cyclists liked bicycle ads, you don’t need to store all of the responses for users who are cyclist to guess accurately which ad to show someone who is a cyclist. Compression amounts to successively reducing information you store (training data or features) as long as your algorithm performs acceptably.

The authors defined a compression scheme (the equivalent of a learning function) and were then able to link the compression scheme to incompleteness. They were able to show that the scheme works if and only if a particular kind of undecidable hypothesis called the continuum hypothesis is true. Since Gödel proved (well, actually developed the machinery to prove) that we can’t decide whether the continuum hypothesis is true or false, we can’t really say whether things can be learned using this method. That is, we may be able to learn an ad placer in practice, but we can’t use this particular machinery to prove that it will always find the best answer. Machine learning and A.I. are by definition intractable problems, where we mostly rely on simple algorithms to give results that are good enough — but having certainty is always good.

Although the authors caution that it is a restricted case and other formulations might lead to better results, there are some two other significant consequences I can see. First, the compression scheme they develop is precisely the same structure that are used in Generative Adversarial Networks (GANs). The GAN neural network is commonly used to generate fake faces and used in photo apps like Pikazo http://www.pikazoapp.com/. The implication of this research is that we don’t have a good way to prove that a GAN will eventually learn something useful. The second implication is that there may be no provable way from guaranteeing that popular algorithms like Expectation Maximization will avoid optimization traps. The work continues

It may be no coincidence that the Gödel Institute is in the same complex of buildings as the Vienna University AI institute.

Next door to the Gödel Institute is the Vienna AI institute

Avi Wigderson has a nice talk about the connection between Gödel’s theorems and computation. If we can’t event prove that a program will be bug free, then we shouldn’t be too surprised that we can’t prove that a program learns the right thing.

A nice talk by Avi Wigderson. Sometimes hacking is all you got.
BooksData ScienceHistorically Black Colleges

Black data science book giveaway

The Atlanta University Center Consortium — the umbrella organization of Morehouse, Spelman, Clark Atlanta University, and Morehouse School of Medicine — just launched a Data Science Initiative. To celebrate, I am giving away two books!

Here’s an excerpt from the announcement:

The AUCC Data Science Initiative brings together the collective talents and innovation of computer science professors from Morehouse College and other AUCC campuses into an academic program that will be the first of its kind for our students,” said David A. Thomas, president of Morehouse College. “Our campuses will soon produce hundreds of students annually who will be well-equipped to compete internationally for lucrative jobs in data science. This effort, thanks to UnitedHealth Group’s generous donation, is an example of the excellence that results when we come together as a community to address national issues such as the disparity among minorities working in STEM.

Announcement of the Atlanta University Center data science initiative at http://d4bl.org/conference.html

To commemorate and honor the founding of this initiative, I’ve set up two book giveaways at Amazon. The first book is W. E. B. Du Bois’s Data Portraits: Visualizing Black America. W.E.B. DuBois was a sociologist who taught at the Atlanta University Center. His visualizations of African American life in the early 20th century still set the standard for data visualization and this book is a collection of visualizations that he and his Atlanta University students produced for the 1900 Paris Exposition. If Atlanta University students were doing amazing data science 100 years ago without laptops, we can only guess what the future holds. Click this link to get your book.

The second book is Captivating Technology: Race, Carceral Technoscience, and Liberatory Imagination in Everyday Life by Dr. Ruha Benjamin, a contemporary African American scholar at Princeton whose work addresses “the social dimensions of science, technology, and medicine”. Click this link to get a copy of Captivating Technology.

There is only one copy per book available so the first person to click gets the book.

If you want to know more about the work being done by Black data scientists, you should check out the DATA FOR BLACK LIVES III conference.

I’ll close with one of the sessions from the first Data for Black Lives conference. Where are the Black (data) scientists? Definitely at the Atlanta University Center!

History

This Fourth of July is yours, not mine

I quote from Frederick Douglass‘s speech of July 5, 1852. In that day, freed Africans in America feared being out on July 4 as lynchings usually spiked then. Those Black folk that cared to celebrated on the 5th.

The featured image is of a map of the indigenous peoples of the U.S. made by Aaron Carapella over at Tribal Nations Maps. I’ll gladly send you a $25 map if you submit a comment on this post or make a contribution to Aaron’s Go Fund Me. Offer is to the first poster 🙂

The original keepers of this land are still fighting to protect their identity, land, and existence. In the last few years, we have witnessed the removal of the basic voting protections accorded by the Civil Rights Act of 1964. It has been argued that this move has resulted in voter suppression and other actions to disenfranchise (again) African Americans and other marginalized groups. Most recently with the Supreme Court ruling that gerrymandering, even when it plainly dilutes the vote of marginalized communities, is ok and is in fact beyond the purview of the court. We are now witnessing a human rights crisis at the U.S. southern border in which internment camps for asylum seekers subject indigenous and LatinX men, women, and children to unlivable conditions — 24 persons having died in these facilities since the current administration took office.

All of these abuses and more call into question the vision of the U.S. that we are celebrating. There has always it feels been a tension between two visions. One is that of a republic that welcomes all and enables all to live the life they wish to their potential — in that vision, the language, religion, color, gender identity, physical ability of an individual are all strengths and part of the fabric that enables a unique society to flourish. The other vision is that of melting pot, a country for and by white Christian men. These are extreme caricatures, but you need only contrast Martin Luther King’s “I Have a Dream” vision with tweets of the current administration.

It is hard to make sense of these polarities, but thinking it through, wrestling with this through reading, discussion, reflection, is essential to the existence of the country. As a start, I would challenge readers to take on the book Stamped from the Beginning by Ibram Kendi.

I sometimes wonder what staying in the British orbit would have meant for the people of color now living in the U.S. Would it just have meant another Canada? Canada, aside from being cold, isn’t so bad a place — a functional democracy. Britain ended slavery in 1833 with the Slavery Abolition Act. The U.K. has for several decades provided subsidized health care and education for all its citizens. On the other (bloody) hand, both Canada and Great Britain continue to grapple with the genocides of indigenous peoples. India, Ghana, Kenya, South Africa — the list of nations still dealing with the scars and trauma of racialized British imperialism spans the globe. Africa is still shedding the anti-LGBTQ legacy of British rule.

I think it’s a better mental effort to think through what living in government and societies created in concert with the protectors could have looked like, and what it could still be. Here’s a zoom in on the area of what would have been the United States as of 1783 (the year the U.S. actually came into existence).

AIAlgorithmsAtlanta

The city of Atlanta doesn’t use facial recognition — so why does Delta Airlines?

I recently made an inquiry with the City of Atlanta’s Mayor’s office as to the use of facial recognition software. I received the following reply on the Mayor’s behalf from the Atlanta Police Department

The Atlanta Police Department does not currently use nor the capability to perform facial recognition. As we do not have the capability nor sought the use of, we not have specific legislation design for or around facial recognition technology.

Delta Airlines, a company based in Atlanta, continues to promote the use of facial recognition software, and according to this wired article makes it difficult for citizens to opt out of its use.

There are several concerns with use of facial recognition technology, succinctly laid out by the Electronic Frontier Foundation:

Face recognition is a method of identifying or verifying the identity of an individual using their face. Face recognition systems can be used to identify people in photos, video, or in real-time. Law enforcement may also use mobile devices to identify people during police stops. 

But face recognition data can be prone to error, which can implicate people for crimes they haven’t committed. Facial recognition software is particularly bad at recognizing African Americans and other ethnic minorities, women, and young people, often misidentifying or failing to identify them, disparately impacting certain groups.

Additionally, face recognition has been used to target people engaging in protected speech

Electronic Frontier Foundation at https://www.eff.org/pages/face-recognition

So in other words, the technology has the potential for free assembly and privacy abuses and because the algorithms used are typically less accurate for people of color (POC), the potential abuses are multiplied.

There are on going dialogs (here is the U.S. House discussion on the impact on Civil Liberties) on when/how/if to deploy this technology.

Do me a favor? If you happen to fly Delta, or are a member of their frequent flyer programs, could you kindly ask for non-facial recognition check in? Then asking for more transparency on the use and audit of the software used would be an important step forward.

FamilyHistory

Questions I never asked my father about London

The last week of May through the first week of June is an emotional Everest for our family. My wife lost her father, our beloved Nanu, six years ago June 5. My father passed away on the 31st of May thirty four years ago. June 5 is also my brother’s birthday, May 26th is my youngest son’s, and May 29th is mine. The day my father died feels like one continuous day encompassing my college graduation, my birthday and his passing.

We try to keep our fathers in memory my wife and I. It is difficult, but to lose those essential connections is unthinkable.

My father would sometimes recount to my siblings and I — in bits and pieces and partial stories — his memories of the second world war. Any given thing could bring out Daddy’s stories — a question we would ask, a documentary, a book one of us was reading, music on the radio, a rainy day at home.

The media obsession with the “D-Day” event and the particular narrative promoted, which persists in being white Anglo middle/upper class, brings his stories back to mind. The photo in this post is from a page from one of his journals, sometime in 1942/43.

My father was 18 when the event now known as “D-Day” occurred. He was a sailor aboard LST-400, a ship that transported soldiers and tanks and other material to some Normandy beach on the morning of June 6, 1944.

He was a Black man-child from Atlanta, one of nine children. He had enlisted in the Navy as a 15 year old. I always liked to think that it was partially just as a way out of the extreme racism and poverty that he found himself situated in. The Great Depression had barely subsided — or at least that is the history book mythology that I have accepted — I really doubt that he or my uncles and aunts experienced any dramatic improvement in their standard of living in the 1930s an 40s. Their father, also a veteran, had died in 1938 from the deep psychic wounds of the First World War.

My mother recounts that my father and a friend had hopped a freight train to Detroit and enlisted there. The Navy had sent my grandmother papers to verify that Daddy was a few years older than he really was (15). It seems that the U.S. had no problem taking child soldiers. I remember him talking about having to jump 100 feet into a tank of water. How was the basic training, what obstacles did he face? Who were his friends? How were Black sailors treated? Was it any better or worse than every day life in 1940s Atlanta?

What did he think as the ship sailed from Virginia across the Atlantic? He would talk about a battle off of the North African coast. How they had to pull badly burned sailors off of a sinking ship. I think that this was a landing in Tunisia called Operation Torch.

I know now from the ship muster rolls that there were Filipino sailors on LST-400 as well. What were there names? How did they spend the hours from one engagement to the next. How did they keep their mind away from the madness. Were they equally as young, conflicted in having to fight for one imperial power against another? Did they will themselves to see hope? Did they come with a dream of U.S. citizenship for their service, or was it simply enough for them to envision a Philippines free of Japanese or U.S. control?

He loved Billie Holiday. Did they allow him to play Billie and Duke aboard the ship? In his journal was an entry listing London clubs to visit — a place called the West Indian Club in London caught my eye. Was jazz played there? Did he spend evenings listening to local musicians playing a melange of jazz and Caribbean rhythms? What was Black London like in 1943?

He would talk about a landing, an invasion I suppose, that they made in Sicily. I looked at the ships logs from that operation recently. It was a small town named Gela, Sicily. According to the logs, other ships in their group had been badly damaged. They were strafed by Luftwaffe Messerschmitt aircraft and by the Italian air force. Their home port was Bizerte, Tunisia. Many of the Tunisians would I meet since his passing had the same toffee brown skin. Did he ever consider just slipping into the crowds headed to Tunis?

After the invasion, did they go ashore to Gela? Who did he meet in Italy, what did they say? He mentioned being involved in providing food and other basics to the people of that town. Were there conversations, encounters that made an impression, made him think differently, informed the compassionate person I knew?

He would tell us about how thick the sky was on June 6, 1944 with aircraft. About soldiers falling in the surf. I remember his stories of attending to starved German soldiers, most younger than him. Were those among his thoughts when he would look off into the distance at something I could not see?

He passed away 34 years ago. I lament that the images that we see as D-Day is “celebrated” (it is a strange word for a period in which 27,000 people were being murdered each day) do not capture what he experienced. Celebration is a strange word for a tragedy that was enabled and abetted by the inability of all countries involved to confront injustice head on. Like the Billie Holiday song, it was bitter fruit.

There are so many questions that remain with me:

What was it like to be a Black teenager thrust into adulthood on a ship, thousands of miles from home?

What did you do after those days after the landing? What did you fear, what did you hope for?

What were the things that gave you hope? What were the soul wounds that you had still to heal from?

My wife, children and I were in Paris during the “Victory in Europe” anniversary this year. I believe that is the day that when most of the savagery came to an end — but how does one ever leave the images and pain. I remember hearing bells ringing. I wonder if it occurred to him to stay, to just find a quiet, humble town in France to just be free.

What difficulties did you face getting the benefits to which you were entitled? The book “When Affirmative Action was White” details the discrimination that Black veterans faced in getting the home and business loans, healthcare, and other benefits provided to white sailors. Was the G.I. Bill just one of the many half-truths you faced? Who heard your frustrations, how did you reconcile them?

You never had a peaceful sleep all the days that I had with you. What were the visions that would not leave? Did anyone delve deeply into them and unlock and free you from the demons of having seen what you did? How does it feel to be free now?

So much of why I try to remember, to keep the questions in mind is simply that he not be erased.

I have over the last thirty years spoken to people who survived this period in forced labor camps, who were child soldiers in the German army, people whose parents lived in India, China, Russia. For many “war” was not a place you went, but a condition that knocked upon the door daily. None of their stories of this time seem to fit into the neat script. They all testify to loss and living with both hope, brokenness, kindness and acknowledgement that some wounds do not heal.

I just hope that the stories live and guide us so that the pain will not be repeated.

inclusionPoliticsSocial JusticeTravel

Cuba as a prayer to inclusion

As the current administration of the U.S. continues to place restrictions on travel to Cuba, my heart aches, and my mind goes to back to amazing days that we spent in Havana and Trinidad last summer.

A year later, impressions remain with me. Walking the streets of Habana and Trinidad, one is left optimistic on what inclusion could be. As we traveled across half the island, and from one end of Habana to the other, I was struct by the absence of the “Black ghettos” — the all too familiar racial segregation that is imprinted on each and every U.S. city that I have ever visited.

I was struct by the fact that the resources, though humble, were shared by all across gender and color. People of different hues and ages did Tai Chi in the park. Occasional people on the street made sarcastic comments on the Castros or Trump, the bureaucratic inefficiencies, the resources constrained by the embargo.

But the generosities were unparalleled. The warmth is still in my heart.

Along the roads, I was struct by the absence of police. Or rather it was the absence of omnipresent force — of the signals that lethal violence is around the corner, trained on Black bodies. The occasional officer, there to mitigate traffic issues, no military grade automatic weapons, that’s what I needed for a vacation.

Seeing people with access to a basic burial, children able to attend a dance class without their parents having to defer due to money, people with access to a simple loaf of bread regardless of the meager cash on hand.

We saw families coming together to say their goodbyes.

I cannot unsee inclusion, I cannot unsee the basic respect for basic human dignity. I cannot unsee humanity in practice.

I hope that you visit soon.