Andrew Ng’s Machine Learning Class on Coursera

machine_learning_coursera

If you’re interested in taking a free online course, consider Coursera. It takes seconds to make an account and filter through the 700 or so classes currently in the database to find what interests you. Classes are generally affiliated with a university, and professors are often the ones lecturing in the videos online. In addition to video lectures, there are homework assignments and exams, which are submitted electronically, as well as user discussion forums where the students can discuss class concepts.

Coursera embodies the concept of the massive open online course (MOOC) which aims to have unlimited participation to allow (theoretically) anyone in the world to obtain an education for free. Founded in 2012 by Daphne Koller and Andrew Ng of Stanford University, Coursera now has over 7 million users and sports an impressive list of university partners. (Check out this paper for an interesting discussion about MOOCs.)

Coursera is similar to the well-known MIT OpenCourseWare, but it has several advantages. The biggest one is that courses on Coursera will have all class material eventually available to the students who sign up, whereas on MIT OpenCourseWare, you face the repeated problem of lack of video lectures, lack of exams and solutions, and other information, especially with the upper-level courses. Coursera’s website design is also vastly superior. On the other hand, Coursera classes requires the user to sign up in a certain date range, so if you go on Coursera right now, chances are high that some of the classes that you want to take aren’t offered in the near future (and you might have to add it to your “watch list” for the next session).

In the meantime, I’ve been checking out Andrew Ng’s machine learning class, which was what really started Coursera. It’s designed to be a ten-week course, with the following syllabus:

  • Week 1: Introduction, Linear Algebra Review, Linear Regression with One Variable
  • Week 2: Linear Regression with Multiple Variables
  • Week 3: Logistic Regression and Regularization
  • Week 4: Neural Networks (Representation)
  • Week 5: Neural Networks (Learning)
  • Week 6: Applying Machine Learning Algorithms
  • Week 7: Support Vector Machines
  • Week 8: Clustering, Dimensionality Reduction
  • Week 9: Anomaly Detection, Recommender Systems
  • Week 10: Large-Scale Machine Learning

A third of the grade is based on multiple-choice quizzes, and the rest is determined by programming assignments, to be done in MATLAB or Octave, the latter of which is an excellent free version of the former. Octave is one of the simplest programming languages out there, so it shouldn’t be too difficult for one to get used to it.

After going through the first few weeks of the course, here are some quick impressions:

  • Advantages: The class doesn’t have many prerequisites (no calculus, no probability, etc.) and is accessible to a broad audience. Professor Ng’s video lectures are excellent. In fact, it’s nice to see that someone who can write complicated papers can clearly explain the basics. There seems to be a lot of collaboration among the students. The class covers most of the concepts I’d expect in a machine learning class, but for some reason doesn’t seem to cover the naive bayes and decision tree learning algorithms.
  • Disadvantages: The simplicity of the class is also its major drawback — to someone like me who already knows machine learning, the class is too easy and I watch video lectures (for review purposes) at 1.5x or 1.75x the speed (a nice feature, by the way). Professor Ng often has to say “the discussion of this concept is beyond the scope of this course….” Consequently, a student at Stanford is better off taking Professor Ng’s “actual” machine learning course.

Again, if you’re interested in learning more about any subject, I encourage you to check out Coursera. There’s definitely a heavy focus on computer science — not surprising, given that the founders are computer science professors — but there are courses in subjects as diverse as health, law, engineering, and music.

Posted in Computer Science | Tagged , , , , | Leave a comment

Cholesterol, Saturated Fat, Grains, Meat, and Other Diet Controversies: why are There so Many People Challenging Conventional Wisdom?

As I mentioned in my recent post introducing Mark’s Daily Apple, I have become more interested in understanding diet, nutrition, and health. Sadly, this doesn’t come without challenges, and in this post, I’d like to discuss some of the current controversies that make it difficult for me to decide what to eat in order to maintain a healthy life.

First, let me provide some background. During elementary and middle school, I learned about the United States Department of Agriculture’s infamous food pyramid. Of course, like most Americans, I didn’t adhere to it exactly, but I at least kept it in mind, so it did impact the way I ate for most of my life.

