Skip to content

Lotfi Zadeh 1921–2017

October 21, 2017

But fuzzy logic lives on forever

New York Times obituary source

Lotfi Zadeh had a long and amazing life in academics and the real world. He passed away last month, aged 96.

Today Ken and I try to convey the engineering roots of his work. Then we relate some personal stories.

Zadeh was a Fellow of the ACM, the IEEE, the AAAI, and the AAAS and a member of the NAE. But besides this alphabet soup of US-based academies, we are impressed with the one he co-founded: the Eurasian Academy. His founding partners were a historian, a neurosurgeon, a music composer, and a mathematician. They recently elected three other members: an actress-screenwriter-director, an actor-director-writer, and a physicist.

In any alphabet of his life, one letter stands out: the letter Z. The term “Fuzzy Set” has two of them. But Zadeh’s first widely noted work goes by just the bare letter.

Z Is For…

Pierre-Simon Laplace discovered a relative of the Fourier transform that has similarly motivated applications and often better behavior. When applied to the density function {f(x)} of a random variable {X} on {\mathbb{R}} or {\mathbb{R}^+}, it has the form

\displaystyle  \mathcal{L}\{f\}(s) = E[e^{-sX}] = \int f(x)e^{-sx} dx.

Here {s} can be a complex number. The function {\mathcal{L}\{f\}} is holomorphic provided we are working on {\mathbb{R}^{\geq 0}}. A neat trick is that we can jump from {f} to the cumulative distribution {F} by

\displaystyle  F(x) = \mathcal{L}^{-1}\left\{\frac{1}{s} \mathcal{L}\{f\}(s)\right\}(x).

Can we get such nice properties for a discrete random variable {X = x[n]} on the integers? Zadeh’s advisor at Columbia, John Ragazzini, led him in showing the power of defining

\displaystyle  \mathcal{Z}\{x\}(s) = \sum_n x[n] s^{-n},

where again {s} can be any complex number, and the domain of {x[n]} and the sum can be {\mathbb{Z}} or {\mathbb{Z}^{\geq 0}}. We note that {\mathcal{L}} is often defined as a function of {t = -s}, that a similar sign issue was discussed in reviewing the 1952 Ragazzini-Zadeh paper, and we’ve switched {z} versus {1/s} in Wikipedia’s article on {\mathcal{Z}} to make it look more like {\mathcal{L}}. With a positive exponent, {E[z^X] = \sum_{n=0}^{\infty} x[n] z^x} is the probability generating function of {X}.

How useful is this? Much of what we can say in a short space is the same as with Fourier: If we form the convolution

\displaystyle  w[n] = (x * y)[n] = \sum_{\ell = -\infty}^{\infty} x[\ell]y[n-\ell],

then its {Z}-transform is just the product function:

