Module 3 - Algorithmic Research
Tuesday, 25 October 2011 13:59
Bomadeno
This was a pair of guest lectures by Pekka Kilpeläinen, also from The University of Eastern Finland. Pekka presented two approaches to algorithmic research, the first analytic-deductive methods, and the second experimental algorithmics. This article will discuss both techniques and discuss the differences between them. The coverage of the analytic-deductive approach will be short, as it was far better covered in our other course, Design and Analysis of Algorithms, which, if you're lucky I will upload my course diary for sometime.
Analytic-deductive algorithmics is the classic style of algorithm analysis taught in many universities as part of an "algorithm analysis course". After developing a pseudocode algorithm, the researcher proceeds to do analysis, calculating the theoretical space and time complexity, comparing it to other algorithms, and discussing only vaguely any probable implementation details. It generally doesn't cover (or at least not in-depth) details of implementation, and constant factors of complexity that maybe important in reality are often hidden by the asymptotic notation. Mechanical considerations such as caching, parallel architectures, machine specific instructions, and so on, are also overlooked by this methodology.
It should be clear from this research methodology that it gives a very theoretical outlook on algorithms. We get to learn whether an algorithm is practical, we get to know theoretical run times for randomized algorithms and theoretical worst case approximation values for approximation algorithms, and we get to see how the complexity will scale with input size. While this is clearly important, it does not give the full picture. Ultimately, the algorithm must be run on real machines to be of any practical use, and so it must be implemented. Experimental algorithmics should be able to offer the answer to many of these questions - what is a real acceptable input size, how big a problem can we currently solve, hardware exploits, actual results from approximation and randomized algorithms, and so on.
Experimental algorithmics is a key research technique of computer science. It used to be the de facto standard for algorithm research, until asymptotic analysis was introduced. After falling into a lull, experimental algorithmics is starting to be used more once again. The overview we were given was based on the paper by David S Johnson, which seems to be a good critical review of the methodology. Experimental algorithmics is most often used either when an algorithm is used in an application, or when one algorithm implementation is compared to another, or to understand the strengths, weaknesses and operation of an algorithm in the flesh, or to create average case behaviour metrics for complex algorithms that resist probabilistic analysis. Sometimes, it is used for many of these cases at once. To avoid the field falling into its original pitfalls (difficult to generalise, poor scientific method, etc) Johnson's paper attempts to concisely summarise the things to avoid and aim for.
Following is the summary list Johnson provides for those preparing to do experimental algorithmics research. If you are planning to do some yourself, I urge you to read the original document [PDF], as it is well written and clearly presented. Now the summary of requirements (as much for my future reference as anything else):
- Perform newsworthy experiments
- Tie your paper to literature
- Use instance testbeds that can support general conclusions
- Use efficient and effective experiment design
- Use reasonably efficient implementations
- Ensure reproducability
- Ensure comparability
- Report the full story
- Draw well-justified conclusions and look for explanations
- Present data in a clear and informative way
As I said, if you are going to do experimental algorithmics, read the paper! This summary doesn't do justice to the full text, which has far more fine-grained advice that these bullet points fail to describe.
Last Updated on Wednesday, 26 October 2011 20:15
Module 2 - Quantitative Research
Tuesday, 18 October 2011 06:00
Bomadeno
Why would you want to use quantitative research? While this is the first question to consider, its answer comes best from knowing how quantitative research works, and the strengths and weaknesses of using it. The 'main idea' of quantitative research is in the name - we collect some measured quantities from somewhere, analyse them somehow, then evaluate and make some conclusions. Each of these 'some' words is a decision we have to make. What will we measure, and how? Where, when, maybe who will we collect from? How will we analyse the data? What can we conclude from this? Those of you paying attention might have noticed that italic 'evaluate' that is not a 'some' word. The evaluation asks all these questions and then why did you do each 'something', what was good, what was bad and how could it be improved. All these parts of the research design can (and should) be developed iteratively, getting refined as the research progresses.
First we need to decide on the research question.This is not easy, but it is very important. The question guides the research, it is the motivation and answering it is the main (or only) goal of the research. With a well-defined, well constrained question, finding and analysing an answer to that question is certainly easier. While questions are relatively easy to come by, answerable questions (especially questions that can be answered concisely) are hard to construct. It is wise to start from a vague idea and iteratively refine it down to a precise question, in between iterations extending to literature reviews, doing prototypes, or whatever is most relevant.
Closely linked to developing the research question is developing the experiment's hypotheses. As a minimum our experiment needs two hypotheses, the null hypothesis and the alternative hypothesis. The null hypothesis says 'the expected thing didn't happen' and the alternative hypothesis says 'the expected thing did happen'. The reason for them being in this order is most likely due to researcher's avid interest in pessimism (the higher value of disproving a theory may also be related!). There are two main categories of hypothesis - the one tailed and the two tailed. The one tailed hypothesis states either 'the value will increase' or 'the value will decrease' - the direction of change is specified. The two tailed hypothesis states 'the value will change' but leaves the direction of change to be determined by the experiment. We can do a little more thorough analysis of one tailed hypotheses, but their inflexibility is a downside.
Now we know much better what question we are trying to answer, we can continue the research plan. First up, we should know what to measure, and how to measure it. What to measure may already be known from writing the research question, but a careful decision must also be made on how to measure it. If the things to measure are not obvious from the research question, we need to define them (and possibly refine the question). The definition should be clear enough for another researcher to repeat the measurements.
The choice of measurement technique impacts on the later stages of research such as what analysis we can apply, and the validity of our experiment. The four possible levels of measurement are, in order of increasing precision and power; nominal, ordinal, interval and ratio scales. Nominal scales simply classify results without any order. Ordinal results have order but have no units, and two consecutive elements in an ordinal scale do not have a known distance between them. An interval scale measures in units, so we can make additive and subtractive comparisons - 30°C is 5°C more than 25°C. This is an improvement, but we lack the power to express multiplicative comparisons sensibly. With a ratio scale, such as height or weight, we can also make multiplicative comparisons such as "20kg is 10 times more heavy than 2kg".
Making the correct choice of measurement scale is important. Some things simply can't be measured on anything more than an ordinal scale, such as human feelings. You can say "I am happier about this than I am about that", but you cannot say how much happier precisely. Unfortunately these techniques are also less amenable to analysis - this has the potential to weaken conclusions and findings. One must also be careful not to apply analysis techniques where it is inappropriate, as they will be meaningless. When designing an experiment, you want to pick the most powerful measurement technique, without using something inappropriate or inapplicable.
When we know what we want to measure, we need to decide how we will collect it, or 'how we actually do the measurement'. This is different to 'how we measure it'. As an analogy, how we measure it is 'with centimetres', and how we perform the measurement is 'straighten the string and place it against a ruler'. We can collect data either in the laboratory, or in the 'real world'. In the laboratory we have complete control over everything (in theory). While lab methods give us control, field methods give us 'applicability' - proof that our theory works outside of the lab. At all times while taking measurements we should aim for comparability, randomization, replicability, blocking, orthogonality and factorial experiments.
When designing experiments in either lab or real world situations there are many pitfalls to be avoided. These include human elements such as bias (both participant and researcher) and reactive effects such as the Hawthorne effect; as well as mechanical issues such as poorly calibrated machinery or anomalies. These pitfalls can all be overcome (to a degree) with good experiment design and they should all be considered and evaluated in the final research paper.
The three main ways to collect field data are field studies, field tests and surveys. Field studies examine without interaction, while field tests change independent variables and look for the expected dependent variable's reaction.
Surveys are a moderately powerful, but most importantly are very easy and cheap to set up, especially with widespread internet adoption. (though this has some drawbacks, as it guarantees the sample of respondents all have internet access! An internet survey "do you use the internet" would obviously be silly!). A good survey must be carefully written, hastily written surveys yield weak data and we know that weak data means limited analysis and weak conclusions!
A number of problems need to be debated whilst developing a survey. First and foremost, related strongly to developing the research question, our survey needs a goal. Typical goals are either descriptive, exploratory or explanatory. Next up, we need to choose our sample. The sample is usually related to what we want to find out, and should be big enough without wasting money. As the sample size grows, the benefit of increasing it grows at a lower rate, so a cost-analysis must be made. the sample, and the method of obtaining the sample must be carefully chosen to reflect the population under examination. Surveys may be performed in person, over the telephone, through the internet, or any other sensible media. The richest information comes from face to face interviews, but the cost is appropriately higher. Once again we have to make an informed decision.
Start the survey with an introduction, explaining the purpose, along with any 'legalities' such as debriefing, the right to withdraw, etc. (We were told to put instruction on the first page, but I believe if instruction are necessary, the survey can be improved.) When developing the questions in a survey, once again we must consider them carefully. (notice an important ongoing theme: think about the research critically and with an open mind (especially to criticism) at all times) Take care to make sure questions are clearly either open-ended, closed, or scales and that the answer space matches this. At all times, word the questions simply and appropriately for your audience, do not use complex technical terms without good reason. Make sure the option to "not answer" or "not care" (or whatever is appropriate) is present. For example, "How often do you shop at K-Citymarket in Joensuu? Monthly[] Weekly[] Daily[]" is not a good set of answers, and should include "Never[]". When using Likert scales, be careful that the answers make sense linguistically. A question such as "Do you like K-Citymarket?" cannot be sensibly answered with "Agree-Disagree" options, and should use "Yes-no" options. When asking, ask impartially - be careful not to use positive or negative words. The previous question would be better asked "how do you feel about K-Citymarket" - the word 'like' mayincline the participant one way or another.
It is also important to consider the order and number of questions. There is some psychology involved here, some may even consider it manipulative, but we want candidates to start our survey, and finish it too! Do not make the survey too long, and include easier questions first to get an "investment" from the participant. Longer questions later are more likely to be tolerated as the candidate will not want to give up on a survey they have already invested in. Such are the foibles of humans.
Before deploying to an 'expensive' number of candidates, or potentially exposing candidates that can only be used once to a poor survey, pre test the survey on a small sample. We as researchers are human and we will make mistakes. Using peers to check your surveys will improve both you and the peer's ability in the field. If the survey gets poor review from a peer, rework it and put it in for evaluation again iteratively, until both of you are happy with the work.
After developing a survey, it's time to deploy it. Don't get sloppy now and waste your hard work - test the practical deployment rigorously before exposing it to candidates. After collecting your sample(s), the data should be ready for analysis and evaluation (see the next page). You may find faults even during analysis and evaluation, if so, and if the budget allows, you can revise the survey even now and run it again. Upon satisfactory completion, you are ready to share your work with peers - which i will cover in the next article.
Once we have our results - a set of measurements of things - we can analyse them. Statistics, both descriptive and inferential, give the way to analyse our results. This very broad and well-developed field was only touched on in the course, but there were a two key points: the basic classes of statistics; and how to actually do the statistics in practice (or 'in software', if you like). The two classes are good for, first, summarising large amounts of data succinctly and second, determining if there is a link between independent and dependent variables.
Statistics also give us ways to quantise the strength of our findings. Rather than just stating "There is a correlation", we can say "there is a 67% correlation". This is very good, because if our measurements stand up, then it lends our research a lot of validity.
Descriptive statistics are used on one variable, such as a sample of heights, weights or times. It can calculate central tendency, dispersion, and distribution. Each of these has various practical methods for calculation, which can be applied to various data measurements. They cannot all be applied to all measurements as mentioned above - you cannot find a meaningful mean of human feelings.
Inferential statistics are used to test hypotheses. There are two classes of inferential statistics, parametric and non parametric. Parametric tests are more powerful, but we must be aware of the constraint - data must come from specific probability distributions. Non parametric tests place no requirement on distribution but they also lack the power of parametric tests.
The lesson on statistics software came mainly from our exercises for this module. The exercise had us investigate Excel, R and SPSS in their applicability to research statistics. The results were surprising to me, as I had no idea Excel was so poor for statistics. Importantly, we learned about R, which is a free, powerful industry standard statistics tool. SPSS is another industry standard tool but is proprietary (and expensive) software.
A note on applicability to computer science. Quantitative techniques are not always applicable to computer science - while quantitative techniques can sometimes be used to great effect, there are time when it is not suitable. Especially when dealing with the 'human' terrain of user experience, quantitative methods lack the ability to describe the rich feelings and thoughts expressed when in these fields. Here we turn to research's other major technique - qualitative research. I will cover this in a future article.
Last Updated on Wednesday, 02 November 2011 10:54
|
Module 2 - Research Papers (chmod 777)
Thursday, 20 October 2011 18:13
Bomadeno
There's a silly geeky joke in the title of this article. chmod is the Unix command for changing a file's permissions, and '777' means 'read, write and execute for all'. I'm using 'execute' as a synonym for thinking, and seeing as we are able to do all three actions - read, write and think, we should make the most of it. Neither reading nor writing research papers is a passive activity, and both need thought. Writing and 'analysis while reading papers' always need deep consideration. The reading process will become faster as you get used to the style and layout of papers. Once you get some experience, you can cut through many papers by rapid recognition of either its "suckiness" (for want of a better word) or irrelevance.
It is vital that someone who plans to publish research is well read. (as I understand it, grounded research kind of requires a lack of knowledge in the field, but you should still read other papers that have performed grounded research - ignorance of the field does not mean ignorance of the technique and is a poor excuse) Reading a wide papers - maybe in place of a morning newspaper - will get you used to the style and techniques accepted by the community. It will engage, challenge, and potentially inspire you.
The technique of 'reading' can be taught. I don't think I am capable of teaching it, but there are things you must realise when reading - you should build these up as you go along, and maybe one day share them with us.
For example of a reading technique that can be taught: for a long time I thought I was very stupid - when I encountered a mathematical formula, it took me regularly took me hours to decipher. This is, in fact, perfectly normal. That one formula may express entire paper in a single line, and understanding can take some time. When first evaluating a paper, skip the formulae, and get an understanding of the paper's theme. If its useful enough to you, return to the formula and take time to understand it, and what it does - be patient. It likely took the original researcher weeks, months or even years to formulate, and here you are, stressing over taking a day to understand it.
Another valuable tip while reading papers is what our lectures called 'meta cognition'. In simple terms, think about what you are reading both as fact, and with a questioning mind. As you read, be cynical - keep asking, why do this, how did you prevent this, what about this, and so on. By constantly asking these questions you should form a good opinion of the research, its findings and validity. It's no good a researcher knowing they did it right, they need to tell everyone they did it right - the paper is more like a photo of the research than a window on it. If it isn't visible in the photo no one can see it, and unlike a window you can't move closer or peer around the frame. Remember this or your paper will likely get rejected (or accepted but archived for eternity). This leads us on to the meat of 'writing papers'.
Bear in mind, that when people read your research they will do so in exactly the same way. Therefore, when you write a paper, you will need to answer all the questions you would ask of it if you were a reader. By asking them regularly of papers you read, they should become natural, and answering them should become an instinctive priority in your mind when writing.
Before writing, you need to know a bit about what you will be writing, which means knowing a bit about what you will be researching. Use brainstorms, discuss with colleagues, decide on suitable publications (and know their audiences), make lists, mind maps, or whatever floats your mental boat. Organise your random ideas a little, like combing your hair so it's easier to run your hand through. Try combing them a different way and see if it flows better. use highlighters, bold text and italics to give attention to important points so you don't forget them.
When it comes to writing style, it is sometimes useful to use jargon. It can provide clarity and precision (eg 'flux' when discussing light bulb advancement), as well as being succinct ('WYSIWYG', when defined once, will save a lot of space). A pet hate of mine - unnecessary jargon. If you can say color instead of chromaticity, say color. This will make your paper more accessible and more pleasant, and if everyone does it, reading papers should become more pleasant for you too. Otherwise, your style should match roughly with your publishing 'stream', so that people accept it willingly. That said, you're an individual and I think that personal style is often more pleasant to read, so don't go so far as to make it unnatural for you. Try sentence short and avoid unnecessary complexity. Write in American English unless you know you need to do otherwise.
Writing structure is a lot less flexible. You must match carefully to your publication's standards, and if you are submitting for publication to multiple locations, editing the formatting in a 'WYSIWYG editor' will be unnecessarily difficult. Use of proper tools such as LaTeX (the Miktex package being a great way to get started) will free you from worrying about formatting structure and style, and allow you to use predefined publishing templates when it comes to making it pretty. With the 'look' not important, and a proper 'WYWIWYG' editor in hand, you can concentrate on writing the sections you need with ease. Using LaTeX properly (learn it, really!) will allow you to easily reorder and rename section headings later if necessary. Write each of the section headings first, then flesh it out bit by bit. Don't write the entire document after the research, iteratively write and improve it throughout the process. Be sure to differentiate sudden ideas and notes from your work, in LaTeX you can use comments and in Word you can use markup and notes. You don't want to accidentally leave a note "turn the oven off" in your paper! (I have suffered such embarrassments.)
Despite differences in section names, the contents of a paper are more or less consistent across publishers:
- Title & authors - the title is what people see. Draw them in, and don't lie. Explain everything in as few words as possible.
- Abstract - a short summary of everything below. It will be displayed separately from the paper so it must stand alone with the title, and not contain any references (internal or external) or acronyms. It must not contain anything not contained within the body of the paper. In the 'window-photo analogy', the abstract is an embedded thumbnail of the photo, and you must choose what appears in it. An interested reader can then scan through a gallery of thumbnails, find your awesome preview, and open the full resolution photo.
- Introduction/Motivation - why are you doing this research? What has already been done here, and what are the gaps? (be brief, literature review is the next section) Why is what you are doing important? (if it isn't important... why are you doing it?) What did you do, again, briefly? What is yet to come in this paper?
- Literature review - what other research is closely related, and how? What are the existing theories and key phenomena? If it's a problem, what existing solutions are there? Also give 'background reading' so that your reader can scrub up on their Blinn-Phong and their BRDF before you plunge into your refinement of specular modelling.
- Methodology - what did you do, how did you do it? Be sure to describe your sampling, any equipment you used, what you measured and how you measured it, as well as any oddities in your analysis process.
- Results - what were the results? do not put a huge table of all results in here - for quantitative research use appropriate statistical summaries, and for qualitative research any relevant clippings or examples. Use tables and graphs well (read Tufte's 'The Visual Display of Quantitative Information' for advice and inspiration here). Be sure to refer to every figure in the text, but also be sure that both the figures can 'stand alone'.
- Analysis - this is where you do a critical analysis of the results. Highlight the important bits, describe your conclusions (with reasoning), compare everything with your background literature and related work, discuss any anomalies, present any practical implications. Don't forget to answer 'is my work valid', and give reasons why (or why not).
- Conclusions - what did you do, what did you find, what can other people do?
- Acknowledgements - optional. Useful people - professors, proof readers, lab technicians, participants and that sort of thing.
- References - if you have no references, who are you? Sadly, the answer is 'nobody'. 'On the shoulders' of giants and all that. Ensure references are in the correct format for the publication (BibTeX for LaTeX will help you here), and that they are correct and enough to find the original work. Reference management tools like Endnote, Zotero or Mendeley will make life easier for you.
So, now you have written a paper. Thinking of sending it for review right away? Don't. Sleep on it and read it yourself the next day, have a beer and read it while you're tipsy. Show it to your mother, your flatmate and a language student. Rewrite, restructure, reword. Sleep. Read it again. Use a good spellchecker and a good style checker (I like 'After the deadline' for readability). Once it's stabilised and you aren't making many changes, you're ready to actually send it to the publisher for review. (note, if there is no review, you're probably submitting to an unreputable place, and your research probably won't be read by people who know how to filter their reading.) The review board are going to write back and they will probably be pretty mean even if they accept it. (so called 'conditional acceptance') Even if they accept it, it might be that they can see the promise and encourage you to revise and reapply. Don't be disheartened by their criticism, think of Simon Cowell and take their feedback as constructive. Make sure you note any changes to match their requirements before sending off another draft. Eventually you should be accepted, then it's just a wait for the fame, glory and riches.
I jest. You're really waiting for the critical, hard-nosed chorus of other people. They're probably just jealous, but read what they say anyway, maybe they'll give you some ideas and things to think about. Next year, read your own paper again and learn from any mistakes you find. Try not to hate the young, naive arrogant you too much - you've learned a lot in the last year.
Last Updated on Thursday, 20 October 2011 20:21
Module One - Introduction
Saturday, 15 October 2011 17:06
Bomadeno
The topics of this module were "Defining Art, Science and Engineering" (naturally focusing on the relation to 'computer science'), "Research Design" at a high level, and then an overview of some technical terms encountered in research. The purpose was to prepare us for the remainder of the course, a kind of framework into which everything else fitted.
The first topic, defining art, science and engineering was less 'defining' and more 'attempting to form some rules that roughly split. There is a lot of overlap between all three areas, and there are no solid definitions. Also, one may set off with a clear artistic idea, develop an engineering solution, and then find a deep scientific finding (perhaps fractals are an example of this - what do you think?). Despite this vagueness, it is possible to make certain generalisations. Science is a more abstract work, and is used across disciplines, with many standards and techniques which are used in the pursuit of new knowledge of the world. Science may not produce useful artifacts in its progress. Engineering is usually in the form of 'problem and solution', and is most often about solving practical problems. It typically produces working solutions to real problems. Art goes beyond finding a simple solution and tries to find beautiful or elegant solutions - or indeed, just beautiful things - or indeed ugly things!
As a side note, the module focused on science and engineering and didn't pay a lot of attention to the art aspect in computer science, despite various major figures in computer science having discussed it. The idea is a very interesting one, and one I want to read more about. My instinct says that there is a degree of art involved in developing good algorithms and especially in developing good implementations.
The main reason for this discussion was the ongoing debate 'what is computer science?'. Is it an engineering or a scientific discipline? My opinion is that it is both, and the fusion of application and theory is beneficial, leading to a rapid pace of development.
Next up was the high level view of research design. The model presented was the Jenkin's model, familiar to anyone who has studied the waterfall model in software engineering. This general model for research always starts with an idea, which is then progressed through six phases, followed by publication. The six phases are literature research, followed by definition of the research problem, a choice of research strategy, experiment design, execution of the plan ('data collection'), then data analysis and finally a critical evaluation. This model applies to all modes of research, whether quantitive or qualitative. Each of these stages should be pretty self-explanatory, and this approach is something I am quite used to from software engineering work, though with more iteration. (I believe this refinement works well here too though)
Module one turned out to be quite interesting (thinking about science, engineering and art), but presented fairly little in the way of new material for me. It was disappointing that art was totally overlooked in relation to computer science, as the idea is at the very least intriguing.
Last Updated on Tuesday, 01 November 2011 19:43
|