After reading Fast Food Nation, I also avoided most forms of fast food starting in high school. On the surface, this diet approach seems to be excellent — just follow the food pyramid and avoid McDonald’s. Unfortunately, up until now, I had been unaware of the vast amount of misinformation, politics, and shoddy science of food that plague the country and are likely correlated with the shocking prevalence of obesity, heart disease, diabetes, and other chronic illnesses.

Continue reading

Posted in Everything Else | Tagged , , , , , , , , | 2 Comments

Introducing Mark’s Daily Apple

Summers are nice because they offer me a break from an intense academic environment. As a result, I’ve had the chance to explore other fields that interest me, and one of them concerns the human diet. Simply put, I’m trying to figure out what I should eat in order to maintain a healthy life.

The Original Food Pyramid

There’s a lot of information available that we can use for diet advice. For instance, the United States Department of Agriculture has their famous (or infamous, as I’ll get to shortly) 1992 food pyramid:

USDA_Food_PyramidLet’s suppose we use this as a guide to optimal health, which seems reasonable because it’s from a United States government organization. (It shouldn’t be, because that pyramid has already been scrapped in favor of new dietary guidelines, but it’s good to discuss it to see the historical perspective on food.)

Unfortunately, even without consulting outside sources, I can already see several problems:

  1. It makes no distinction between whole or minimally processed foods and heavily processed foods. (I’ll throw in whole grains in the “minimally processed foods” category.) The former group includes fruits, vegetables, and animal products obtained from their natural state. The latter group would include pizza, chemically-laden meats, and so on.
  2. It suggests consuming fats, oils, and sweets sparingly, but the dairy and protein groups already include substantial amounts of fat. And my understanding is that fat has long been essential for human health. Our early ancestors ate lots of plants, but they would also eat the complete carcass of animals, including fat-dense organs that we shun today.
  3. It suggests that the serving counts should not be exceeded, which might impose unnecessary restrictions. Consider my situation: I love eating huge salads, and I also have a habit of downing an entire bag of baby carrots as an afternoon snack. This means that I easily rack up 7-10 servings of vegetables daily (depending on how you define a serving), but according to this pyramid, I shouldn’t be eating so many vegetables.

I know that no pyramid can disseminate detailed information in such a small amount of space, but such simple modifications could go a long way.

This brings me to the next part of this post.

Mark’s Daily Apple

My quest for learning more about health, diet, nutrition, and food led me to Mark’s Daily Apple. It’s an extensive blog written by Mark Sisson, a well-known advocate of eating the Paleo diet (though he calls it “Primal”) and preventing chronic diseases of civilization (e.g., diabetes and heart disease) by lifestyle choices. I didn’t think much of this at first, but the more I thought about the food I ate, the more I kept coming back to his blog. It also didn’t hurt that he’s another Williams alum, which might have piqued my curiosity.

Mark Sisson advocates his own food pyramid, which emphasizes meats (including fish, eggs, and fowl), vegetables, fats, fruits, and some carbohydrates. Notice the distinct lack of bread, rice, cereal, and pasta! It’s a long story about why he excludes them, but Sisson explains this in his blog and has some decent (but in my opinion, not overwhelming) evidence to back up his claims. For the most part, I favor his food pyramid over the 1992 USDA food pyramid, but I think Sisson’s pyramid should have kept vegetables as the “base” group to reiterate how they should compose the bulk of the diet in terms of volume.

If you want more information about his philosophy towards food and life, I’ll refer you to his Start Here page. When reading Mark’s Daily Apple, realize that Mark Sisson’s focus is not just on nutrition, but indeed, on a lifestyle. His advice encompasses sleep, play, exercise, and many other factors that affect our health. There’s so much out there that Mark Sisson posts new entries daily and still has no shortage of topics to talk about. His blog has been on my About page for a while, but I thought it would be interesting to actually introduce it in one of my entries.

In a future blog post, I’ll delve more deeply into diet controversies. (Don’t worry — this digression doesn’t mean that I’m turning into a nutritionist…)

Posted in Everything Else | Tagged , , , , , | 1 Comment

More Deaf Computer Science Ph.D.s

About a year and a half ago, I wrote a blog entry about deaf computer science Ph.D.s. I recently revisited this topic and found out that I missed a few people from my earlier list, so this post is a continuation of my previous one. Here are the new Ph.D.s:

  1. Vinton Cerf (Ph.D., University of California, Los Angeles, 1972), though if we’re getting picky, he’s hard-of-hearing.
  2. Daniel Berry (Ph.D., Brown University, 1974)
  3. Dimitri Kanevsky (Ph.D., Moscow State University, in the 1970s), though again, if we’re picky with our criteria, he actually got his Ph.D. in math.