\displaystyle  \begin{array}{rcl}  \mathcal{Z}\{w\}(s) &=& \sum_{n = -\infty}^{\infty}\left[\sum_{\ell = -\infty}^{\infty} x[\ell]y[n-\ell]\right]s^{-n}\\ &=& \sum_{\ell = -\infty}^{\infty} x[\ell]\left[\sum_{n = -\infty}^{\infty} y[n-\ell] s^{-n}\right]\\ &=& \left[\sum_{\ell = -\infty}^{\infty} x[\ell]s^{-\ell}\right]\cdot\left[\sum_{n' = -\infty}^{\infty} y[n']s^{-n'}\right]\\ &=&\mathcal{Z}\{x\}(s)\cdot\mathcal{Z}\{y\}(s). \end{array}

Using products this way makes convolutions easier to work with. Many hard-to-handle functions become nicer under their {Z}-transforms. The Dirac delta function {\delta(x) = 1} if {x = 0} and {\delta(x) = 0} otherwise is strange at face value—though it can be understood as the random variable whose outcome is always {0}. Under the {Z}-transform, however,

\displaystyle  \mathcal{Z}\{\delta\}(s) = \sum_n \delta(n) s^{-n} = s^0 = 1.

Nothing can be nicer than the constant {1}. For explanation of where {Z} is more general than the discrete Fourier transform and relatives we defer to this beautiful page. All this grew out of ideas in the 1940s by others including Witold Hurewicz—another z—but Zadeh’s joint paper had the greatest influence in signal processing.

Z to Fuzzy

The art of {\mathcal{Z}} is continuous functions forming a well-behaved nimbus around certain discrete entities. Suppose we try to do this for every discrete concept? Begin with the idea of a set {A}, namely a subset of some universe {U}. Instead, let us think of a fuzzy set {\mathcal{A} = (U,\alpha)} where

\displaystyle  \alpha: U \rightarrow [0,1].

Here the real number {\alpha(u)} is called the grade of memebership of {u} in {\mathcal{A}}. The original set {A} is the case {\alpha_A(u) = 1} if {u \in A} and {\alpha_A(u) = 0} otherwise. The point is that we are now free to consider other functions {\alpha} that approximate {\alpha_A} and are smoother and nicer to work with. We can consider whole ensembles of such functions.

From fuzzy sets it is a short step to fuzzy logic. This has an antecedent: the infinite-valued logic of Jan Łukasiewicz and others. A statement may have a truth value between 0 and 1. A common choice is to represent the value by a logistic curve of a main parameter. Here is a somewhat distorted curve for the statement “X is wealthy” parameterized by the net worth of X:

“Simulating Complexity” blog source

The point for us is that logistic curves are natural to work with when modeling such predicates in a larger system. Here is a pertinent recent example for image processing. Further points are that a logical 0-1 assignment to “wealthy” would have an artificially sharp distinction somewhere and that the logistic curves are more faithful to neural-net models of how we think.


Zadeh’s original 1965 paper is one of the most cited science papers of all time. It has close to {200,000} citations. He confessed that:

“I knew that just by choosing the label ‘fuzzy’ I was going to find myself in the midst of a controversy… If it weren’t called fuzzy logic, there probably wouldn’t be articles on it on the front page of the New York Times. So let us say it has a certain publicity value. Of course, many people don’t like that publicity value, and when they see it in the New York Times, it doesn’t sit well with them.”

That controversy was real—see the next section. Zadeh in an acceptance speech for the 1989 Honda Foundation prize said

“The concept of a fuzzy set has had an upsetting effect on the established order.”

I (Dick) never understood why this generalization of sets created such push-back. Stuart Russell, a Berkeley professor who worked next door to Mr. Zadeh for many years, noted:

He always took criticism as a compliment. It meant that people were considering what he had to say.

The impact of his work has been recognized by a posthumous “Golden Goose” Award. The award’s name counters the stigma of the “Golden Fleece” awards given out in 1975–1988 by US Senator William Proxmire in half-jest to federally-funded research projects he deemed frivolous and wasteful. Zadeh drew attention from Proxmire as a potential “Golden Fleece” awardee. The Golden Goose citation, however, describes the “Clear Impact,” especially as seen by engineering-minded Japanese:

Part of this interest came from the fact that ‘fuzzy’ was not a pejorative term in Japanese, but instead a neutral or even positive one. Researchers there took his idea and ran, creating conferences and journals focused on making advances in fuzzy logic. To this day, the only country with more patents on fuzzy ideas and concepts than the United States is Japan.

In 1986, the first commercial application of fuzzy logic hit the shelves in Japan: a fuzzy shower head. Using fuzzy concepts of hot, cold, high pressure, low pressure, and others, the shower head could use fuzzy logic to control showers across the country. Within a few years, the market was overflowing with fuzzy consumer products. Vacuum cleaners, rice cookers, air conditioning systems, microwaves, everything was moving to fuzzy control. Even the entire subway system of Sendai in Japan was built with fuzzy logic controlling the motion of the trains.

Kahan’s Story

Way back in the first month of this blog, I (Dick) quoted the following remarks by William Kahan. I was in the audience for Zadeh’s lecture too but let’s let Kahan speak:

My two favorite stories about him concern his tremendous candor. The first is about his ideas on “fuzzy sets” and the second is on “who should get tenure.” I will only tell the first one—to protect the innocent and the guilty. When I first arrived at the Computer Science Department at Berkeley, the faculty decided to have a new series of lectures that fall. The plan was to have short lectures by each faculty of the department—in this way new graduate students would learn each faculty’s research area.

One day Professor Zadeh was presenting his area of research—an area that he created called “fuzzy sets.” Fuzzy sets were then and still are today a controversial area. Some researchers do not think much of this area. However, the area is immensely popular to many others. There are countless conferences, books, and journals devoted completely to this area. Kahan was in the audience while Zadeh was speaking. Finally, at some point Kahan could take it no more. He stood up and Zadeh asked him what his question was. Kahan stated in the most eloquent manner that it might be okay to work on fuzzy sets in the privacy of your own basement (after all this was Berkeley), but there was no excuse for exposing young minds to this “stuff”—his term was stronger. We all were shocked. For a few seconds no one spoke. I wondered how in the world Zadeh could respond. Zadeh finally said, “thank you for your comments,” and went on with the rest of talk, as if nothing had happened. The next year the faculty talks were cancelled.

Ken’s Story

I met Zadeh once, when he was the featured speaker at the 6th International Conference on Computing and Information (ICCI 1994), which was held at Trent University in Peterborough, Ontario, May 26–28, 1994. Jie Wang and I drove there from STOC which was held in Montreal that year. This small conference—not to be confused with ones having similar names and acronyms—lasted just a few more years. It is hard to find any information on the 1994 meeting now—just a few paper citations—and I have found no proof on the Internet that Zadeh was there. But he was—in a non-fuzzy but decidedly freezy setting.

There was a welcoming reception in the late afternoon of the 25th. It was slated to be outside in a wooded park on the university grounds. It was late May after all. But it was cold. I’ve known cold days in May in Buffalo, but none like that—biting wind and icy sleet. Only twenty or so of the registrants braved the weather. There was fortunately a round wooden structure, covered and enclosed and large enough to shelter us, but with no central heating. Instead it had a coal heat stove. We huddled around on chairs and stools and the part of the circular wall bench near the stove. Although over two hours of nominal daylight remained, the dark clouds and scant windows made it pitch night inside. If I recall correctly, the original intent of a cookout was shelved and replaced by a bulk order of sandwiches and potato chips and other picnic fare.

Nearest the stove sat the 73-year-old Zadeh wrapped in blankets. His face glowed orange as he regaled us in good humor with stories. I don’t think I kept any record of what he said. We felt in the presence of a great man but under surreal conditions—accentuated for Jie and me by our having had a hot lunch in the downtown Montreal hotel for STOC. Somewhere I do have notes of the keynote he gave the next morning before departing—in a modern and heated university lecture room—but I have not unpacked my boxes of old notebooks since my department’s move to a new building six years ago.

His birthplace Baku has been on my mind because I’ve recently read Thomas Reiss’s biography The Orientalist of Lev Nussimbaum, who wrote under the pseudonyms Essad Bey and Kurban Said. Nussimbaum had at least a hand in the writing and production of the 1937 romance Ali and Nino, which is considered the national novel of Azerbaijan. Baku juts into the Caspian Sea and calls itself the easternmost European city as demarked by the Urals and Asia Minor extended east. I wish it had occurred to me to ask about his upbringing and the history between the wars.

Open Problems

We convey our profound appreciation and regrets to his family and friends.


Michael Cohen 1992-2017 and Vladimir Voevodsky 1966–2017

October 3, 2017

Two more tragic losses coming before a greater tragedy

Composite of crops from src1, src2

Michael Cohen and Vladimir Voevodsky were in different stages of their careers. Cohen was a graduate student at MIT and was visiting the Simons Institute in Berkeley. He passed away suddenly a week ago Monday on a day he was scheduled to give a talk. Voevodsky won a Fields Medal in 2002 and was a professor at the Institute for Advanced Study in Princeton. He passed away Saturday, also unexpectedly.

Today we join those grieving both losses.
Read more…

Drama Therapy: A Math Viewpoint

September 19, 2017

What is drama therapy?

Kathryn Farley obtained her PhD from Northwestern University in performance studies in 2007. After almost a decade working in that area, she has just started a Master’s program at New York University in a related field called drama therapy (DT).

Today, I thought I would talk about the math aspects of DT.
Read more…

Happy Birthday Ken

September 15, 2017

It was just Ken’s birthday

Kenneth Regan’s birthday was just the other day.

I believe I join all in wishing him a wonder unbirthday today. Read more…

A TSP Breakthrough

September 11, 2017

A new approximation algorithm

Composite of src1, src2, src3

Ola Svensson, Jakub Tarnawski, and László Végh have made a breakthrough in the area of approximation algorithms. Tarnawski is a student of Svensson at EPFL in Lausanne—they have another paper in FOCS on matchings to note—while Végh was a postdoc at Georgia Tech six years ago and is now at the London School of Economics.

Today Ken and I want to highlight their wonderful new result.

Svensson, Tarnawski, and Végh (STV) have created a constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). This solves a long-standing open problem and is a breakthrough of the first order. Read more…

A Retirement Party for Joel Seiferas

August 29, 2017

A gathering this Labor Day in Rochester

Announcement source

Joel Seiferas retired on December 31, 2016 and is now a professor emeritus in the University of Rochester Computer Science Department.

Today Ken and I wish to talk about his party happening this Labor Day—September 4th.
Read more…

On the Edge of Eclipses and P=NP

August 17, 2017

A topical look at Norbert Blum’s paper and wider thoughts.

Cropped from source

Thales of Miletus may—or may not—have accurately predicted one or more total solar eclipses in the years 585 through 581 BCE.

Today we discuss the nature of science viewed from mathematics and computing. A serious claim of {\mathsf{NP \neq P}} by Norbert Blum has shot in front of what we were planning to say about next Monday’s total solar eclipse in the US. Update 9/2/17: Blum has retracted his claim—see update at end.
Read more…