Tuesday, October 1, 2013

An Outcome: Inchoate View of Algorithm Ontology

Since Moshe Vardi's Editor's Letter coincided so nicely with my own formulation of the theme of the philosophy of computer science class of Fall 2012, I wrote a letter to the editor (of the Communications of the ACM) outlining some of the questions that suggest a more grounded and less formal view of the algorithm.  I am now investigating the consequences.  (Here's a sentence that was deleted during editing:  "Let us suspend the notion that what a computer DOES must inform what an algorithm IS.")

The letter can be found here.  Please scroll down, as it is not the top entry.

http://cacm.acm.org/magazines/2013/6/164592-how-to-claim-your-fair-share-in-academic-publishing/fulltext

Monday, May 27, 2013

A New Topic: Objective Search


Here is a new and different topic for a Philosophy of Computer Science class.

Objective web search-- search that carries no geographic or demographic predilections-- would seem to be critical for research. Google offers the option to turn off search history personalization, and to change the geographic context.  One attractive way to accomplish this would be for the search engine to explicitly list
all the factors at play (date and time, Internet activity, IP address area, recent purchases, social network contacts) in a search, and allow piecewise disabling of the filters.

Two types of parameters affect the results, of course-- the user's demonstrated interests and preferences, maintained in personalization data, and other people's opinions, reflected in the priority of results presented.  Is there any way to request "universal" search, which would return the same results under any circumstances, thwarting both types of parameters?  In the category of others' opinions, the Google algorithm PageRank, determining the order of appearance of retrieved web pages, obviously exerts an enormous influence on what users see.  What kind of factors affect the PageRank algorithm's authority measures?  Would objectivity require forgoing PageRank altogether, and if so, could some other efficient ranking organize the millions of results?  For example, could a known bias in one parameter be offset somehow by a conflicting bias?

Along with the question, "Can we get completely objective results from Internet search engines?", other questions arise:

1. Do students, and even academic staff and sophisticated researchers, understand the implications of personalized search?
 
2. As a free service, is Google required to provide services and options like this that the public, or the academy, demands?  Should it be treated as a public utility, under regulations that would force it to do so?  If so, how does the international nature of the Internet bear on that treatment and those regulations?

3. Is a "universal" or truly objective point of view for web searches possible, meaningful, desirable?  Is Google responsible for not just reflecting, but successfully defining, such objectivity in its presentations of results?  Is Google responsible for exposing all the factors pertaining to its searching and ranking algorithms?  Does the rise of the Internet affect traditional issues of subjectivity in research?

Under this topic, objective web search, the philosophical subject matter includes ethical and governance issues respecting social justice, as well as, perhaps, the epistemology of the prediction of requests.  The computer science subject matter includes design and analysis of search algorithms, as well as myriad issues regarding efficient distribution and retrieval of data.  The topic invites a multi-disciplinary approach.  The libraries of any educational institution would have cogent contributions to make.  The social sciences could advise on the effects of community, local, and regional factors manifest in socio-economic and business data.  History can tell us of the long-term effects of limited or distorted information.  

Friday, December 14, 2012

The Early Results

As the semester winds up, I feel that the course has been a success.  This precedes grading of the final exam, and inspection of the student evaluations, and is colored by the usual relief on achieving the minimal standard that no disaster occurred.  No one dropped out after the first week, no one imploded, and no one ran screaming from the classroom.  (As they must, for greatest significance, these statistics include the instructor.)

As a quick means of illustrating the outcomes, while keeping student work confidential, let me simply provide the questions from the Take-Home part of the final exam (which was complemented by an In-Class part).

========


1. Although we still haven’t decided whether an algorithm that we refer to by name, such as Selection Sort, includes all of its dynamic instantiations (executions), we know that it can’t be defined fully by just one execution trace. Why?


2. We have seen that games rely on input data during execution. Theoretically, the result of any deterministic process that has all input known at start can be computed by an observer without even running. Consider an auction, as well, and explain whether these things are algorithms, in your opinion.


3. (From the Final Review class): If a description, including task and preconditions, is part of an algo- rithm, what kind of part is it? What is the ontology of the description, and how does it relate to the ontology of the instructions? Here are some possibilities.

(a) The preconditions, because they are don’t fit our definition, are a separate but necessary part of an algorithm. The algorithm object is really a pair of things, one a written description and the other a written set of instructions as we have conceived of it.

(b) The preconditions are implicit in the instructions themselves, and don’t require a separate recognition. The algorithm is nothing without those conditions. So Binary Search, for example, because it works only on sorted data, “assumes” sorted data, without any need to say so explicitly.

Choose one, or make up your own, and defend it based on our accepted definition of algorithm, and your own view of the unsettled questions.


4. Choose one of the questions below to answer. Your answer may be speculative, but give reasons for your claims.

(a) We have never clearly discussed one of the questions from the textbook: Do we ourselves embody algorithms? This does not mean executing an algorithm deliberately and consciously; it means how we accomplish tasks in our daily lives. We have discussed performing Binary Search in a naive form, when searching in a phone book, for example. How about others, such as transmission protocols and LIFO processing? Does your view on these questions tell us anything about algorithms in general?

(b) Is recursion itself an algorithm? Recall that we have seen a definition of primitive recursion (giving the minimal structures of a programming language) that includes this operation:
f (x, 0) = h(x) 
f (x, succ(y)) = g(y, f (y)
Although it is given as a declarative, contributing to the definition of a set of functions, can it be construed as a set of directions and thereby an algorithm in itself? Explain your answer by using aspects of algorithms that we have seen in this class.


5. We have a list of still-controversial properties, as given in Chapter 10 of the textbook. These are attributes that may or may not apply to algorithms in general (or perhaps they have different values for individual algorithms). They are inter-dependent in many ways. Pick one and explain how settling its status would affect two of the other controversial properties.



Sunday, October 28, 2012

The Intuitive Path


It should be clear from earlier postings that, in this class, we want to investigate algorithms not as theoretical structures born of definitions and theorems, but as real, manifest, and colorful-- whatever that means, whatever they turn out to be, whatever flavor of ontology turns out to apply.  And we want to get there by going straight ahead down the path of inquiry, not branching through a thicket of terminology.

I wish to guide the class into ideas that come directly from their own experience of algorithms.   I admit to a lack of rigor.  I look about, ready to seize upon any justification for this plebeian approach.  And I find one-- experimental philosophy.

The young professor Joe Ulatowski, already known to us and visiting here for a year, came to my class for a discussion of experimental philosophy.  From this, the students gained (1) a general definition, based on the usual ethical issues such as trolley problems, (2) an understanding, and validation, of how the querying of our own and others' thoughts might aid the articulation of the concept of the algorithm.

I tossed out a couple of thought experiments, thinking that they were trivial and would be supplanted by more sophisticated version.  They have served well, however, and are still providing food for thought.

1.  Company A runs this algorithm to generate payroll: Take hours, take rate of pay, multiply together hours 40 or less to get the pay, then multiply hours over 40 by (rate*2), and add that to the pay.
Company B runs this algorithm:  Take hours, take rate of pay, multiply together hours 40 or less to get the pay, then multiply hours over 40 by (rate*1.5), and add that to the pay.  Are they executing the same algorithm?  Answer by consensus:  Yes, because the overtime rate is easily parameterized.  But what if Company B applies different overtime rates to different positions?  What if Company B adds a bonus in its payroll processing?

2.  In Company A, a manager wants to see a list of all of the staff, available in database table or spreadsheet form, grouped together by division.  Her assistant runs the sorting algorithm on the "division" field, knowing that the grouping is a result.  Is this single program executing two different algorithms?

While probing our intuitions about algorithms, we have built up a question set.  At first, I hoped to organize it into some kind of hierarchy, but that did not happen; the need faded away.  It remains heterogeneous and unorganized, like traditional brainstorming results.  Here are a few samples.

2.  Does an algorithm have to be digital?  Or symbolic?
8.  Is the algorithm a "natural kind?"
12.  Is the imperative construct compositional?
19.  Is developing algorithms an art or a science?
36.  What did Al-Kwarizmi actually say about algorithms?

The question set is the students' basis for both expository and philosophical essays, now underway.  And, by the way, we're still arguing about whether a recipe is an algorithm.

Wednesday, September 12, 2012

The First Couple of Weeks

The class has started off, with neither a bang nor a fizzle, but with satisfactory activities and solid interest.  Because my students did not sign up to serve as subjects of public discussion, and because the only view that I can relate is that of the instructor, I will forgo describing the class proceedings.

Suffice it to say that I am balancing the technical and the abstract, usually in each class session, by (1) examining and practicing algorithm tracing and representation, with simple sorting, searching, and encoding; and (2) discussing philosophy in general, and posing questions about individual and comparative features of algorithms.  We have read the entry, "Philosophy of Computer Science," in the Stanford Encyclopedia of Philosophy, and we have read Moshe Vardi's letter, mentioned previously, in the Communications of the ACM.  And I am assigning and collecting a steady stream of written work. 
I have taught, in a cursory way, more of the technical matter than I thought would be necessary at the start, such as semantic functions and compositionality, monotonicity, the entity-relationship model, with set theory coming up.  But no student is in danger of mastering those subjects in this class. 

We are also, in this course, testing a new Learning Management System, which brings our high-minded inquiries down to earth for dealing with the intricacies of web interfaces.  And we are discovering that some of the classrooms no longer provide the equipment that I expected.  I'm pleased to say that these mundane details of teaching are offset by the interesting questions and speculations already at play in the class.

Tuesday, July 31, 2012

Materials on the Ontology of Algorithms

One good plan for a course on the ontology of algorithms would be to read the Editor's Letter from Moshe Vardi in the March 2012 issue of the Communications of the  ACM, "What is an Algorithm?" [1] A short up-to-date view from an authoritative source would start us off on the right foot.  Vardi reflects on the significance of his title question and the dearth of answers, and refers to two papers presented at an international congress by Yiannis Moschovakis and Yuri Gurevich.  We could spend a semester mastering the technical material and discussing the competing claims of those two works, deriving their implications, and comparing them with others.

But this is a junior class for newcomers to the fields.  A quick glance back at the course objectives fails to reveal "bafflement" or "intimidation."  It would be counter-productive to throw these students into the research literature of academic computer science.  Instead, we will start our exploration at the level of intuition and move forward into tutored intuition, perhaps approaching the same points across friendlier terrain.  Points raised by Moschovakis and Gurevich include the status of declarative structures as algorithms, for example, and the possibility that heterogeneous types of abstraction might be appropriate.  Nice issues!  All three papers are cited in the course textbook.

I am indeed writing a textbook for this course, which will end up as a modest textbooklet, or course packet.  I want to provide concise materials, encouraging students to contribute to the elaboration of questions as well as answers.  I want to easily reference other elements of the course, such as examples, tables, definitions, and completed exercises.  (The manuscript format is EPUB, using Amaya and Sigil for composition, and I will distribute the text for free to students.)

These written materials, unsurprisingly, are sparse.  Yet an outline emerges, built on a sequence of ontological questions.
  • What is an algorithm, as defined by examples?
  • What distinguishes algorithms from other abstract structures?
  • What makes two algorithms identical or distinguishes one from another?
  • What are the properties that we can attribute to individual algorithms?
I provide several simple algorithms on paper, to start, for close examination.  We will unapologetically use rigorous-enough pseudocode for the expression of algorithms.  We will gloss over implementation details and mathematical formalisms-- unless they arise naturally in some critical context.  We will spend a lot of time articulating descriptions of tasks and their solutions; we will not shrink from mundane or silly analogies if they help to get a concept across.

Such a breezy appeal to informality notwithstanding, this class calls for set theory and other simple discrete mathematics.  (Don't they all?)  The students will need to get comfortable with functions as sets of ordered pairs, and with Turing Machines as tangible abstractions (so to speak) for programs, and with uncomputable functions.  The resulting textbook's outline:

I.  Introduction
  In which we enact algorithms.

II.  The Background
  Definitions
    In which we tackle the definitions of philosophy, computer science, ontology, and algorithm, relying heavily on other people's work.
  Simple Set Theory
    In which we master the basics of finite and infinite sets and subsets, membership, operators, and cardinality.

III.  What Are Some Examples of Algorithms?
  In which we read, trace, and write pseudocode for standard named algorithms, trying to elicit possible characterizations.

IV.  What is the Class of Algorithms?
  In which we compare algorithms with other structures, such as directions, games, and proofs, and attempt to formulate some for simple tasks.

V.  What Makes Algorithms the Same or Different?
  In which we study programs as Turing Machines, as well as relations and functions, seeking insight to determine how many different payroll algorithms exist; not to mention, algorithms for trivial tasks, algorithms for arithmetic, and so forth.

VI.  What Properties do Algorithms Hold?
  In which we attempt to articulate the key properties that apply to all or some algorithms, or figure out why we can't.

Now that the course planning is under control, this blog may languish as I travel and finish preparations, until I get some time to report after the semester starts.


[1]  Moshe Vardi, What is an Algorithm?, Communications of the ACM, March 2012, pg. 5 (55:3) DOI:10.1145/2093548.2093549

Links to the two papers he mentions--
Gurevich:  http://goo.gl/0E7wa
Moschovakis: http://goo.gl/HsQHq

Monday, July 23, 2012

Assignments and Activities on Algorithms

The student background is assumed to be mixed, some more comfortable with philosophy, and some, with computer science.  Assignments should be designed to both pull and push, so to speak.  And, as mentioned in "Pedagogical Goals," they should foster respect for the methods and matters of the other discipline.

Some assignments should be small.  Some should be large.  Some should be machine-gradable.  Some should be peer-gradable.  Some should be collaborative.  Some should require revision.  I intend to assign many short written pieces and many small research tasks.  Often, these will be combined.  Some will be assigned to only one person, who will have the duty of reporting to the class.  The instructor's task, in addition to formulating the assignments themselves, is to coordinate all of the work, and spread it fairly across the student body.

Initial work will focus on defining the concepts concerned-- philosophy, computer science, ontology, and algorithm-- that last, at least tentatively.  Subsequent early activities will exercise our grasp of particular algorithms in order to strengthen our understanding of the general abstract concept.  We will start by running through some simple classic algorithms for searching and sorting.  We will act out some of them with tangible data such as decks of playing cards, sorting the cards into order in different ways, and searching for target values in the deck in different ways. 

Questions that we will consider as we do so include:  How does this algorithm work; how would you explain it in a sentence?  What are the preconditions?  How is the output or solution manifested?  What makes this algorithm unique?  Worthy of a name?  Interesting?  The first few questions are more technical to appeal to the budding computer scientists, and the latter more lyrical, if you will, to appeal to the budding philosophers.  These questions can be turned into short assignments.

We will also watch carefully for steps in which we exercise human judgment or short cuts, and consider whether those can be captured in a program.  To clarify such issues, we will examine common sets of directions such as recipes, licensing procedures, and IRS tax form instructions.  We will consider whether computation is always a component of an algorithm, whether an algorithm can have intermediate input, and whether an algorithm assumes a problem to be solved.  While these preliminary questions lend themselves better to discussion than to individual writing, the writing can be assigned as a product of the discussion.

Short pointed work is effective, in my experience.  I rely on assignments of the fill-in-the-blank and worksheet type, which can serve as homework exercises with clear right and wrong answers [1].  And it doesn't have to be rote.  I can illustrate this in terms of another computer science topic, the Halting Problem, as it might be pitched to different levels of expectation.  A graduate level exercise on the Halting Problem might ask for a proof of its unsolvability and discussion of the implications.  An upper-division undergraduate form of the exercise might present a sketch of the proof and ask for its completion.  A lower-division undergraduate version (which I have used in a multi-disciplinary sophomore course) might supply each of the steps, written out, and ask for them to be arranged in the right order.  These techniques can be applied to explication of algorithms.  For this class, written traces of the more sophisticated sorting and searching algorithms might fill the bill, especially if they also require comments on the appropriate context of application.  If this doesn't quite work, subsequent problem sets can be pitched up or down.

Students will also perform Internet research to find algorithms in pseudocode form, and will send messages of acknowledgement to those who provide such materials.  We will build up expertise, and refine definitions, as we go along, so I will also assign students to record notes in class meetings, and post them in a repository for future reference.

For assignments directed to a higher level of thinking, I plan a project that probes how strictly algorithms are embedded in daily human or natural life, as mentioned in the previous post, "Theme: The Ontology of Algorithms."  This will require students to research, understand, and apply an algorithm in a familiar context, perhaps with some fictional or creative component, and will contribute to the investigation of some of the greater questions, such as whether nature executes algorithms.

We won't neglect assignments at the top levels of Bloom's taxonomy.  The students will (perhaps later) consider a couple of wild cards that might make juicy essay topics: 
(1) What would a non-analytic account of algorithms look like; how would this come out in the tradition of Continental philosophy? 
(2) Are algorithms created or discovered?
Question 2 seems a good candidate for an essay during the first half of the course that is later revised near the end, not with a view to correction of the answer, but with a view to more sophisticated treatment.

[1]  Mark Guzdial, BLOG@CACM, February 20, 2012, "Why Don't we use Worksheets in Computer Science Education?", http://cacm.acm.org/blogs/blog-cacm/146183-why-dont-we-use-worksheets-in-computer-science-education/fulltext