These three people are all established scientists with impressive resumes.

Vinton Cerf is known as one of the “fathers of the Internet,” which should say a lot about his contributions to computer science. For instance, he helped to form the Internet Corporation for Assigned Names and Numbers (ICANN), which manages the global domain naming system (its headquarters is in the U.S. … I’m not sure how other countries feel about that). Not surprisingly, Dr. Cerf has an array of awards and honors, including the Turing Award, the Presidential Medal of Freedom, and the National Medal of Technology. In 1997, he joined the board of trustees at Gallaudet University. Nowadays, he works at Google.

Daniel Berry has been deaf in both ears since birth, and can only use a hearing aid in one ear. He does not sign because his parents spoke English and he picked up lipreading, which may be one reason why I didn’t know of him until now (and he mentions on his website that he doesn’t have many hearing impaired acquaintances). In terms of academics, he got his computer science Ph.D. from Brown back in 1974. He then joined the faculty at UCLA from 1972 to 1987, The Israel Institute of Technology from 1987 to 1998, and then at the University of Waterloo from 1988 to now. Note that all three of these schools have outstanding computer science departments, which should give you an idea of his research ability. Professor Berry provides a brief paper on his website that describes his background in more detail, as well as his recommendations for making the web more accessible.

Dimitri Kanevsky got his Ph.D. in Russia in the 1970s (I can’t find the exact date) and held research positions at the Max Planck Institute in Germany and the Institute for Advanced Study in Princeton. Armed with mathematics background but a desire to make practical use of it, he joined IBM in 1986, where he still works today. Dr. Kanevsky specializes in speech recognition, so there’s a good chance that any recognition software today traces its origin to him. Dr. Kanevsky’s resume includes being named an IBM Master and more than 15o U.S. patents.

Unfortunately, I’ve never personally met any of these people, but it would be nice to do so someday.

Posted in Deaf | Tagged , , , , , | 1 Comment

Padden Named Social Sciences Dean at UC San Diego

In deaf-related news, I just found that Carol Padden, professor of communication at the University of California, San Diego, has been named dean of the social sciences at her school. Her tenure will start in October.

I didn’t know her before this announcement, so it was interesting to read about her background. She was born as the second deaf child of two deaf faculty members at Gallaudet University. She started her education in a deaf school and then became a mainstreamed student at a public school system.

After graduating from Georgetown in 1978 with a Bachelor of Science in Linguistics, she went to UC San Diego to pursue a PhD in Linguistics, which she obtained in 1983. She has since been on the faculty (and, of course, will be a dean) at the same school, specializing in the study of American Sign Language. Professor Padden seems particularly interested about understanding the variety of sign languages that are developing throughout the world. For instance, what properties of sign languages develop after only one or two generations of use? Which ones require more time to evolve? While I can’t judge her research, it must be top-tier, since she was a MacArthur Fellow in 2010.

Posted in Deaf | Tagged , , , , | Leave a comment

Friendly Computer Science Textbooks

I’d been meaning to post this earlier, but I got sidetracked by Project Euler (more on that later). In any case, I want to list a few computer science textbooks that, in my opinion, are written in a friendly style and are easy for someone to read like a novel. These are my favorite kind of textbooks, because they often incorporate two important aspects: elaboration and examples. Notice that this does not mean that mastering the corresponding subject is easy! It just makes it easier for an experienced and educated reader to do so.

I’m inspired to think about this because, as much as I enjoyed my complex analysis class last fall, the textbook we used glosses over so many details that it made analyzing some of the proofs excruciatingly difficult. At least, for me … I can’t speak for everyone in the class, but my professor did have to explain that the goal of his lectures was to emphasize why the authors/book did something in their proofs.

In the past few weeks, I read parts of Methods of Mathematical Economics, a textbook about the mathematics behind linear programming and other popular applied mathematics techniques. It is written in a conversational style (the author uses “I” instead of “we”), and it was very helpful to me for a final project.

Here are four books on the computer science side that I’ve found to be very readable.

  1. Algorithm Design, by Jon Kleinberg, and Eva Tardos, presents an introduction to the common themes underlying an algorithms course. I enjoyed it because it emphasizes the decision-making behind many of the proofs. In addition, it contains several sample problems with detailed solutions. These solutions also explain why certain approaches might not work or are suboptimal.
  2. Artificial Intelligence: A Modern Approach, by Stuart Russell and Peter Norvig, is a surprisingly readable “encyclopedia-like” book about AI. I do not recommend reading the entire thing, especially in one sitting! But if you pick out a single chapter, the book should serve you well. I talked with Stuart when I was visiting Berkeley, and he told me I needed to know more learning theory. I asked him how I could learn more, and he said: “read the book.” Good — I’ll do that!
  3. Distributed Systems: Principles and Paradigms, by Andrew S. Tanenbaum and Maarten Van Steen, is about concepts of distributed systems (i.e., those relying on multiple computers/machines). This book is filled with examples. Almost every concept is explained with an immediate real-life example.
  4. Introduction to the Theory of Computation, by Michael Sipser, overlaps somewhat with Algorithm Design, but emphasizes automata, computability, and complexity, rather than pure algorithms. It is a concise book, but somehow provides the impression that it’s detailed and expansive. Fortunately, each chapter contains problems with full solutions.

I’d be interested in knowing if there are other popular, readable computer science textbooks.

Posted in Computer Science | Tagged , , , , | Leave a comment

2014 Williams College Phi Beta Kappa and Sigma Xi

After finding out I made it into the Williams College Phi Beta Kappa and Sigma Xi honor societies, I went online looking for more information about the induction ceremonies. Unlike the commencement exercises, there does not seem to be much out there about these two ceremonies, so I figured I might explain what goes on during these events.

Just a quick background: Phi Beta Kappa and Sigma Xi are two honor societies that some colleges and universities offer to their students. Phi Beta Kappa tends to admit students based on GPA and breadth of coursework, while Sigma Xi admits those who have done and plan to continue doing science and math research. (At Williams College, Phi Beta Kappa is solely based off of GPA; roughly the top 12.5% of the class gets in.) In the Williams College class of 2014, I believe there were 68 Phi Beta Kappa inductees and 56 Sigma Xi inductees. Of course, there was significant overlap among the two groups.

Phi Beta Kappa

We had several speakers in this ceremony. Some provided administrative information, such as “welcome to the society” and “please do X to complete your application” type of stuff.

To me, the most notable speaker was the Williams professor who introduced us to the history of the Williams College Phi Beta Kappa charter. It started in 1776 at the College of William and Mary (the college that, according to the speaker, our grandmothers still think we go to) and then spread to Massachusetts when Harvard acquired a charter in 1779. Williams tried numerous times to acquire one from Harvard, but did not succeed until 1864. The charter we obtained, written in Latin, was shown on display throughout the ceremony. Sadly, it appears to be the only one of its kind in which the granting institution’s name (“Harvard”) was written in much larger text than the name of the school being awarded (“Williams”)!

After the history talk, another guest speaker highlighted the diversity of the majors studied and languages spoken among the Phi Beta Kappa members. He listed almost every major and language, except for computer science and American Sign Language. I am not sure how those two didn’t make it on his lists.

Near the end of the ceremony, each of us went on stage to receive Phi Beta Kappa materials.

Sigma Xi

This induction ceremony was much shorter than the one for Phi Beta Kappa. The Sigma Xi speaker spoke briefly about how he wished us all an excellent career in science, and encouraged us to try and get promoted to full membership. All the Sigma Xi inductees stood up and got to the stage to get our materials, and then we stood there while all the parents and other family members took pictures. I noticed at least one of the old class pictures is online — if the 2014 one goes up, you should try and find me.

Posted in Everything Else | Tagged , , , | Leave a comment

Speak vs. Use ASL

Here’s an interesting question to consider: which one of “he/she/someone uses ASL” or “he/she/someone speaks ASL” should you use in writing and conversation? The answer isn’t obvious to most people without knowledge of ASL, because while speak is the default term for most languages, it’s not clear if ASL falls under that category due to its visual nature (and, I might add, its no-speaking requirement).

I never had someone tell me which of the two phrases to use, and I’ve flip-flopped on my usage. I would say speak when I was younger, then in recent years I switched to saying use, and now I’m starting to think I should go back to speak. My recent shift is due to a discussion on the Deaf Academics mailing list.

Here is a video of someone arguing on behalf of speak, and here is the transcript (the meaning of s5s is explained in the video):

“Hi, I’m Michele Westfall and I currently write for ASL Rose. John Clark asked me to talk with you about Speak vs Sign, and I’m happy to do so. It’s no problem at all. Why? For the past couple of years, I’ve been encouraging Deaf people … really, everyone to use the word “speak” in relation to ASL. Why? I’ve been noticing that the hearing society frequently sees us as “silent.” Yes, they regard ASL as “beautiful,” but when it really counts and really comes down to it, we are still SILENT in their eyes. I’ve noticed that both hearing and Deaf people tend to say “ASL users”…and that bothers me.

Think about it: hearing people never say “English users”…”French users”…”Spanish users”…”Chinese users.” Really, the contrast is huge. We say “ASL users”, “we sign”, “we do ASL”….which serves to emphasize the difference between ASL and all other voiced languages and puts way too much emphasis on the Voice. Hearing people get to say “speak”…and we can’t.

I disagree with that. I say, YES, we speak ASL. Understand, I’m not saying we have to say “We speak [using 4-handshape on chin] ASL.”  That’s wrong. What’s the right way? “We speak [using s-5-s handshape] ASL.” Get it? s5s = speak…that’s our version of speak. Don’t say 4-handshape on chin/speak. That’s the hearing version (or the hearing-minded version). We s5s/speak ASL. Or…”I’m an ASL s5s/person [speaker].” Or “The ASL s5s/person [speaker] for the day is XXXXX.”

Just an example. You s5s/speak ASL. I s5s/speak ASL. To let you know, I’ve been saying this for the past several years. I even write it…for example “I speak ASL.” on paper. In English sentence….I speak ASL/you speak ASL. And hearing people always accept it and never object. They don’t say, “Wait a minute! What’s this?” They accept it because it seems natural to them. I think…it’s time. We’ve been saying all along that ASL is a language. It means we must change our words to reflect that reality. What’s our reality? ASL is our language, and therefore…what? We speak ASL!  We don’t sign ASL.

Saying “We sign ASL” gives way too much credit/weight to Voice. No. Enough. It’s time to bring ASL on equal footing with all other voiced languages. You speak ASL. I speak ASL. We don’t “do” ASL. We don’t “use” ASL. We speak ASL. We are ASL speakers. I hope this makes sense to you. If not, let me know. Bye bye.”

Posted in Deaf | Tagged , , | Leave a comment

Git and Git Immersion

One critical skill I acquired this past year was how to use git. It’s a distributed version control system that is often used by programmers and software companies to manage their code. The reason why git and other version/revision control systems are so useful is that they allow multiple people to easily work together on a project by means of a shared code repository. Rather than have one person work on a small part of a project and email any updates to everyone else, he or she can instead “push” their modifications to the repository, and other collaborators can “pull” the updated code so that they are working with the latest version. (I use “push” and “pull” since these are git-related terms, but other systems have different terminologies for adding and getting repository code.)

If the current code has serious issues, it is possible to roll back to a previous version, which is just like having a bunch of backup files. This is one of the main benefits of using version control systems, even for a project managed by just one person. For instance, I used git for my undergraduate thesis and the related code, so whenever I wanted to work on it, I would just pull from the current repository, make my changes, and then push at the end. Git turned out to be a lifesaver when, two weeks before I had to send my thesis to the rest of the department, I accidentally deleted a chapter. The solution? Pull the latest version of that chapter from the repository.

Git is very common among computer science students, and possibly even more popular among computer science Ph.D. students, so it’s a good skill to have in one’s toolkit. I learned git largely by trial and error and having other people tell me what to do, but one resource I found that might be useful to beginners is Git Immersion. This is a tutorial that walks you through the basic commands of git. It was mostly review for me, but I did learn a few things, such as “git mv” which will save me time when moving files in my repositories. In the past, I would move files, then delete the original files from git, then add the new ones (in the different location), then commit everything, but git mv does all that at once. My one qualm is that I wish they incorporated GitHub in the tutorial, but it’s technically not part of git, so I can see the reason for excluding it.

Say, I wonder how non-computer scientists write their theses, or more accurately, those who don’t employ version control systems. I would hate having to save countless backups for a variety of files. In addition, another key benefit of git is that each time you make a change, you can record the high-level idea of this modification, and it will appear in the log for future reference. This makes it easy to go back and search for an old version of a file.

Posted in Computer Science | Tagged , , | Leave a comment

Two Suggestions on Grading

As my final college grades come in, I once again reflect back on my undergraduate classes and their grading schemes. The key question: how much did my grades correspond to the amount of material I learned or the amount of the subject I mastered? This is a tricky question to consider. Obviously, the amount of “mastery” required to get an A varies from school to school, subject to subject, and even course to course within the same field. But I believe that everyone can give a rough interpretation of how much he or she learned from a class (at least, right after it finishes). This may or may not correspond to the actual grade.

For the sake of completeness, here are four cases that can occur, supposing for simplicity that an A is the standard for excellence:

  1. You get an A, and feel like you deserved it.
  2. You get an A, but don’t feel like you deserved it.
  3. You get less than an A, and feel like you deserved it.
  4. You get less than an A, and don’t feel like you deserved it.

I have had all four of these cases happen at Williams. Case 4 is obviously bad, since everyone feels slighted when this happens. But Case 2 can arguably be just as worse in the long run, since you know less about the subject than what might be suggested from your transcript, but employers may not see that until after you’re on the job. In an ideal grading scheme, only cases 1 and 3 would occur.

So how can classes be designed to reduce instances of the two undesirable cases? I have two suggestions, but keep in mind that these are aimed at computer science and/or mathematics courses. I don’t have enough experience with other majors, though these might work for corresponding classes anyway.

Suggestion 1: Require Individual Work

One of the main observations I’ve made while at Williams is that sometimes it is possible to “hide” your weaknesses by joining a group and earning the group’s collective grade. For instance, this might involve a computer science group project where everyone in the group gets the same grade. In these cases, your grade is largely determined by who you work with!

Learning how to work in groups is certainly an important skill, so I’m not suggesting that these projects be eliminated entirely. Instead, I urge professors to divide up projects in two categories: those that allow groups and those that must be done individually. Or during a group project, perhaps require that everyone give a self-evaluation of their peers. This happened in my African Studies class in the Spring 2013 semester. (But this tactic runs into problems if you work with shady people … again, it matters who you work with!)

In a typical computer science course, grading is determined by a combination of group work, homework, and exams. For mathematics courses, they typically use only homework and exams. This brings me to my next suggestion…

Suggestion 2: Make Exam Score Ranges Larger

I think this suggestion will be more helpful than requiring individual work, and in any case exams are (I hope!) an example of something in that category. The problem that I have experienced in Williams classes is that exams are often set so that the vast majority of students (say, 85%) get scores in the 85-100 range. In a ten question exam where all questions are weighted equally, the first nine might be minor variations of homework problems, and only the last question gets used to differentiate between those who really know the material.

But this doesn’t give enough discrimination among students, and it means more students might get As because they lucked out on that tricky question, and more students might get Bs because they happened to make a careless error on one of the easier questions.

Increasing the exam score range so that the median and mean are within the 70-75 range would give professors more ability in distinguishing the different categories of students. With an “85-100 exam,” if I get a 94 and another person gets a 95, should I consider myself equal to that other person in terms of knowing the material? If I lucked out on that last question, that class might end up giving me an A, but I might view it as Case 2. But if scores were distributed over a 40-100 range, all of a sudden that 94 starts looking a lot better. And if I end up with, say, a 70 on an exam where lots of students get 90s, I’ll be momentarily disappointed, but the grade I get will reflect that I didn’t know enough of the material to warrant a higher grade, and that others were more deserving of getting an A.

I think a lot of students won’t like larger score ranges, but really, this shouldn’t be the case. Professors should assign grade ranges appropriately, so that scores in the 80-100 range would be an A, rather than the “standard” 90-100 range. All these numbers are really arbitrary, and in the real world, no one knows “100 percent” of their field/profession anyway.

PS: It’s good that Williams’ final exam period ends five days before the last day of May. Otherwise, I would have broken my streak of having at least one blog post a month…

Posted in Everything Else | Tagged , , | Leave a comment

How to Quickly Tell That P = NP or P =/= NP Papers are Bogus

 

PvsNP

For one of my final projects this semester, I’m working on something that’s loosely based off of the traveling salesman problem (TSP) and the P vs NP question, the latter of which is arguably the most famous open problem in all of computer science. Whoever proves that P = NP, P =/= NP, or that the problem cannot be proved/solved for whatever reason, gets a $1,000,000 prize from the Clay Mathematics Institute.

As part of my pre-project research, I’ve had the chance to look at a few papers about the TSP and the P vs NP question. Some papers have been great to skim, if only to gather insights about the TSP’s integer programming formulation, but others (typically those that claim to solve P vs NP) are clearly mockeries. In this post, I’d like to discuss the ways one can quickly tell that papers claiming to solve this question — or in fact, any other famous open problem — are bogus. Let’s do this under the assumption that you’re looking at a pre-print of the paper before it has been reviewed by a preeminent conference or journal.

For reference and amusement, here’s a page that lists (as of this writing) one hundred and five papers/proofs that (mostly) claim to solve this question. The author of this page states that only one of these papers has appeared in a peer-reviewed journal. And of course, it doesn’t solve the problem:

Note: The following paragraphs list many papers that try to contribute to the P-versus-NP question. Among all these papers, there is only a single paper that has appeared in a peer-reviewed journal, that has thoroughly been verified by the experts in the area, and whose correctness is accepted by the general research community: The paper by Mihalis Yannakakis. (And this paper does not settle the P-versus-NP question, but “just” shows that a certain approach to settling this question will never work out.)

Before we begin, let me just start with a disclaimer. Yes … this problem may be solved throughout my lifetime. So the title of this blog post may be changed to “How to Quickly Tell That All but One P = NP or  P =/= NP Papers are Bogus” … but for now it is safe, as the Clay Mathematics Institute has yet to recognize a solution. Furthermore, by definition, if P = NP, then the papers claiming that P =/= NP are erroneous, and vice versa. So, under the assumption that (for whatever reason) you’re skimming a paper claiming to solve the P vs NP question (or another famous open problem), what are three quick signs that the paper is not worth reading?

Reason #1: The author isn’t a top theoretical computer scientist (or, if there is more than one author, then none are top theoretical computer scientists) The logic is pretty simple. The top theoretical computer scientists are more likely to be at the forefront of the P vs NP question. Thus, they will know the relevant background work, understand why previous approaches failed, and may have ideas or new techniques to bring to the field. If you don’t know the name of an author, then a good proxy is the prestige of the university he or she resides. Again, the logic is simple: ranking of universities correlates with quality of professors.

But … an unknown mathematician made the biggest academic result in all of science, technology, engineering, and mathematics in 2013. I’m referring to when Yitang Zhang made groundbreaking progress on the Twin Primes Conjecture. (If I was writing this post last year, I’d be talking about the Higgs Boson result in 2012, which was from several established scientists. But I find Zhang’s case to be more interesting to discuss, as some may consider it as a counterexample to Reason #1.) On the other hand, Zhang’s paper, which is available on the Internet somewhere, satisfies my two other reasons.

Reason #2: The paper isn’t written using LaTeX. Oh yes … LaTeX is awesome. And it’s a shame that some people who write up these proofs do not even take the time to make their papers look nice. All top computer scientists will use LaTeX for their papers, and about 99% of the non-top ones will. Yet some of the papers I saw on that linked page were clearly written using a different (and inferior) word processor.

The use of LaTeX is important to give the impression that one is serious about his or her work by presenting it cleanly to readers. But there’s another easily-identifiable characteristic of bogus papers that can make it clear that the paper isn’t worth reading. That is …

Reason #3: The paper is short. This can vary from discipline to discipline, and whether the paper was written using LaTeX or not (with non-LaTeX papers tending to take up more pages due to poor formatting/spacing). I would suggest that any paper that is shorter than the equivalent of about 40 double-spaced, 12-pt font, normal-margin pages cannot contain enough information to really resolve the P vs NP question. For that kind of paper, the authors would almost certainly need a full section of more than 10 pages just to discuss the background work. Then it’s another 20 or more pages to discuss the new techniques or ideas the paper brings to the field. Then it’s 20 more to set up the lemmas to prove it. Then 20 more to prove the theorem. Then 20 more to show why common counter-arguments are false. And so on.

Only one of the papers I checked on that P vs NP page were long enough to my liking. I didn’t have the time to see all of them, so maybe I am missing a few others. It is worth noting that Zhang’s paper was around 50 pages.

Posted in Computer Science | Tagged , , | 1 Comment

I’m Going to Berkeley!

OLYMPUS DIGITAL CAMERA

This entry is a few days overdue — my apologies. (Excuse of the day: my thesis is due in a few weeks.) Admitted students had until April 15th to make their graduate school choices, and I made mine on April 13. As you can no doubt tell from the title of this post, I have committed to the University of California, Berkeley. I will start pursuing a Ph.D. in computer science there this fall.

It was not an easy decision, especially because I only applied to top-tier schools. I was debating for a full month between Berkeley and Washington (with each school seemingly have the edge on various days), but in the end, there were several factors that made me end up on Berkeley.

It’s an exciting time for me! I have already received an email about setting up my Berkeley ID, and I can’t wait to get started this fall. I hope that the next six years (five if I’m extraordinarily lucky) will bring fulfilling and rewarding experiences.

Posted in Computer Science | Tagged , , | 1 Comment

Are You Disabled? Your Boss Needs to Know

Recently, there’s been a flurry of emails in one of my subscribed email lists about some recent regulations that require employers to ask if their employees have a disability. I’ll list the main points of the linked Wall Street Journal article.

  1. U.S. regulations now require federal contractors to ask their employees if they have a disability. It is up to employees to determine if they wish to disclose any information. (So the title is actually misleading, as the bosses don’t need to know.)
  2. Those contractors that don’t employ a minimum of 7 percent, or can’t prove they are taking steps to achieve this goal, could face penalties.
  3. This applies to contractors with at least 50 employees or at least $50,000 in government money.
  4. The Labor Department issued these regulations to help combat the high jobless rate of the disabled population.

Some people responded to the email list saying that these regulations were long overdue, but a few were not satisfied or had reservations. (To put it briefly, I think these are “overdue” mainly because they help raise awareness of the challenges disabled people face in the workforce, but for now I’ll discuss what others have said.)

A number of people talked about how disclosing information is a difficult and sensitive topic for people with hidden disabilities. Should they tell their bosses or not? Consider the case of someone with a hidden disability applying for a job. Do they feel confident enough to disclose their disability to a hiring committee before any job offer? I suspect that if the job applicant knows that these contractors are trying to recruit people with disabilities, that will raise the probability of disclosure, but I doubt any information will be easily accessible.

Related to the visible/hidden disability discussion, some also worried that employers would give preference to people with visible disabilities to fill in the ranks if not enough employees were willing to disclose hidden disabilities. Because of how the ADA has expanded the definition of a disability, it’s very likely that contractors already have way more than 7% of employees who are disabled.

And of course, there is the possibility that managers and hiring committees of these contractors will protest, arguing that they now have to “lower the bar” to hire a specific group of people.

There didn’t seem to be much discussion about deaf people, which would have been related to the visible/hidden disability discussion because I would argue that deafness can fall in both categories.

Posted in Deaf | Tagged , , , , | 1 Comment

Graduate School Visit #4: The University of Washington

I departed from San Francisco and landed in Seattle near midnight. Fortunately, Washington’s visit days didn’t start until the following day (Tuesday). They were the only school I visited that restricted their visit days to be two days, probably because they know they have lots of cross-admits with Berkeley. I rode a shuttle that brought me back to the Silver Cloud Inn near the university’s campus. I did request to live with graduate students, but I was told that Washington had over ninety students show up to visit days, and there were sadly not enough hosts to accommodate all of us.

Washington_PaulAllen

The following morning, another shuttle took a group of students from the hotel to the Paul G. Allen Center. It was quite nostalgic coming back to the same building that I spent a lot of time in while at the 2011 Summer Academy, and I still remembered my way around it.

Continue reading

Posted in Computer Science | Tagged , | Leave a comment

Graduate School Visit #3: The University of California, Berkeley

Berkeley2

After visiting Cornell, I had a short break at Williams and then traveled to San Francisco to visit the University of California at Berkeley.

Continue reading

Posted in Computer Science | Tagged | Leave a comment