Deniz Yuret's Homepage

Gamma distribution

2011-10-29T14:49:00.000+03:00

The Gamma distribution is often used as a prior for positive random variables just like the Gaussian distribution for real valued random variables. The purpose of this post is to build some intuition about how the two parameters, the shape parameter "a" and the scale parameter "b", effect the behavior of a Gamma random variable. In particular we will show that for vague Gamma parameters (a<<1) the distribution almost acts like an upper bound on the random variable.

Here is the Gamma PDF:

$f(x) = \frac{1}{\Gamma(a) b} (\frac{x}{b})^{a-1} e^{-x/b} \;\; x\geq 0; a , b>0$

The mean is ab and the variance is ab². When a=1 it is equivalent to the exponential distribution. In fact when a is an integer, it is equivalent to the sum of (a) independent exponentially distributed random variables each of which has a mean of (b). It is shaped like the exponential distribution with a spike at 0 for a<1, but has a mode at (a-1)b for a>1 (see the Wikipedia article).

MacKay suggests representing the positive real variable x in terms of its logarithm z=ln x (ITILA, pp. 314). This will give us a better idea about the order of magnitude of typical x in terms of a and b. The distribution in terms of z is:

$f(z) = \frac{1}{\Gamma(a)} (\frac{x}{b})^a e^{-x/b} \;\; z \in \Re; x=e^z; a, b>0$

We can get an idea about the shape of f(z) by looking at its first two derivatives with respect to z:

$f'(z) = f(z) (a-\frac{x}{b})$

$f''(z) = f(z) (a^2 - (2a+1)\frac{x}{b} + (\frac{x}{b})^2)$

The graph above shows f(z) and its two derivatives for a=1/10 and b=10. The first derivative tells us that f(z) has a single mode at x=ab. Note that x=ab is the mean of f(x) but only the mode (not the mean) of f(z). The curve raises slowly on the left of the mode and falls sharply on the right. The second derivative has two roots that give us the values with the minimum and the maximum slope:

$x = ab + \frac{b}{2} \pm \frac{b}{2} \sqrt{1+4a}$.

Now we are going to look at the limit where a<<1, typically used as a vague prior. The height of the mode at x=ab is a^ae^-a/Γ(a). Γ(a) is well approximated by 1/a for small a, a^a and e^-a both go to 1, so f(z) ≈ a at the mode.

Next, let's look at the right side (x>ab) where f(z) seems to fall sharply. According to the roots of the second derivative given above, the minimum slope occurs at around x=b (if we ignore the terms with a<<1). The value of f(z) when x=b is 1/(e Γ(a)). Γ(a) is well approximated by 1/a for small a, so this value is approximately a/e. The slope at x=b is approximately -a/e and if we fit a line at that point the line would cross 0 at x=eb. Thus for small a, the probability can be considered negligible for x>eb.

Next, let's look at the left side (x < ab) where f(z) appears more flat. The maximum slope occurs around x=a²b (if we approximate √ 1+4a with 1+2a-2a²). The slope at x=a²b is approximately a² which gives a flat shape for x<ab when a<<1.

In summary, when used with a<<1, f(z) rises slowly for x<ab (with approximate slope a²) and falls sharply for x>ab (with approximate slope -a/e). You are unlikely to see x values larger than eb from such a distribution, but you may see values much smaller than the mean ab. Thus a vague Gamma prior is practically putting an upper bound on your positive value. The figure below shows how the f(z) distribution starts looking like a step function as the shape parameter approaches 0 (b=1/a and the peak heights have been matched for comparison).

I should also note that in the limit where a→0 and ab=1, we get an improper prior where f(z) becomes flat and the Gamma distribution becomes indifferent to the order of magnitude of the random variable. However it flattens a lot faster on the left than on the right.

Ergun Biçici, Ph.D. 2011

2011-08-16T10:52:00.003+03:00

The Regression Model of Machine Translation
Ergun Biçici. Ph.D. Dissertation. Koç University, Department of Computer Engineering. August, 2011. (PDF, Presentation)

Abstract:
Machine translation is the task of automatically finding the translation of a source sentence in the target language. Statistical machine translation (SMT) use parallel corpora or bilingual paired corpora that are known to be translations of each other to find a likely translation for a given source sentence based on the observed translations. The task of machine translation can be seen as an instance of estimating the functions that map strings to strings.

Regression based machine translation (RegMT) approach provides a learning framework for machine translation, separating learning models for training, training instance selection, feature representation, and decoding. We use the transductive learning framework for making the RegMT approach computationally more scalable and consider the model building step independently for each test sentence. We develop training instance selection algorithms that not only make RegMT computationally more scalable but also improve the performance of standard SMT systems. We develop better training instance selection techniques than previous work from given parallel training sentences for achieving more accurate RegMT models using less training instances.

We introduce L_1 regularized regression as a better model than L_2 regularized regression for statistical machine translation. Our results demonstrate that sparse regression models are better than L_2 regularized regression for statistical machine translation in predicting target features, estimating word alignments, creating phrase tables, and generating translation outputs. We develop good evaluation techniques for measuring the performance of the RegMT model and the quality of the translations. We use F_1 measure, which performs good when evaluating translations into English according to human judgments. F_1 allows us to evaluate the performance of the RegMT models using the target feature prediction vectors or the coefficients matrices learned or a given SMT model using its phrase table without performing the decoding step, which can be computationally expensive.

Decoding is dependent on the representation of the training set and the features used. We use graph decoding on the prediction vectors represented in n-gram or word sequence counts space found in the training set. We also decode using Moses after transforming the learned weight matrix representing the mappings between the source and target features to a phrase table that can be used by Moses during decoding. We demonstrate that sparse L_1 regularized regression performs better than L_2 regularized regression in the German-English translation task and in the Spanish-English translation task when using small sized training sets. Graph based decoding can provide an alternative to phrase-based decoding in translation domains having low vocabulary.

RegMT System for Machine Translation, System Combination, and Evaluation

2011-07-30T23:09:00.001+03:00

Ergun Bicici; Deniz Yuret. Proceedings of the Sixth Workshop on Statistical Machine Translation. pp. 323-329. Edinburgh, Scotland. July, 2011. (PDF, BIB, Proceedings, Poster)

Abstract: We present the results we obtain using our RegMT system, which uses transductive regression techniques to learn mappings between source and target features of given parallel corpora and use these mappings to generate machine translation outputs. Our training instance selection methods perform feature decay for proper selection of training instances, which plays an important role to learn correct feature mappings. RegMT uses L2 regularized regression as well as L1 regularized regression for sparse regression estimation of target features. We present translation results using our training instance selection methods, translation results using graph decoding, system combination results with RegMT, and performance evaluation with the
F1 measure over target features as a metric for evaluating translation quality.

Instance Selection for Machine Translation using Feature Decay Algorithms

2011-07-30T22:58:00.021+03:00

Ergun Bicici; Deniz Yuret. Proceedings of the Sixth Workshop on Statistical Machine Translation. pp. 272-283. Edinburgh, Scotland. July, 2011. (PDF, BIB, Proceedings, Presentation)

Abstract: We present an empirical study of instance selection techniques for machine translation. In an active learning setting, instance selection minimizes the human effort by identifying the most informative sentences for translation. In a transductive learning setting, selection of training instances relevant to the test set improves the final translation quality. After reviewing the state of the art in the field, we generalize the main ideas in a class of instance selection algorithms that use feature decay. Feature decay algorithms increase diversity of the training set by devaluing features that are already included. We show that the feature decay rate has a very strong effect on the final translation quality whereas the initial feature values, inclusion of higher order features, or sentence length normalizations do not. We evaluate the best instance selection methods using a standard Moses baseline using the whole 1.6 million sentence English-German section of the Europarl corpus. We show that selecting the best 3000 training sentences for a specific test sentence is sufficient to obtain a score within 1 BLEU of the baseline, using 5% of the training data is sufficient to exceed the baseline, and a ~ 2 BLEU improvement over the baseline is possible by optimally selected subset of the training data. In out-of-domain translation, we are able to reduce the training set size to about 7% and achieve a similar performance with the baseline.

ACL 2011 Tutorials

2011-06-21T22:04:00.002+03:00

Here are some notes from the ACL tutorials:

Formal and Empirical Grammatical Inference
Jeffrey Heinz, Colin de la Higuera and Menno van Zaanen

Jeffrey and Colin motivated and presented the main results for formal grammatical inference. Even though many theoretical results are negative, learning is usually possible by restricting the model class (to a well defined subset used by natural languages) or assuming a non-distribution-free setting. Colin's book was recommended as a good introduction to the theory. It would be interesting to see if Turkish morphotactics or morphophonemics fall into one of the easy-to-learn model subclasses. You can download the slides.

Rich Prior Knowledge in Learning for Natural Language Processing
Gregory Druck, Kuzman Ganchev, Joao Graca

There is a recent trend for encoding prior knowledge in learning problems not in the prior distributions but later in the learning process. The prior knowledge usually comes in the form of feature-class expectations and guiding the model toward the correct expectations is only possible after considering the input. Posterior regularization, constraint driven learning, and generalized expectation criteria seem to be related implementations of this idea. You can download the slides.

Dual Decomposition for Natural Language Processing
Michael Collins and Alexander M Rush

I did not attend this one but here are the slides.

Semantic Structures by Ray Jackendoff

2011-05-23T00:26:00.006+03:00

Jackendoff divides the study of the language faculty into three components: phonological, syntactic, and conceptual. In speech recognition a model that tells us what word sequences are likely is essential to recognition accuracy, because the acoustic information is often ambiguous (e.g. "She kissed this guy." vs. "She kissed the sky."). Stated in Jackendoff's terms, a probabilistic model of the syntactic component is helpful in disambiguating what is going on in the phonological component. Similarly I think a model of what is likely in the conceptual component is essential to resolving ambiguities in the syntactic component. If "what is likely to be said" is essential in interpreting "what is heard", then "what is likely to be meant" is similarly essential in interpreting "what is said".

Unfortunately we do not have good conceptual models yet, so computational linguists still try to make do with error prone hand tagging and shallow machine learning to disambiguate senses, references, and relations.

On a side note, each component in Jackendoff's work is modeled after the generative paradigm which, for the syntactic component, is described as follows:

Speakers can understand and create an indefinite number of sentences they have never heard before.
Therefore the repertoire of syntactic structures cannot be characterized as a finite list of sentences.
Nor can it be characterized as an infinite list of possible sentences because we have finite brains.
Thus it MUST be mentally encoded in terms of a finite set of primitives and a finite set of principles of combination that collectively generate the class of possible sentences.

Am I the only one befuddled by this argument? Primitives plus means of combination is certainly one way to create infinity using finite means, but why assume it is the only way? Dynamic systems, random processes, who knows what else can lead to infinite possible outcomes from a finite initial endowment. Why just present two strawmen, finite and infinite lists, as the only alternatives to discrete primitives and combination? Why after a couple of paragraphs further narrow the description to "the argument from creativity to the NECESSITY for principles or rules in syntactic knowledge"? Discrete primitives with finite and definite constraints and rules of combination is one way to build a representational system, unlikely to be the correct way for all three components of language, and certainly not the only way.

See also: Plausibility vs. Inference.

The Noisy Channel Model for Unsupervised Word Sense Disambiguation

2011-05-11T10:44:00.004+03:00

Seminar presentation at ITU on our CL paper.

A tutorial on language modeling with SRILM

2011-04-11T16:15:00.000+03:00

From Eternity to Here by Sean Carroll

2011-03-24T16:43:00.018+02:00

Why is the future different than the past? The fundamental rules of physics seem as symmetric in time as they are for different directions of space, yet you can't unscramble an egg and you can't remember the future. The answer seems to lie in the concept of entropy, which tends to increase over time in a closed system unlike energy and momentum which stay constant. Yet, entropy is one of these concepts that lead to quite a bit of confusion, sort of like (and sometimes for the same reasons as) probability. Sean Carrol's wonderful book tackles the mysteries of entropy and arrow of time. Here are some entropy puzzles and some further reading:

Entropy puzzles:

If you find yourself in a universe with low entropy it is as likely to have come from a higher entropy state as it is to evolve into a higher entropy state. So how do you know you are not a Boltzmann brain?
Take a box with a partition in it, with gas A on one side, gas B on the other side, and both gases are at the same temperature and pressure. Remove the partition. If gas A and B are different gases, there is an entropy that arises due to the mixing. If the gases are the same, no additional entropy is calculated. What if you thought they were the same gas and years later it was discovered that they happened to be two different isotopes? (See Gibbs paradox and E.T. Jaynes' paper). More generally this microstate / macrostate business seems completely user defined and arbitrary, so how can it have real physical effects?
In a reversible system there must be just as many paths that decrease the entropy as that increase the entropy. Why don't we observe as many of the first type as the second?
A gas squeezed in the corner of a room will tend to spread thereby increase its disorder and entropy. If we add an attractive force like gravity matter seems to clump together rather than spread out. How does clumping together increase entropy?
A rotting plant turns into dust and gas which increases disorder and entropy. A seed turns a bunch of gas and dust into a full grown tree which seems to decrease entropy. This can only happen because the seed is not a closed system and is using the energy from the sun and ends up increasing the overall entropy of the universe at the end. When, how, and why does this type of thing happen?

Further reading:

From Eternity to Here: Sean Carroll's book that inspired this post.
Labyrinth of Time: Michael Lockwood's book on the arrow of time with a bit more philosophy and a bit less black hole physics.
Time and Chance: David Z. Albert's book gives one of the clearest discussions of thermodynamics (both classical and statistical) and its relation to the arrow of time.
Good and Real: Gary L. Drescher's book that tackles not only the arrow of time, but quantum indeterminacy, consciousness, free will, and ethics. This is one of my favorite books which inspired a few earlier posts.
E. T. Jaynes has a number of articles that clarify some of the mysteries. See also these links.
Permutation City: One of my favorite sci-fi novels by Greg Egan explores the nature of time, simulation and reality. Maybe instants are not ordered in time at all, the state of our short term memory seems to give this impression.
Max Tegmark at MIT came up with the Mathematical universe hypothesis which is reminiscent of the Dust theory that underlies Permutation City. See also Hans Moravec's essay.

Bologna Translation Service

2011-03-17T13:55:00.000+02:00

Plausibility vs. Inference

2011-01-03T09:39:00.004+02:00

Here are two examples of common sense judgement:

(1) I saw the Statue of Liberty flying over New York. => I was flying over New York.
(2) I gave the book to Mary. => Mary has the book.

The first one involves syntactic disambiguation. Either the subject or the object could be doing the flying (consider "I saw the airplane flying over New York.") Our "common sense" tells us that the Statue is too big to fly, so I am the more likely one flying.

The second one involves a semantic inference. The meaning of give involves a physical transfer or a transfer of possession, as a consequence the item given ends up with the recipient. Our "common sense" is full of such little factoids (here is another: "Oswald killed Kennedy." => "Kennedy is dead.") which let us see beyond what is explicitly stated in the text.

I want to emphasize that these examples are qualitatively different and calling them both "common sense judgements" may be confusing. The first one is a plausibility judgement (which is more likely to fly: me or the statue?). The second one is an exact inference, i.e. "give" definitely causes transfer and "kill" definitely causes death. To solve the first one we need a model of what is more likely to be happening in the world. To solve the second one we need more traditional inference of what entails what.

Disambiguation problems in computational linguistics (word sense disambiguation, resolving syntactic ambiguities, etc.) rely on plausibility judgements, not exact inference. A lot of work in AI "common sense reasoning" will not help there because traditionally reasoning and inference work focus on exact judgements.

As far as I can see nobody is working on plausibility judgements explicitly. Researchers use corpus statistics as a proxy to solve disambiguation problems. This may be obscuring the real issue: I think the right way to do linguistic disambiguation is to have a model of what is plausible in the world.

Research focus

2010-12-23T16:59:00.007+02:00

In 1976 John McCarthy, one of the founders of artificial intelligence, wrote a memo discussing the problem of getting a computer to understand a story from the New York Times:

"A 61-year old furniture salesman, John J. Hug, was pushed down the shaft of a freight elevator yesterday in his downtown Brooklyn store by two robbers while a third attempted to crush him with the elevator car because they were dissatisfied with the $1,200 they had forced him to give them."

McCarthy suggested that a real understanding of this story would entail being able to answer questions like:

Who was in the store when the events began?
Who had the money at the end?
Did Mr. Hug know he was going to be robbed?
Does he know now that he was robbed?

Answering these questions is still beyond the state of the art in natural language processing, because they require common sense knowledge in addition to the text of the story. In fact the problems associated with answering questions only based on the text of the story are only beginning to be solved on a large scale:

When and where was Mr. Hug pushed?
Who forced who to give $1,200 to whom?
Did the money satisfy the robbers?

To achieve an understanding at this level, we need to address linguistic problems like word sense disambiguation ("push" has 15 senses), named entity recognition (Mr. Hug = John J. Hug), anaphora resolution (him = John J. Hug), parsing (who did what to whom?), semantic relation identification (dissatisfied with $1,200 = $1,200 did not satisfy). The figure below illustrates the main challenge: the ambiguity present in most natural language expressions. Our group studies statistical machine learning methods to address these problems with the eventual goal of natural language understanding by machines.

Different interpretations of the sentence: "I saw the man on the hill with a telescope."

Naive Bayes is a joint Maximum Entropy Model

2010-11-16T23:16:00.028+02:00

Naive Bayes and Maximum Entropy models are both popular in NLP applications. In this post I will show that Naive Bayes is really a type of joint Maximum Entropy model (and much easier to compute). Maximum Entropy models aim to find the distribution that maximizes entropy while still obeying certain feature expectation constraints. Maximizing entropy with feature expectation constraints turns out to be equivalent to maximizing likelihood in a log-linear (aka exponential) model. Logistic regression is a specific type of conditional maxent model. Naive Bayes is a specific type of joint maxent model.

Consider a classification problem with a D dimensional input vector x and a discrete output variable y. Naive Bayes models assume that the individual components of x are independent given the output y:

\[ p(\mathbf{x}, y) = p(y) \prod_{d=1}^D p(x_d|y) \]

The factors on the right hand side are then estimated using maximum likelihood, which boils down to counting frequencies if x and y are both discrete. In comparison here is a joint maximum entropy model:

\[ p(\mathbf{x}, y) = \frac{1}{Z} \exp(\sum_{m=1}^M \lambda_m f_m(\mathbf{x}, y)) \]

where fm are arbitrary real valued "feature functions" of the input and the output and Z is a normalization constant. This looks nothing like Naive Bayes at first glance, but if we choose feature functions that look at the output y with at most one component of the input x:

\[ p(\mathbf{x}, y) = \frac{1}{Z} \exp(\lambda_0 f_0(y)) \prod_{d=1}^D \exp(\lambda_d f_d(x_d, y)) \]

the similarity becomes more apparent. In fact if the feature functions are binary, this expression will have exactly the same form as the Naive Bayes expression, and maximizing likelihood will give exactly the same answers. Let us illustrate with an example:

\[ \begin{array}{cccc}
x_1 & x_2 & y & n \\
1 & 1 & 1 & 3 \\
1 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 3 \\
\end{array} \]

Here x1 and x2 are inputs, y is the output, and n is the number of times a particular combination has been observed. The Naive Bayes maximum likelihood estimates will give:

\[ \begin{array}{l}
p(y=1) = p(y=0) = 1/2 \\
p(x_1=1|y=1) = p(x_2=1|y=1) = 3/4 \\
p(x_1=1|y=0) = p(x_2=1|y=0) = 1/4 \\
\end{array} \]

which will lead to the following not-so-good estimates:

\[ \begin{array}{lll}
x_1 & x_2 & p(y=1|x_1, x_2) \\
1 & 1 & 0.9 \\
1 & 0 & 0.5 \\
0 & 1 & 0.5 \\
0 & 0 & 0.1 \\
\end{array} \]

The equivalent joint maximum entropy model will have 10 feature functions. The following table specifies when each feature function will return 1, star indicating "don't care":

\[ \begin{array}{lllll}
f & y & x_1 & x_2 & \lambda \\
f_0 & 0 & * & * & \lambda_0 \\
f_1 & 1 & * & * & \lambda_0 \\
f_2 & 0 & 0 & * & \lambda_1 \\
f_3 & 0 & 1 & * & \lambda_2 \\
f_4 & 1 & 0 & * & \lambda_2 \\
f_5 & 1 & 1 & * & \lambda_1 \\
f_6 & 0 & * & 0 & \lambda_1 \\
f_7 & 0 & * & 1 & \lambda_2 \\
f_8 & 1 & * & 0 & \lambda_2 \\
f_9 & 1 & * & 1 & \lambda_1 \\
\end{array} \]

Because of the symmetry of this example, not all lambda coefficients will be distinct, in fact only three distinct lambdas are necessary as indicated in the last column of the table. The maximum likelihood estimates of the lambdas will satisfy the expectation constraints: the empirical frequency of each feature will be equal to the expected frequency:

\[ \frac{1}{N} \sum_{n=1}^N f(\mathbf{x}_n, y_n) = \sum_{\mathbf{x},y} p(\mathbf{x}, y) f(\mathbf{x}, y) \]

Here the sum on the left is over the instances in the dataset, whereas the sum on the right is over all possible x, y pairs. This equation can be derived by setting the derivative of the log likelihood expression to zero. The following parameters satisfy these constraints and thus maximize the likelihood:

\[ \lambda_0 = \lambda_2 = 0, \lambda_1 = \log(3), Z = 32 \]

This joint maximum entropy model gives exactly the same results as the Naive Bayes model. For example:

\[ p(x_1=1, x_2=1, y=1) = \frac{1}{Z} \exp(\lambda_0 + 2 \lambda_1) = \frac{9}{32} \]
\[ p(x_1=1, x_2=1, y=0) = \frac{1}{Z} \exp(\lambda_0 + 2 \lambda_2) = \frac{1}{32} \]

This example is from Chris Manning's NLP class (lecture 7) where he compares the Naive Bayes model to a conditional Maximum Entropy model:

\[ p(y | \mathbf{x}) = \frac{1}{Z(\mathbf{x})} \exp(\sum_{m=1}^M \lambda_m f_m(\mathbf{x}, y)) \]

A conditional maxent model will satisfy conditional expectation constraints and maximize conditional likelihood (which can again be derived by setting the derivative of the log conditional likelihood to zero):

\[ \sum_{n=1}^N f(\mathbf{x}_n, y_n) = \sum_{n=1}^N \sum_y p(y|\mathbf{x}_n) f(\mathbf{x}_n, y) \]

Using the same set of feature functions and parameters, one can derive the values that satisfy the constraints:

\[ \lambda_0 = \lambda_2 = 0, \lambda_1 = \frac{1}{2} \log(3) \]

The conditional model will give probabilities that match the data perfectly:

\[ \begin{array}{lll}
x_1 & x_2 & p(y=1|x_1, x_2) \\
1 & 1 & 3/4 \\
1 & 0 & 1/2 \\
0 & 1 & 1/2 \\
0 & 0 & 1/4 \\
\end{array} \]

However it is important to understand that this model handles feature interactions better than Naive Bayes not because of any magic associated with maxent models, but as a result of maximizing conditional instead of joint likelihood. When you maximize joint likelihood, maxent gives the same results as Naive Bayes. Of course with maxent, one always has the option of defining features with cross terms (more than one input variable) to handle feature interaction.

Next Generation Parser Evaluation

2010-11-15T18:00:00.003+02:00

An ACL Workshop Proposal by Laura Rimell and Deniz Yuret.

This workshop aims to foster the development of innovative, targeted, formalism-independent parser evaluation resources and methods that will guide us in building the next generation of parsers.

Under many of our existing evaluation measures, parsing accuracy appears to have plateaued around the 90% mark. To continue making meaningful improvements to parsing technology, we first need to clarify what this 90% represents. Do our evaluations measure semantically-relevant syntactic phenomena? Do they accurately represent multiple domains, languages, and formalisms? How relevant are they for downstream tasks? Do they reflect the level of inter-annotator agreement? We also need to identify and understand the "missing 10%": there is a growing awareness in the community that parsers may perform poorly on less frequent but semantically important syntactic phenomena, but in fact we are not even certain whether such crucial phenomena are represented in our current evaluation schemes. We need new ways of highlighting the specific areas where parsers need to improve.

We believe parser evaluation should:

- be relevant for multiple formalisms, languages, and domains
- be targeted towards finding parser weaknesses
- focus on semantically important tasks
- be extrinsic or task-oriented as well as intrinsic
- be based on schemes with high inter-annotator agreement
- show us how we can improve parser training methods

The workshop builds on the insights gained from the COLING-08 workshop on Cross-Framework and Cross-Domain Parser Evaluation. This earlier workshop made particular inroads towards framework-independent parser evaluation by fostering discussion of formalism-independent schemes, especially grammatical relation schemes.

Despite the advances made in cross-framework evaluation, such evaluations still suffer from a loss of accuracy arising from conversion between output formats. One recent answer to this problem is the PETE task. In PETE (Yuret et al., 2010, http://pete.yuret.com) parser evaluation is performed using simple syntactic entailment questions. Given the sentence "The man who stole my car went to jail", the annotator is asked to judge entailments like "The man went to jail" or "My car went to jail". This scheme is formalism-independent, has high inter-annotator agreement, and focuses evaluation on semantically relevant distinctions. A new version of PETE will form the shared task for this workshop.

Another known weakness in existing evaluation measures, including ones based on grammatical relation formalisms, is that they are aggregate measures, in which syntactic phenomena are de facto weighted by frequency rather than by degree of syntactic difficulty or semantic importance. Thus such measures are are likely to have disproportionate contributions from high-frequency, "easy" grammatical phenomena such as determiners and subjects; while frequency weighting is obviously important, it makes it difficult to discern the phenomena where parsers really need to improve.

One answer to this problem is to focus evaluation on syntactic phenomena which we know to be difficult for parsers, such as the unbounded dependency evaluations performed in Rimell et al. (2009) and Nivre et al. (2010). This area is wide open for development: we have known for a long time that parsers have difficulty with phenomena like coordination and PP attachment, but are there other problematic constructions? We should also focus on finding new ways of determining which phenomena are most difficult, and hence where we need to focus parser training efforts. Also crucial is finding ways to measure the importance of parser errors for downstream tasks, especially semantic tasks, and weighting parser performance accordingly.

Third, many evaluations are still intrinsic, and while intrinsic evaluations play an important role -- especially for developing new parsers, and for fine-grained comparisons with previous work -- it is increasingly clear that performance on intrinsic evaluations doesn't always predict task performance.

Recent papers such as Miyao et al. (2008, 2009) and Miwa et al. (2010) focus on task-based evaluation, especially for the biomedical domain. We need more evaluations that focus on a greater range of tasks, languages, and domains (or even subdomains, since the field has barely begun to address how the vocabulary and writing conventions across e.g. biomedical subdomains may affect parsing accuracy).

Finally, unlike other NLP subfields, almost no parser evaluation studies discuss the relevance of inter-annotator agreement. It may be that the 90% evaluation plateau reflects the limits of inter-annotator agreement, but we lack a clear picture of how these figures correspond. New, more natural annotation methods may help in this area.

At this workshop we especially encourage papers that consider how techniques and resources from other NLP subfields can be brought to bear on parser evaluation. Perhaps resources annotated with information on compound nouns, subcategorization frames, selectional preferences, or textual entailments may serve as gold standards. Perhaps new gold standards may be created by exploiting shallow parsing or novel approaches to human annotation. Perhaps we can learn something from sentence simplification, semantic parsing, or active learning. Ultimately we are interested in finding new and exciting ways to identify where we need to improve our parsers.

The workshop will have two parts.

Part I: PETE-2 shared task. This will be an updated version of the successful SemEval-2010 shared task on Parser Evaluation using Textual Entailments. As noted in Yuret et al. (2010), two important improvements to the task are re-balancing the composition of syntactic phenomena covered in the task dataset, and automating the entailment generation process. Both of these improvements will be made for the new PETE-2 dataset.

Anyone will be welcome to submit a system to the shared task portion of the workshop, and reports on the shared task will make up part of the workshop program. For teams not wishing to build their own RTE system to interpret their parser output, we will ofter a simple system that generates RTE judgments from Stanford Dependency output, based on the top performing systems from SemEval-10 PETE.

Part II: Papers. We invite full-length papers which present evaluation resources, tools, techniques, or ideas; results of new evaluations; or new methods for targeted parser training based on evaluation results. We welcome submissions on all related topics, including but not limited to:

- new formalism-independent evaluation resources
- new domain-specific or cross-domain evaluation resources
- new language-specific or multi-lingual evaluation resources
- new evaluation resources targeted to specific syntactic phenomena
- new approches to identifying syntactic phenomena that are difficult for parsers
- evaluation schemes that consider semantic relevance
- new extrinsic or task-based evaluations
- schemes for improvement of a parser based on evaluation results
- evaluation techniques that consider inter-annotator agreement
- ideas for bringing insights from other NLP subfields to bear on parser evaluation

Desired Workshop Length: one day

Estimated Number of Attendees: 25

Organizers:

Laura Rimell
Computer Laboratory
University of Cambridge
William Gates Building
15 JJ Thomson Ave
Cambridge
CB3 0FD
United Kingdom
+44 (0)1223 334696
laura.rimell@cl.cam.ac.uk

Statement of research interests and areas of expertise: Rimell has worked on domain adaptation for parsing and is interested in novel parser evaluation methods. She has worked on the evaluation of a variety of treebank, grammar-based, and dependency parsers on unbounded dependencies and was a contributor to the COLING-08 parser evaluation workshop as well as a member of the top-performing team in the SemEval-10 PETE task. She is also currently working on acquisition of lexical resources and has an interest in their relationship with parsing and parser evaluation.

Deniz Yuret
Department of Computer Engineering
Koc University
Istanbul
Turkey
+90-212-338-1724
dyuret@ku.edu.tr

Statement of research interests and areas of expertise: Yuret has worked on unsupervised parsing and various unsupervised disambiguation problems, including word senses, semantic relations, and morphology. He was the organizer of the SemEval-10 PETE task and is currently co-organizing the next SemEval.

Computational Models of Narrative

2010-11-15T17:46:00.004+02:00

AAAI 2010 Fall Symposium (Proceedings), November 11-13, 2010, Arlington, VA. Mark Finlayson, Program Chair.

Narratives are ubiquitous. We use them to educate, communicate, convince, explain, and entertain. As far as we know every society has narratives, which suggests they are deeply rooted and serve an important cognitive function: that narratives do something for us. It is clear that, to fully explain human intelligence, beliefs, and behaviors, we will have to understand and explain narrative.

The symposium will bring together researchers with a wide variety of perspectives to share what is known about the fundamentals of the computational modeling of narrative and to explore the forefront of that knowledge. We seek participation from as wide a variety of approaches as possible, including not only AI researchers and technologists, but also psychologists, cognitive scientists, linguists, philosophers, narrative theorists, anthropologists, educators, storytellers, and neuroscientists.

Probability twisters

2010-11-03T20:41:00.005+02:00

Of all the math problems I collect, these are my favorites. They do not require anything more than elementary math, but they do seem to trigger a software bug in most people's brains. Choose between several different arguments that lead to different answers for each problem. (Updated Nov 2010: two siblings problem)

(Two siblings) If you pick a random family with two kids and calculate the probability of both being girls the obvious answer would be 1/4 (assuming girls and boys being equally likely). However simple variations of this problem easily lead to some confusion:
- Variation 1: If you ask the family whether they have at least one girl, and they say yes, the two girl probability is 1/3.
- Variation 2: If you see one of their kids on the street and notice that she is a girl, the two girl probability is 1/2.
You can verify these answers by imagining the sample space of all (say four million) two-child families and assuming equal numbers of boy-boy, boy-girl, girl-boy, and girl-girl families (say one million each). What is tricky to understand is why these two variations have different answers when it seems like they give you the exact same information. Here are some more variations:
- Variation 3: If you learn that the older sibling is a girl, the two girl probability is 1/2.
- Variation 4: If you learn that the family has one girl named Florida, the two girl probability is approximately 1/2.
- Variation 5: If you learn that the family has one girl born on a Wednesday, the two girl probability is 13/27.

(Umit - Monty Hall Problem) You are a participant on the game show "Let's Make a Deal." Monty Hall shows you three closed doors. He tells you that two of the closed doors have a goat behind them and that one of the doors has a new car behind it. You pick one door, but before you open it, Monty opens one of the two remaining doors and shows that it hides a goat. He then offers you a chance to switch doors with the remaining closed door. Is it to your advantage to do so?
- Argument 1: It does not matter. The probability of finding the car in the remaining two doors was equal in the beginning, and they are still equal now. The fact that you put your hand on one of them cannot increase or decrease its probability of having the car under it.
- Argument 2: If we repeated this experiment a million times, you would get the the car only one third of the time by sticking to your first door. People who consistently switch would win the other two thirds. Therefore you should switch.
- Argument 3: Think about what you would do if there were a thousand doors, rather than three, and Monty Hall opened 998 doors with goats behind them.
- Bibliography: http://math.rice.edu/~pcmi/mathlinks/montyurl.html
(Encyclopedia of Bridge) You are South with three small of a suit, and dummy has QJ9. You desperately need a trick from this suit. You lead low to the Queen, and East wins with the King. When you get a second chance, you lead low to the J9 and West plays low. Should you play the Jack or the 9?
- Argument 1: If either opponent has A10, it does not matter. If East has the Ace and West the 10, you want to play the 9. If it is the other way around, you want to play the Jack. Both sides are equally likely to have the Ace so it does not matter what you play.
- Argument 2: You should play the Jack because East has the Ace only 1/3 of the time. If East had AK, he would play the King to the first trick only half the time. If he had K10, he would always play the King. Since we know he played the King, it is twice as likely that he has the K10 and not AK.
- Note: Note the similarity with the Monty Hall problem.
(Memduh - Two envelope problem) I offer you a pick between two envelopes with money. One envelope has twice as much money as the other. You pick one, and out comes 10 dollars. Now I give you a chance to switch. Would you like to switch? How much are you willing to pay to switch?
- Argument 1: Of course you switch. The expected amount of money in the other envelope is 0.5x5 + 0.5x20 = 12.5 dollars. In fact you are willing to pay up to 2.5 dollars to switch.
- Argument 2: What if I asked you the question before you opened the envelope and saw the 10 dollars? Using the same reasoning, you can assume there is A dollars in the envelope and compute 0.5x(A/2) + 0.5x(2A) = 1.25A for the expected money in the other envelope. So you would switch. Just before you open your new envelope, I ask you whether you would like to switch again? What would your answer be?
- Note: In fact if I can find two people that believe in Argument 1, I can build a money machine. Just keep giving them two envelopes with 5 and 10 dollars and charge for switching... :^) (Of course I charge them whatever comes out of the first envelope for playing the game, so that it is a zero sum game.)
- Bibliography: http://www.u.arizona.edu/~chalmers/papers/envelope.html
(Neal) I pick two real numbers. You look at one of them. Can you find a strategy that lets you guess whether you are looking at the larger or smaller number with more than 1/2 success rate.
- Argument 1: Obviously you cannot find such a strategy.
- Argument 2: Take a probability distribution that is non-zero over all the real numbers (standard normal for example). Draw a random number from this distribution and respond assuming that the hidden number is equal to your random number. There are three cases: (i) Your random number will be smaller than both my numbers, in which case you have 50% chance of winning. (ii) Your random number will be larger than both my numbers, in which case you have 50% chance of winning. (iii) Your random number will be between my two numbers, in which case you have 100% chance of winning. The average is greater than 50%.
- Note: Using a similar argument one can show that you could in fact make a profit in the two envelope problem by employing a mixed strategy.
(Alkan) You draw a random line that cuts a circle with unit radius. What is the probability that the chord will be longer than sqrt(3)?
- Argument 1: Consider the distance between the midpoint of the chord and the center of the circle. If this distance is less than 1/2 the chord will be longer than sqrt(3). Therefore the answer is 1/2.
- Argument 2: Draw a tangent at one of the points the line intersects the circle. Consider the angle between this tangent and the chord. If this angle is between 60 and 120 degrees, the chord will be longer than sqrt(3). Therefore the answer is 1/3.
- Argument 3: Consider the midpoint of the chord. If this midpoint is within a concentric circle with half the radius, the chord will be longer than sqrt(3). The area of a circle with half the radius is 1/4th of the original. Therefore the answer is 1/4.

Anharmonicity, mode-coupling and entropy in a fluctuating native protein

2010-10-27T14:10:00.004+03:00

A. Kabakçıoğlu, D. Yuret, M. Gür, B. Erman. 2010 Phys. Biol. 7 046005 doi: 10.1088/1478-3975/7/4/046005 (PDF, PDF, HTML, Online, Hermite code)

Abstract: We develop a general framework for the analysis of residue fluctuations that simultaneously incorporates anharmonicity and mode-coupling in a unified formalism. We show that both deviations from the Gaussian model are important for modeling the multidimensional energy landscape of the protein Crambin (1EJG) in the vicinity of its native state. The effect of anharmonicity and mode-coupling on the fluctuational entropy is in the order of a few percent.

Istanbul Marathon 2010

2010-10-19T09:04:00.020+03:00

Some pictures from the Istanbul Marathon...

Here is our route from runkeeper.com:

Some useful links:
evolutionrunning.com: How to run without injury.
Galloway's Marathon book: Everybody can do it!
Born to run: To get inspired.

And some pictures:

Adam's Tongue by Derek Bickerton

2010-09-19T12:53:00.005+03:00

Bickerton presents his theory on the origin of language. Some notes:

- Human language is qualitatively distinct from animal communication systems (ACSs): most words are incomplete by themselves and need to be combined to express meaning whereas animal calls are self sufficient.

- A better model for origins of language may be pidgins (languages created by people that live together but do not share a common language).

- A protolanguage would have words as we know them that combine but no well defined rules of syntax or morphology.

- ACSs are all about the here and now, most words refer to things outside the current happenings.

- ACSs are mainly manipulative whereas language mainly informative.

- Communicative units come in three flavors: icons resemble the thing talked about, indices point to them, and symbols do neither. (function words which do not refer at all form a separate group). Displacement (referring to things that are not in the here/now) is only possible with symbols and icons. Iconic signs may have been the first displaced ones paving the way for symbols.

- "Since we usually regard language as no more than the means by which we express our thoughts, it seems natural to think that language should issue from intelligence, rather than vice versa. It seemed equally obvious, to naive observers, that the earth was the center of the universe, and the sun, moon, and planets all went around it." pp.58

- Categories are different from concepts. pp.87. Concepts you can think about or think with, whereas all you can do with categories is to tell whether something belongs in them. pp.205

- The ACSs of ants and bees may be closer to humans because they exhibit displacement (about food sources distant in time and space). ch.7

- Crucial as speciation is, it's still far from completely understood. pp.149

- The real breakthrough in language had to be displacement rather than arbitrariness (of signs). pp.160

- Bickerton's sequence:
1. Animals have concepts that won't merge.
2. Protohumans start talking.
3. Talking produces typically human concepts.
4. Merge appears and starts merging concepts.
5. The brain maybe gets rewired.
6. Capacities for complex thought planning etc. develop.

Chomsky's version has concepts appear first and talking last. pp.189.

- Thoughts like "roses are red" are offline as opposed to online thinking about here and now. (still makes the hearer do stuff: think of roses, think of red, merge...) pp.193

- Categories have to be only detailed enough to distinguish between appropriate reactions (affordances?). pp.206.

- I don't quite know what he's saying about memory pp.207 or recursion pp.244.

- Posted using BlogPress from my iPhone

Author Alerts

2010-09-04T17:58:00.006+03:00

I have looked for a way to get alerted about new releases from my favorite authors for a long time. I think Amazon used to support this in the past but they no longer do. Barnes and Noble has writer alerts for only a small list of authors. This is such an obvious feature for a bibliophile that I do not understand why nobody supports it. I was about to write my own code but luckily ran into www.authoralerts.com first. Highly recommended.

Unsupervised Part of Speech Tagging Using Unambiguous Substitutes from a Statistical Language Model

2010-08-26T11:05:00.002+03:00

Mehmet Ali Yatbaz and Deniz Yuret. Coling 2010. pp. 1391--1398. Beijing, China. (PDF, Poster)
Abstract: We show that unsupervised part of speech tagging performance can be significantly improved using likely substitutes for target words given by a statistical language model. We choose unambiguous substitutes for each occurrence of an ambiguous target word based on its context. The part of speech tags for the unambiguous substitutes are then used to filter the entry for the target word in the word--tag dictionary. A standard HMM model trained using the filtered dictionary achieves 92.25% accuracy on a standard 24,000 word corpus.

SemEval-2010 Task 12: Parser Evaluation using Textual Entailments

2010-07-15T21:06:00.004+03:00

Deniz Yuret, Aydın Han, Zehra Turgut. Proceedings of the 5th International Workshop on Semantic Evaluation. (SemEval-2010) pp. 51--56. July, 2010. Uppsala, Sweden. (PDF, Presentation, Task website, Proceedings, Journal submission).

Abstract: Parser Evaluation using Textual Entailments (PETE) is a shared task in the SemEval-2010 Evaluation Exercises on Semantic Evaluation. The task involves recognizing textual entailments based on syntactic information alone. PETE introduces a new parser evaluation scheme that is formalism independent, less prone to annotation error, and focused on semantically relevant distinctions.

L1 Regularized Regression for Reranking and System Combination in Machine Translation

2010-07-15T15:39:00.002+03:00

Ergun Bicici, Deniz Yuret. Proceedings of the Joint Fifth Workshop on Statistical Machine Translation and MetricsMATR. pp. 282--289. July 2010. Uppsala, Sweden. (PDF, Slide, Poster)

Abstract: We use L1 regularized transductive regression to learn mappings between source and target features of the training sets derived for each test sentence and use these mappings to rerank translation outputs. We compare the effectiveness of L1 regularization techniques for regression to learn mappings between features given in a sparse feature matrix. The results show the effectiveness of using L1 regularization versus L2 used in ridge regression. We show that regression mapping is effective in reranking translation outputs and in selecting the best system combinations with encouraging results on different language pairs.

The Trouble with Physics by Lee Smolin

2010-04-22T11:32:00.012+03:00

Smolin's book made me think of a dilemma I face often. I find the current system of scientific funding disturbing. Chief among the "values" of a scientist is absolute honesty. Yet, the project proposals we need to fill periodically ask us to describe what we are going to do in detail for the next three years. I don't know what I am going to do during the next three weeks! It depends on what results I am going to get using my current approach during the next couple of days. Maybe I will have a brilliant idea that will change my whole approach to the problem. Maybe I will be taken over with another problem. Honestly I don't know. The only thing I can promise is that I will put all my working energy on making progress on the problem that I find most promising at the time. But apparently that is not enough to get funding, and we are forced to either (i) bend the truth, or (ii) tie ourselves to an approach that we will most likely find suboptimal in the near future.

To me the answer is simple: scientists should be funded not on promises about the future (which nobody can honestly make, let alone scientists whose job is to explore the unknown), but on past performance. That leaves the problem of young scientists who have no past. There should be a reasonable amount of seed funding for such people, just enough to make sure an adventurous spirit has enough time to risk his career tackling an important and deep problem.

Smolin's book should be required reading by all who manage scientists and scientific funding. If you are not interested in the debate on string theory, just read the last few chapters on how science works based on a shared ethic, and why we should take a bit more risk on "Seers" who tend to obsess about high risk problems and may take a long time (sometimes forever) producing anything valuable.

Chapter 17 proposes the shared ethic among scientists rather than some abstract "scientific method" as chiefly responsible for the success of science. Chapter 18 draws a distinction between two types of scientists "Seers" and "Craftspeople". In fact pretty much the whole book is an elaboration of how and why the scientific establishment does not provide enough room for "Seers" who by nature like to obsess about high risk problems and need much longer incubation times.

I find the shared ethic of science to be one of the most important creations of human culture. I had long held the view that science was about "what is" and not about "what ought to be", thus science and ethics had nothing to do each other. Recently I started to see the ethic of scientists as people, if not the result of their work, as being very relevant. Dennis Overbye describes it best:

"Not only does science not provide any values of its own, say its detractors, it also undermines the ones we already have, devaluing anything it can’t measure, reducing sunsets to wavelengths and romance to jiggly hormones. It destroys myths and robs the universe of its magic and mystery. So the story goes. But this is balderdash. Science is not a monument of received Truth but something that people do to look for truth. That endeavor, which has transformed the world in the last few centuries, does indeed teach values. Those values, among others, are honesty, doubt, respect for evidence, openness, accountability and tolerance and indeed hunger for opposing points of view."

Biçimbilimsel Çözümleme

2010-02-23T17:51:00.003+02:00

*********************************************
KOC UNIVERSITY
ELECTRICAL AND COMPUTER ENGINEERING
ECOE 590 SEMINAR
*********************************************

Date : 23 February 2010, Tuesday
Time : 17:00
Place : ENG B29
Title : Biçimbilimsel Çözümleme
Speaker : Gülşen Cebiroğlu Eryiğit
Download : PDF

Doğal Dil İşleme’nin en temel seviyelerinden biri olan biçimbilimsel çözümleme, bir sözcüğün yapısının bilgisayarlar tarafından otomatik olarak çözümlenmesi işlemidir. Biçimbilimsel çözümleme işlemi sonucunda bir sözcüğün en küçük anlamlı birimleri olan morfemlerin (biçimbirimlerin) bulunması ve sözcük yapısının çözümlenmesi hedeflenmektedir. Örneğin “arabalar” sözcüğünün gövdesinin “araba” olduğu ve bu sözcüğün çoğul eki almış bir isim olduğunun otomatik olarak belirlenmesi bir biçimbilimsel çözümleme işlemidir. İşlem sırasında, sözcüğü oluşturan morfemlerin birbirlerinden ayrılmasından yola çıkılarak, bu işleme aynı zamanda Biçimbilimsel Ayrıştırma adı da verilmektedir.
Bu konuşmada, biçimbilimsel çözümleme konusu ayrıntılı olarak ele alınacak, kullanım alanları, genel yaklaşımlar ve Türkçe'nin biçimbilimsel çözümlemesi konusunda bilgi verilecektir.

CFP: Parser Evaluation using Textual Entailments (PETE)

2010-02-22T23:13:00.008+02:00

SemEval-2010 Shared Task #12
Parser Evaluation using Textual Entailments (PETE)
(http://pete.yuret.com)

The purpose of this post is to encourage participation in the task "Parser Evaluation using Textual Entailments" in the 5th International Workshop on Semantic Evaluations, SemEval-2010 (http://semeval2.fbk.eu/semeval2.php) collocated with ACL-2010, July
15-16, Uppsala.

This shared task should be of interest to researchers working on
* parsing
* semantic role labeling
* recognizing textual entailments

Parser Evaluation using Textual Entailments (PETE) is a shared task in the SemEval-2010 Evaluation Exercises on Semantic Evaluation. The task involves recognizing textual entailments (RTE) based on syntactic information. Given two text fragments called 'Text' and 'Hypothesis', Textual Entailment Recognition is the task of determining whether the meaning of the Hypothesis is entailed (can be inferred) from the Text. The PETE task focuses on entailments that can be inferred using syntactic information alone.

Text: The man with the hat was tired.

Hypothesis-1: The man was tired. (YES)

Hypothesis-2: The hat was tired. (NO)

Our goals in introducing this task are:

To focus parser evaluation on semantically relevant phenomena.

To introduce a parser evaluation scheme that is formalism independent.

To introduce a targeted textual entailment task focused on a single linguistic competence.

To be able to collect high quality evaluation data from untrained annotators.

The following criteria were used when constructing the entailments:

They should be decidable using only syntactic inference.

They should be easy to decide by untrained annotators.

They should be challenging for state of the art parsers.

You can find more details about our entailment generation process in the PETE Guide. You can download the development and test datasets including gold answers and system scores here: PETE_gold.zip. There is no training data. The evaluation is similar to other RTE tasks. There is a Google group semeval-pete for task related messages.

Instructions:

join the mailing list (http://groups.google.com/group/semeval-pete)
register in SemEval website (http://semeval2.fbk.eu)
download the development (trial) data from SemEval website (http://semeval2.fbk.eu)
download task guide from task website (http://pete.yuret.com/guide)
download test data from SemEval website (http://semeval2.fbk.eu)
upload results to SemEval website (http://semeval2.fbk.eu)

Important Dates:

~~February 19 - the development (trial) data available.~~

~~March 26 - the test data available.~~

~~April 2 - end of submission period for the task.~~

April 17 - Submission of description papers.

May 6 - Notification of acceptance.

July 15-16 - Workshop at ACL 2010, Uppsala.

Parsers:

Here are some links for publicly available parsers that can be used in this task. You do not have to use any of these parsers, in fact you do not have to use a conventional parsing algorithm at all -- outside the box approaches are highly encouraged. However, to get a quick baseline system using an existing parser may be a good way to start.

Berkeley Parser
Bikel Parser
C&C CCG Parser
Collins Parser
Charniak Parser
CMU Link Parser
DeSR Parser
Enju Parser
MaltParser
Minipar
MSTParser
RASP Parser
Stanford Parser
conll-entailments.pl: This is not a parser but a simple script to illustrate how short entailments may be generated from a dependency parse. Incomplete and buggy, use at your own risk.

Further Reading:

PETE Guide: A description of the entailment generation process (February, 2010).
D09-1085.pdf: Rimell, L., S. Clark, and M. Steedman. Unbounded Dependency Recovery for Parser Evaluation. Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing (August, 2009).
thesis.pdf: Onder Eker's MS thesis (August, 2009).

semeval-abstract.pdf: The PETE task abstract (December, 2008).
pete.pdf: The initial PETE task proposal (September, 2008).
Workshop on Cross-Framework and Cross-Domain Parser Evaluation (August, 2008)
natlog-wtep07-final.pdf: Bill MacCartney and Christopher D. Manning. 2007. Natural logic for textual inference. ACL-PASCAL Workshop on Textual Entailment and Paraphrasing, pp. 193-200. (June, 2007).
targeted textual entailments: On targeted textual entailments in general (June 2007).

a blog post: On the consistency of Penn Treebank annotation (October, 2006).
lre98.pdf: Carroll, J., E. Briscoe and A. Sanfilippo (1998) `Parser evaluation: a survey and a new proposal'. In Proceedings of the 1st International Conference on Language Resources and Evaluation, Granada, Spain. 447-454.

Contact:

Deniz Yuret dyuret@ku.edu.tr

Preprocessing with Linear Transformations that Maximize the Nearest Neighbor Classiﬁcation Accuracy

2010-02-21T22:27:00.003+02:00

Mehmet Ali Yatbaz and Deniz Yuret. 1st CSE Student Workshop (CSW’10), 21 February 2010, Koc Istinye Campus, Istanbul. (PDF, PPT)

Abstract
We introduce a preprocessing technique for classification problems based on linear transformations. The algorithm incrementally constructs a linear transformation that maximizes the nearest neighbor classification accuracy on the training set. At each iteration the algorithm picks a point in the dataset, and computes a transformation
that moves the point closer to points in its own class and/or away from points in other classes. The composition of the resulting linear transformations lead to statistically significant improvements in instance based learning algorithms.

L1 Regularization for Learning Word Alignments in Sparse Feature Matrices

2010-02-21T18:58:00.002+02:00

Ergun Bicici and Deniz Yuret. 1st CSE Student Workshop (CSW’10), 21 February 2010, Koc Istinye Campus, Istanbul. (PDF, Poster)

Abstract
Sparse feature representations can be used in various domains. We compare the effectiveness of $L_1$ regularization techniques for regression to learn mappings between features given in a sparse feature matrix. We apply these techniques for learning word alignments commonly used for machine translation. The performance of the learned mappings are measured using the phrase table generated on a larger corpus by a state of the art word aligner. The results show the effectiveness of using $L_1$ regularization versus $L_2$ used in ridge regression.

The Noisy Channel Model for Unsupervised Word Sense Disambiguation

2010-02-19T09:17:00.003+02:00

Deniz Yuret and Mehmet Ali Yatbaz. Computational Linguistics, Volume 36, Number 1, March 2010. (Abstract, PDF)

Abstract: We introduce a generative probabilistic model, the noisy channel model, for unsupervised word sense disambiguation. In our model, each context C is modeled as a distinct channel through which the speaker intends to transmit a particular meaning S using a possibly ambiguous word W. To reconstruct the intended meaning the hearer uses the distribution of possible meanings in the given context P(S|C) and possible words that can express each meaning P(W|S). We assume P(W|S) is independent of the context and estimate it using WordNet sense frequencies. The main problem of unsupervised WSD is estimating context dependent P(S|C) without access to any sense tagged text. We show one way to solve this problem using a statistical language model based on large amounts of untagged text. Our model uses coarse-grained semantic classes for S internally and we explore the effect of using different levels of granularity on WSD performance. The system outputs fine grained senses for evaluation and its performance on noun disambiguation is better than most previously reported unsupervised systems and close to the best supervised systems.

Emacs Turkish mode

2010-02-17T22:04:00.002+02:00

This is for people trying to type Turkish documents on a U.S. keyboard using Emacs. The program provides a turkish-mode in which the correct Turkish accents are added to the ascii version of the last word typed each time the user hits space. The latest version is available here.

It was inspired by Gökhan Tür's deasciifier:
http://www.hlst.sabanciuniv.edu/TL/deascii.html

The program uses decision lists (included at the end of this file) which was created based on 1 million words of Turkish news text using the GPA algorithm. For more information on GPA see the Greedy prepend algorithm for decision list induction.

To activate the program first load this file into emacs:
M-x load-file ENTER turkish.el ENTER
Then turn on the turkish mode:
M-x turkish-mode

When Turkish mode is enabled, the space, tab, and enter keys correct the previous word by adding Turkish accents. For corrections use C-t to toggle the accent of the character under the cursor.

Permutasyon, Kombinasyon ve 12 kardeşleri

2010-02-14T16:26:00.014+02:00

Bilgisayar Olimpiyat Kampından Notlar I

Temel sayma problemlerinin çoğu iki sonlu kümenin elemanları arasında kaç çeşit eşleme yapılabileceği sorularına indirgenebilir. Örneğin bir basketbol takımının K oyuncusunu bir otelin N odasına yerleştirmeye çalıştırdığımızı düşünelim. Öncelikle bir odada kaç kişi kalabileceği sorusuna göre üç farklı tip problem tanımlayabiliriz:

A. Bir odada herhangi sayıda oyuncu kalabilir.
B. Bir odada en çok bir kişi kalmalı (K <= N).
C. Bir odada en az bir kişi kalmalı (K >= N).

Diğer yandan K ya da N küme elemanlarının kimliklerinin önemli olup olmadığı, ya da permutasyonlarının (değişik sıralamalarının) farklı çözüm olarak sayılıp sayılmadığı da bize dört farklı tip problem verir. Bu problem tiplerini değişik objelerle örneklendirecek olursak:

0. K ve N elemanlarının kimlikleri önemli. (K kişiyi N odaya dağıtıyoruz)
1. K'lar birbiriyle eş, N'ler farklı. (K topu N odaya dağıtıyoruz)
2. K'lar farklı, N'ler birbiriyle eş. (K kişiyi N takıma ayırıyoruz)
3. K'lar da N'ler de birbiriyle eş. (K topu N gruba ayırıyoruz)

Burada birbiriyle eşlenmesi daha kolay olduğu için kişi yerine top, oda yerine takım ya da grup kullandık. (0) probleminde kimin hangi odada kaldığı önemliyken, (1) probleminde sadece hangi odada kaç top olduğu önemli. (2) probleminde ABCD isminde dört kişiyi (AB) ve (CD) gibi iki takıma ayırmakla (CD) ve (AB) gibi iki takıma ayırmak aynı çözüm sayılıyor. (3) probleminde ise ne topların ne grupların kimliği önemli, burada örneğin 6 topu 3+2+1 olarak ayırmak ile 4+1+1 olarak ayırmak farklı çözümler sayılsa da 3+2+1 ile 1+2+3 aynı çözüm sayılıyor.

Matematikçi Gian-Carlo Rota bu seçenekleri göz önüne alarak temel sayma problemlerini A0, A1, ..., C2, C3 şeklinde 12 kategoride sınıflandırmayı öneriyor. Örneğin lisede öğrendiğimiz permutasyon B0, kombinasyon B1 problemlerine denk geliyor. Malesef bu sınıflamanın dışında kalan Catalan objelerini, permutasyon tiplerini, ağaç tiplerini sayma problemleri de var fakat onları başka bir notta ele alırız.

Bu problemlerin bazıları şu teknikle çözülebilir: saymamız istenilen çözümlerden herhangi birini oluşturmak için K aşama tanımlayalım. i'nci aşamada $n_i$ potansiyel farklı seçenek olsun. İzleyebileceğimiz farklı yol sayısı bu durumda $n_1 n_2 \ldots n_k$ çarpımı olarak ifade edilebilir. Hemen bir iki örnek:

A0. K kişiyi N odaya herhangi bir sınırlama olmadan dağıtmak için her kişiye tek tek hangi odayı istediklerini sorarız. K sorunun (aşamanın) her birine N farklı cevap (seçenek) gelme olasılığı var. Dolayısıyla potansiyel çözüm sayımız $N^K$ olur.

B0. K kişiyi N odaya her odada en fazla bir kişi kalacak şekilde dağıtmak için yine herkese tek tek hangi odayı istediklerini sorabiliriz. Fakat sırası gelen kişi kendinden önce seçilmiş odaları seçemez, boş odalardan birini seçebilir. Yani birinci kişi N oda, ikinci kişi (N-1) oda, üçüncü kişi (N-2) odadan birini seçebilir. Bu durumda çözüm sayımız N(N-1)...(N-K+1)=$N^\underline{K}$ olur.

Bazan yukarıda verdiğimiz sayma tekniği kendi başına yeterli olmaz, çözümleri bilerek fazla ya da eksik sayıp sonradan bir düzeltme yapmak gerekebilir.

B1. K topu N odaya her odada en fazla bir top olacak şekilde dağıtma problemine bakalım. Topların kimliği önemli olmadığına göre buna N odadan K tanesini seçme problemi olarak da bakabiliriz. Çözüme B0 gibi başlayıp her topa hangi odayı istediğini soralım. Örneğin 3 top ve 5 oda varsa 123, 231, 245 gibi $N^\underline{K}$ farklı cevap alabiliriz. Fakat topların kimlikleri önemli olmadığına göre 123, 132, 213, 231, 312, 321 cevaplarının hep aynı 3 odayı doldurdukları için aynı konfigürasyon olarak sayılmaları gerekir. Diğer bir deyişle aslında B0 çözümü kullanarak biz her konfigürasyonu 6=3!=K! defa saymış olduk. Doğru cevabı elde etmek için B0'daki cevabı K!'e bölerek $N^{\underline{K}} / K! = \tbinom{N}{K}$ formülünü elde ederiz.

Bazı problemlerde en pratik çözüm ise önce eldeki problemi saymasını bildiğimiz başka bir probleme dönüştürmekten geçer:

A1. K topu N odaya herhangi bir sınırlama olmaksızın dağıtmayı düşünelim. Bu topları N odaya koymakla onları sıraya dizip aralarına N-1 duvar yerleştirmek birbirine eş iki problem olarak görülebilir. İkinci problemde duvarlarla toplar K+N-1 pozisyon işgal ederler. Bu pozisyonlardan hangi K tanesini topların işgal edeceğini sorarsak $\binom{K+N-1}{K}$ çözümünü elde ederiz.

C1. K topu N odaya her odada en az bir top olacak şekilde dağıtma (K>=N) probleminde ise önce her odaya birer top koyarak boş oda kalmamasını garantiler, daha sonra kalan K-N top üzerinde A1 çözümünü uygulayabiliriz: $\binom{K-1}{K-N}$.

Son olarak bu problemlerin bir kısmının kapalı bir formülle çözümü yoktur. Bu durumlarda özyinelemeli (recursive) formüller aramak tek çıkar yol olabilir:

C2. K kişiyi N takıma (her takımda en az bir kişi olacak şekilde, K>=N) ayırma problemini ele alalım. Özyinelemeli çözümlerin ana fikri problemin daha küçük bir halini çözebildiğimizi varsaymak, ve buna dayanarak orijinal problemi çözmektir. C2 için önce K-1 kişiyi takımlara ayırmanın yollarını sayabildiğimizi varsayalım. K'inci kişiyi ne yapacağımızı düşünelim. Bu son kişi ya kendi başına bir takım olacak (bu durumda geri kalan K-1 kişi N-1 takım oluşturacak), ya da diğerlerinin oluşturduğu takımlardan birinin içine eklenecek (bu durumda geri kalan K-1 kişinin N takım oluşturması, ve son kişinin bunlardan birini seçmesi gerek). Bu dediklerimizi formüle dökersek: f(K, N) = f(K-1, N-1) + N f(K-1, N). Formülü tamamlamak için problemin en küçük halini elle çözebiliriz f(1,1) = 1. Bu çözüm bize genel olarak K elemanlı bir kümenin elemanlarının kaç değişik şekilde N parçaya ayrılabileceğini verir ve hesapladığımız f fonksiyonu da ikinci tip Stirling sayısı olarak bilinir.

C3. K topu N gruba ayırma problemi için ise en küçük grupta tek top olan çözümlerle birden fazla top olan çözümleri ayrı ayrı sayalım. En küçük grupta tek top olan çözümlerin sayısını geri kalan K-1 topu N-1 gruba ayırarak bulabiliriz. En küçük grupta birden fazla top olan çözümleri ise (daha önce C1'de yaptığımız gibi) önce her gruba garanti olan birer topu koyup geri kalan K-N topu N gruba ayırarak sayabiliriz. Formüle dökecek olursak: f(K, N) = f(K-1, N-1) + f(K-N, N) ve f(1, 1) = 1. Bu çözüm bize genel olarak bir K tamsayısının kaç değişik şekilde N parçaya ayrılabileceğini verir.

Diğer çözdüğümüz problemlerde de benzer tekniklerle özyinelemeli formüller bulabiliriz. Örneğin:

A0. K-1 kişi hangi odalarda kalacaklarına karar verdikten sonra son kişi yine N odadan birini seçer.
$N^K$: f(N,K) = N f(N,K-1)

B0. Son odada kimsenin kalmadığı ve birinin kaldığı çözümleri toplarız.
$N^{\underline{K}}$: f(N,K) = f(N-1,K) + K f(N-1,K-1)

B1. Son odaya top konulan ve konulmayan çözümleri toplarız.
$\tbinom{N}{K}$: f(N,K) = f(N-1,K-1) + f(N-1,K)

Kalan problemlerin çözümünü okuyucuya bırakıyorum. İpucu olarak C0 ve A2'nin C2 kullanarak, A3'un ise C3 kullanarak çözülebileceğini B2 ile B3'un ise pek ilginç çözümleri olmadığını söyleyebilirim.

Unsupervised morphological disambiguation using statistical language models

2009-12-11T16:26:00.001+02:00

Mehmet Ali Yatbaz and Deniz Yuret. NIPS 2009 Workshop on Grammar Induction, Representation of Language and Language Learning. December 2009. (PDF, Poster)
Abstract:
In this paper, we present a probabilistic model for the unsupervised morphological disambiguation problem. Our model assigns morphological parses T to the contexts C instead of assigning them to the words W. The target word $w \in W$ determines the possible parse set $T_w \subset T$ that can be used in $w$'s context $c_w \in C$. To assign the correct morphological parse $t\in T_w$ to $w$, our model finds the parse $t\in T_w$ that maximizes $P(t|c_w)$. $P(t|c_w)$'s are estimated using a statistical language model and the vocabulary of the corpus. The system performs significantly better than an unsupervised baseline and its performance is close to a supervised baseline.

How to speak

2009-11-17T17:00:00.003+02:00

******************
KOC UNIVERSITY
ECOE 590 SEMINAR
******************

Speaker : Patrick Winston (video presentation)
Title : How to speak
Date : 17 November 2009, Tuesday
Time : 17:00
Place : ENG B30
Refreshments will be served at 16:45

Abstract: In this skillful lecture, Professor Patrick Winston of the Massachusetts Institute of Technology offers tips on how to give an effective talk, cleverly illustrating his suggestions by using them himself. He emphasizes how to start a lecture, cycling in on the material, using verbal punctuation to indicate transitions, describing "near misses" that strengthen the intended concept, and asking questions. He also talks about using the blackboard, overhead projections, props, and "how to stop."

Video available at http://isites.harvard.edu/fs/html/icb.topic58703/winston1.html

Turkish Language Resources

2009-08-27T12:22:00.000+03:00

This post contains links to various Turkish language resources that I have collected. Please send a comment if you find Turkish resources that you would like to see on this page.

Bibliography

Özgür Yılmazel's Bibliography on Turkish Information Retrieval and Natural Language Processing.

tr-disamb.tgz

Turkish morphological disambiguator code. Slow but 96% accurate. See Learning morphological disambiguation rules for Turkish for the theory.

correctparses_03.txt.gz, train.merge.gz

Turkish morphology training files. Semi-automatically tagged, has limited accuracy. Two files have the same data except the second file also includes the ambiguous parses (the first parse on each line is correct).

test.1.2.dis.gz, test.merge.gz

Turkish morphology test files, second one includes ambiguous parses (the first parse on each line is correct). The data is hand tagged, it has good accuracy.

tr-tagger.tgz

Turkish morphological tagger, includes Oflazer's finite state machines for Turkish. From Kemal Oflazer. Please use with permission. Requires the publically available Xerox Finite State software.

turklex.tgz, pc_kimmo.tgz

Turkish morphology rules for PC-Kimmo by Kemal Oflazer. Older implementation. Originally from www.cs.cmu.edu

Milliyet1.bz2, Milliyet2.bz2, Milliyet3.bz2

Original Milliyet corpus, one token per line, 19,627,500 total tokens. Latin-5 encoded, in three 11MB parts. From Kemal Oflazer. Please use with permission.

Turkish wordnet

From Kemal Oflazer. Please use with permission.

METU-Sabanci Turkish Treebank

Turkish treebank with dependency annotations. Please use with permission.

sozluk.txt.gz

English-Turkish dictionary (127157 entries, 826K) Originally from www.fen.bilkent.edu.tr/~aykutlu.

sozluk-boun.txt.gz

Turkish word list (25822 words, 73K) Originally from www.cmpe.boun.edu.tr/courses/cmpe230

Avrupa Birliği Temel Terimler Sözlüğü

(Originally from: www.abgs.gov.tr/ab_dosyalar, Oct 6, 2006)

BilisimSozlugu.zip

Bilişim Sözlüğü by Bülent Sankur (Originally from: www.bilisimsozlugu.com, Oct 9, 2006)

turkish.el

Emacs extension that automatically adds accents to Turkish words while typing on an English keyboard.

en-tr.zip, lm.tr.gz

Turkish English parallel text from Kemal Oflazer, Statistical Machine Translation into a Morphologically Complex Language, Invited Paper, In Proceedings of CICLING 2008 -- Conference on Intelligent Text Processing and Computational Linguistics, Haifa, Israel, February 2008 (lowercased and converted to utf8). The Turkish part of the dataset is "selectively split", i.e. some suffixes are separated from their stems, some are not. lm.tr.gz is the Turkish text used to develop the language model.

Önder Eker, M.S. 2009

2009-08-14T08:59:00.003+03:00

Parser Evaluation Using Textual Entailments
Önder Eker. M.S. Thesis. Boğaziçi Üniversitesi Department of Computer Engineering, August 2009. (PDF)

Abstract
Syntactic parsing is a basic problem in natural language processing. It can be deﬁned as assigning a structure to a sentence. Two prevalent approaches to parsing are phrase-structure parsing and dependency parsing. A related problem is parser evaluation. PETE is a dependency-based evaluation where the parse is represented as a list of simple sentences, similar to the Recognizing Textual Entailments task. Each entailment focuses on one relation. A priori training of annotators is not required. A program generates entailments from a dependency parse. Phrase-structure parses are converted to dependency parses to generate entailments. Additional entailments are generated for phrase-structure coordinations. Experiments are carried out with a function-tagger. Parsers are evaluated on the set of entailments generated from the Penn Treebank WSJ and Brown test sections. A phrase-structure parser obtained the highest score.

ACL 2009 Notes

2009-08-07T13:56:00.002+03:00

Some notable ACL talks with links and notes...

Tutorial: Kevin Knight, Philipp Koehn.
Topics in Statistical Machine Translation
MT: Phrase based, hierarchical, and syntax based approaches. Hiero is equivalent? to a syntax based approach with a single nonterminal. Minimum Bayes Risk (MBR) chooses not the best option but the one that has maximum expected BLEU. Approaches that work with lattices and forests. System combination provides significant gain. Integrating LM into decoding improves. Cube pruning makes hiero and syntax based more efficient. Throwing out 99% of the phrase table gives no loss. Factored models help when factors used as back off. Reordering tried before. The source and target can be string, tree, or forest. Arabic and Chinese seem most popular. Good test: can you put a jumbled up sentence in the right order. If we could output only grammatical sentences (simplified English?). Dependency LM for output language. Lattice translation. Giza alignments not very accurate, guess = 80%. Bleu between human translators is at the level of best systems, i.e. cannot use as upper bound.
Tutorial: Simone Paolo Ponzetto and Massimo Poesio.
State-of-the-art NLP Approaches to Coreference Resolution: Theory and Practical Recipes
Coref: ACE is current standard dataset. Also MUC and other new ones. Anaphora approx 50% proper nouns, 40% noun phrases, 10% pronouns. NPs most difficult. Tough to know when discourse-new. Have evaluation problems like other fields. Would think deciding on anaphora easier for annotators, but issues like whether to consider China and its population anaphoric.
P09-1001 [bib]: Qiang Yang; Yuqiang Chen; Gui-Rong Xue; Wenyuan Dai; Yong Yu.
Heterogeneous Transfer Learning for Image Clustering via the SocialWeb
ML: Qiang Yang gave the first invited talk. When the training and test sets have different distributions or different representations. Did not talk much about: when train and test have different labels. Link to causality. Unsupervised pre-learning boosting supervised learning curve.
P09-1002 [bib]: Katrin Erk; Diana McCarthy; Nicholas Gaylord.
Investigations on Word Senses and Word Usages
WSD: Annotators provide scores 1-5 for two tasks: how good a fit between a usage and sense, how close are two usages of same word. Claim forcing annotators to single decision detrimental. Also claim coarse senses insufficient to explain results.
P09-1010 [bib]: S.R.K. Branavan; Harr Chen; Luke Zettlemoyer; Regina Barzilay.
Reinforcement Learning for Mapping Instructions to Actions
Situated language: Best paper award. Good work goes beyond studying language in isolation. Reinforcement results sound incredibly good, number of features pretty small, how much prior info did they exactly use?
P09-1011 [bib]: Percy Liang; Michael Jordan; Dan Klein
Learning Semantic Correspondences with Less Supervision
Semantic representations: Learn semantic mappings in the domains of weather, robocup sportscasting, and NFL recaps when it is not clear what record and what field the text is referring to.
P09-1009 [bib]: Benjamin Snyder; Tahira Naseem; Regina Barzilay
Unsupervised Multilingual Grammar Induction
Syntax: A candidate constituent in one language may be split in another preventing wrong rules to be learnt.
P09-1024 [bib]: Christina Sauper; Regina Barzilay
Automatically Generating Wikipedia Articles: A Structure-Aware Approach
Summarization: I did not know summarization consists of cutting and pasting existing text.
P09-1025 [bib]: Neil McIntyre; Mirella Lapata
Learning to Tell Tales: A Data-driven Approach to Story Generation
Schemas: Learning a model of fairy tales to generate new ones. Nice idea but resulting stories not so good. Better models possible.
P09-1034 [bib]: Sebastian Pado; Michel Galley; Dan Jurafsky; Christopher D. Manning
Robust Machine Translation Evaluation with Entailment Features
MT: Compared to human judgement Meteor does best (significantly better than Bleu) among shallow evaluation metrics. Using RTE to see if the produced translation is an entailment or paraphrase of the reference does better.
P09-1039 [bib]: Andre Martins; Noah Smith; Eric Xing
Concise Integer Linear Programming Formulations for Dependency Parsing
Syntax: Best paper award.
P09-1040 [bib]: Joakim Nivre
Non-Projective Dependency Parsing in Expected Linear Time
Syntax: By adding one more operation that swaps tokens to the shift reduce parser, generation of nonprojective parses possible.
P09-1041 [bib]: Gregory Druck; Gideon Mann; Andrew McCallum
Semi-supervised Learning of Dependency Parsers using Generalized Expectation Criteria
Syntax: Instead of labeled data, use expectation constraints in training parser.
P09-1042 [bib]: Kuzman Ganchev; Jennifer Gillenwater; Ben Taskar
Dependency Grammar Induction via Bitext Projection Constraints
Syntax: Similar to above, but uses bitext constraints.
P09-1057 [bib]: Sujith Ravi; Kevin Knight
Minimized Models for Unsupervised Part-of-Speech Tagging
Syntax: Best paper award.
P09-1068 [bib]: Nathanael Chambers; Dan Jurafsky
Unsupervised Learning of Narrative Schemas and their Participants
Schemas: very nice work modeling structure of NYT stories. Could be improved by focusing on a particular genre and introducing narrative ordering to model (apparently time ordering is really difficult).
P09-1070 [bib]: Joseph Reisinger; Marius Pasca
Latent Variable Models of Concept-Attribute Attachment
SemRel: unsupervised learning of concept clusters and attributes for each cluster from text.
P09-1072 [bib]: Kai-min K. Chang; Vladimir L. Cherkassky; Tom M. Mitchell; Marcel Adam Just
Quantitative modeling of the neural representation of adjective-noun phrases to account for fMRI activation
Brain: continuing the work of brain imaging. Some success in guessing which adj-noun pair being thought. Better questions can be asked.
P09-2062 [bib]: Chris Biemann; Monojit Choudhury; Animesh Mukherjee
Syntax is from Mars while Semantics from Venus! Insights from Spectral Analysis of Distributional Similarity Networks
WSD: Qualitative differences between distributional similarity networks for semantics and syntax. Does it say anything about word meaning representation?
P09-2059 [bib]: Gumwon Hong; Seung-Wook Lee; Hae-Chang Rim
Bridging Morpho-Syntactic Gap between Source and Target Sentences for English-Korean Statistical Machine Translation
MT: Problems similar to Turkish. Collins '05 proposed reordering. Lee 06 removed useless function words. Hong inserts pseudo-words to xlate to Korean morphemes.
P09-2069 [bib]: Haşim Sak; Tunga Güngör; Murat Saraçlar
A Stochastic Finite-State Morphological Parser for Turkish
Mor: A probabilistic generative model for Turkish words.
P09-1076 [bib]: Bonnie Webber
Genre distinctions for discourse in the Penn TreeBank
Invited talk - Discourse: topics seem relevant to Schema learning, should find a good tutorial.
P09-1087 [bib]: Michel Galley; Christopher D. Manning
Quadratic-Time Dependency Parsing for Machine Translation
Syntax: nonprojective parsing tying each word to its most likely head. Why did this not work when I tried it in CoNLL? Gives O(n2). Could you adopt Nivre for linear? Unsupervised parsing? Using dependency LM as a feature.
P09-1088 [bib]: Phil Blunsom; Trevor Cohn; Chris Dyer; Miles Osborne
A Gibbs Sampler for Phrasal Synchronous Grammar Induction
MT: Bayesian magic. Look into SCFGs. Generates its own word alignment. Works better on non-monotonic language pairs, monotonic ones difficult to improve on.
P09-1089 [bib]: Shachar Mirkin; Lucia Specia; Nicola Cancedda; Ido Dagan; Marc Dymetman; Idan Szpektor
Source-Language Entailment Modeling for Translating Unknown Terms
MT: Generate paraphrases or entailments for unknown words using RTE.
P09-1090 [bib]: Ananthakrishnan Ramanathan; Hansraj Choudhary; Avishek Ghosh; Pushpak Bhattacharyya
Case markers and Morphology: Addressing the crux of the fluency problem in English-Hindi SMT
MT: Reordering and factored model. Fluency and adequacy manually evaluated in addition to BLEU.
P09-1108 [bib]: Adam Pauls; Dan Klein
K-Best A* Parsing
Syntax: Best paper award.
P09-1104 [bib]: Aria Haghighi; John Blitzer; John DeNero; Dan Klein
Better Word Alignments with Supervised ITG Models
MT: Check if they have code available. Claim 1.1 bleu improvement.
P09-1105 [bib]: Fei Huang
Confidence Measure for Word Alignment
MT: Measure confidence based on posterior probability, improve alignments.
P09-1113 [bib]: Mike Mintz; Steven Bills; Rion Snow; Daniel Jurafsky
Distant supervision for relation extraction without labeled data
SemRel: Unsupervised method.
P09-1116 [bib]: Dekang Lin; Xiaoyun Wu
Phrase Clustering for Discriminative Learning
WSD: cluster phrases instead of words. Much less ambiguous, so pure context. Use different size clusters together, let the learning algorithm pick. Similar to hierarchical. Improves NER and query classification. Any application where clustering words useful because of sparsity. Clusters derived from 700B web data. Are the clusters available?
P09-1117 [bib]: Katrin Tomanek; Udo Hahn
Semi-Supervised Active Learning for Sequence Labeling
ML: Self learning does not work because the instances with most confidence are not the useful ones. Active learning asks for labels of instances with least confidence. Boosting effect?
D09-1030 [bib]: Chris Callison-Burch
Fast, Cheap, and Creative: Evaluating Translation Quality Using Amazon’s Mechanical Turk
MT: This article has one answer to the BLEU upper bound question among other things. The following graph shows that professional humans still get higher Bleu compared to SMT systems (although this is using 10 reference translations). They mention Google MT got higher Bleu but probably the test set was used in training. Still gives relative performances. Also, amazing things apparently can be done with Amazon Turk. Should use them to judge Turkish alignment quality.
D09-1045 [bib]: Jeff Mitchell; Mirella Lapata
Language Models Based on Semantic Composition
LM: Using simple VSM model for semantics small improvement over trigrams.
W09-2504 [bib]: Idan Szpektor; Ido Dagan
Augmenting WordNet-based Inference with Argument Mapping
RTE: Some lexical substitutions require other words to be shuffled. Automatic learning of shuffling rules using DIRT.
W09-2506 [bib]: Stefan Thater; Georgiana Dinu; Manfred Pinkal
Ranking Paraphrases in Context
WSD: Using lexsub dataset. No dictionary (I think). VSM semantic representation. Check Mitchell&Lapata, Erk&Pado for prior work.
W09-2507 [bib]: Kirk Roberts
Building an Annotated Textual Inference Corpus for Motion and Space
W09-2510 [bib]: David Clausen; Christopher D. Manning
Presupposed Content and Entailments in Natural Language Inference
RTE: Example: "Mary lied about buying a car" -> Mary did not buy a car. "Mary regretted buying a car" -> Mary bought a car. "Mary thought about buying a car" -> Uncertain. Kartunnen 1975 presupposition projection. Check out NatLog system (natural logic).
D09-1058 [bib]: Jun Suzuki; Hideki Isozaki; Xavier Carreras; Michael Collins
An Empirical Study of Semi-supervised Structured Conditional Models for Dependency Parsing
Syntax: Take a look at earlier model in Suzuki, ACL'08. What is with the q function? Other work building on McDonald: Carreras '07, Koo '08. MIRA training.
D09-1059 [bib]: Richard Johansson
Statistical Bistratal Dependency Parsing
Syntax: Trying simultaneous parsing/SRL with joint probabilistic model.
D09-1060 [bib]: Wenliang Chen; Jun’ichi Kazama; Kiyotaka Uchimoto; Kentaro Torisawa
Improving Dependency Parsing with Subtrees from Auto-Parsed Data
Syntax: Self training, SSL for parser. Improvement, even though confidence in unlabeled text not well represented. Best system does 46% of the sentences completely correct (unlabeled).
D09-1065 [bib]: Brian Murphy; Marco Baroni; Massimo Poesio
EEG responds to conceptual stimuli and corpus semantics
Brain: Using EEG instead of fMRI in Mitchell style work. Why doesn't anybody try: (1) verbs, (2) grammaticality, (3) lie/truth, (4) agree/disagree, (5) complex grammatical constructs.
D09-1070 [bib]: Taesun Moon; Katrin Erk; Jason Baldridge
Unsupervised morphological segmentation and clustering with document boundaries
Mor: help unsupervised morphology by assuming same stem more likely to appear in same document.
D09-1071 [bib]: Jurgen Van Gael; Andreas Vlachos; Zoubin Ghahramani
The infinite HMM for unsupervised PoS tagging
Syntax: Use npbayes to pick the number of HMM states. Directly use learnt HMM states rather than trying to map them to existing tagset.
D09-1072 [bib]: Qiuye Zhao; Mitch Marcus
A Simple Unsupervised Learner for POS Disambiguation Rules Given Only a Minimal Lexicon
D09-1085 [bib]: Laura Rimell; Stephen Clark; Mark Steedman
Unbounded Dependency Recovery for Parser Evaluation
Syntax: same motivation as Onder's work. Focuses on a particular construct difficult for parsers (accuracy < 50%) and builds a test set. Same problem in many fields (infrequent senses ignored in WSD, rare issues ignored in RTE/Semantics, rare constructs ignored in syntax, etc. etc.)
D09-1086 [bib]: David A. Smith; Jason Eisner
Parser Adaptation and Projection with Quasi-Synchronous Grammar Features
Syntax: learn mapping between parsers with different output styles (e.g. how they connect auxiliary verbs).
D09-1087 [bib]: Zhongqiang Huang; Mary Harper
Self-Training PCFG Grammars with Latent Annotations Across Languages
Syntax.
D09-1088 [bib]: Reut Tsarfaty; Khalil Sima’an; Remko Scha
An Alternative to Head-Driven Approaches for Parsing a (Relatively) Free Word-Order Language
Syntax: Separate ordering information to get better coefficient stats in parser learning. Many issues same as Turkish.
D09-1105 [bib]: Roy Tromble; Jason Eisner
Learning Linear Ordering Problems for Better Translation
MT: Approximate solution to reordering problem for MT. Shows improvement. Does not make use of parse tree.
D09-1106 [bib]: Yang Liu; Tian Xia; Xinyan Xiao; Qun Liu
Weighted Alignment Matrices for Statistical Machine Translation
MT: Compact representation for an alignment distribution. Similar to forest for trees or lattice for segmentations.
D09-1107 [bib]: Matti Kääriäinen
Sinuhe – Statistical Machine Translation using a Globally Trained Conditional Exponential Family Translation Model
MT: New MT engine based on structured learning. Faster than moses with better TM scores, but overall lower BLEU.
D09-1108 [bib]: Hui Zhang; Min Zhang; Haizhou Li; Chew Lim Tan
Fast Translation Rule Matching for Syntax-based Statistical Machine Translation
MT: Compact representation with fast search for packed forests.

Modeling Morphologically Rich Languages Using Split Words and Unstructured Dependencies

2009-08-04T12:31:00.002+03:00

Deniz Yuret and Ergun Bicici. In the Joint conference of the 47th Annual Meeting of the Association for Computational Linguistics and the 4th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing (ACL-IJCNLP 2009) (PDF).

Abstract: We experiment with splitting words into their stem and sufﬁx components for modeling morphologically rich languages. We show that using a morphological analyzer and disambiguator results in a signiﬁcant perplexity reduction in Turkish. We present ﬂexible n-gram models, Flex-Grams, which assume that the n−1 tokens that determine the probability of a given token can be chosen anywhere in the sentence rather than the preceding n − 1 positions. Our ﬁnal model achieves 27% perplexity reduction compared to the standard n-gram model.

Morphological cues vs. number of nominals in learning verb types in Turkish: The syntactic bootstrapping mechanism revisited

2009-07-22T04:31:00.001+03:00

A. Engin Ural; Deniz Yuret; F. Nihan Ketrez; Dilara Koçbaş; Aylin C. Küntay. Language and Cognitive Processes, 24(10), pp. 1393-1405, December 2009 (PDF, PDF, HTML).

Abstract: The syntactic bootstrapping mechanism of verb learning was evaluated against child-directed speech in Turkish, a language with rich morphology, nominal ellipsis and free word order. Machine-learning algorithms were run on transcribed caregiver speech directed to two Turkish learners (one hour every two weeks between 0;9 to 1;10) of different socioeconomic backgrounds. We found that the number of nominals in child-directed utterances plays a small, but significant, role in classifying transitive and intransitive verbs. Further, we found that accusative morphology on the noun is a strong cue in clustering verb types. We also found that verbal morphology (past tense and bareness of verbs) is useful in distinguishing between different subtypes of intransitive verbs. These results suggest that syntactic bootstrapping mechanisms should be extended to include morphological cues to verb learning in morphologically rich languages.

Keywords: Language development; Turkish; Child-directed speech, Syntactic bootstrapping; Morphology

Natural Language Processing summer course at Sabanci University

2009-04-29T10:59:00.002+03:00

This summer Kemal Oflazer, Dilek Hakkani-Tur ve Gokhan Tur are offering a Statistical Natural Language Processing course at Sabanci University. A draft syllabus is included below.

STATISTICAL NLP CLASS:

Kemal Oflazer:

Overview of NLP (2 hours)

NLP Applications
Processing pipeline: Basic steps and how they feed into each other and how they are used by applications

Morphological Analysis (could be skipped or shortened) (2 hours)

Introduction to Statistical Models, n-gram language modeling, (2hours)

Applications to simple sequence problems (tagging English and/or deascifier)

Morphological Disambiguation (applications to Turkish)

HMMs (formal treatment (backward-forward + viterbi) + applications to tagging) (2-3 hours)

CFGs and Probabilistic CFGs (3-4 hours)

Inside-outside algorithm for training PCFGs
Parsing with PCFGs

Machine Translation (MT) (3-4 Hours)

Brief overview Classical Symbolic MT
Statistical Machine Translation

Word-based Models
Phrase-based Models
Syntax-based models

Dealing with Morphology in SMT

Dilek Hakkani-Tur:

Elements of Information Theory / Advanced Language Modeling and Applications

Entropy/Perplexity/Mutual Information
Noisy Channel Model

Sequence classification / HMM
Sample classification / Naive Bayes

Smoothing
Adaptation

Named Entity Extraction (NE)

Using HMM for NE

Using CRF for NE
Using Boosting/MaxEnt/SVM for NE

Spoken Language Understanding (SLU) as Template Filling

HMM approaches (AT&T vs BBN)
Hidden Vector State Models
Latent Semantic Analysis
Sample-classification based (Boosting/MaxEnt/Decision Trees)

Summarization

Greedy Algorithms, MMR
TextRank/LexRank
Classification based extractive summarization
Global Models for Summarization: Linear Programming approaches

Question Answering
Spoken Dialog Systems and Dialog Management (DM)

Dialog Systems
DM

Finite State Models
Agent Models
Reinforcement Learning

Gokhan Tur

Topic Classification

Discriminative classification: SVM/Boosting
Generative classification: language model, document similarity, vector-space-model
Feature selection/transformation (LDA)
Latent semantic indexing

SLU as Intent Determination

Semantic Role Labeling
Robustness to ASR

Topic Clustering

K-Means
Top/Down vs. Bottom/Up

Topic Segmentation

HMM
TextTiling
Markov Chains

Sentence Segmentation

HMM
CRF
Hybrid

Active Learning/Semi-Supervised Learning/Unsupervised Learning/Model Adaptation/Robustness

Deniz Yuret's Math Problems

2009-04-26T12:33:00.000+03:00

This is a list of elementary problems I like for one reason or another from various branches of mathematics. I cited the people I heard the problems from, they are not necessarily the originators. The unsolved flag just means that the problem is yet unsolved by me. Send me a solution if you find one. You can send me any interesting problems you find by adding a comment to this post. Also check out my other math posts, especially probability twisters, unsolved elementary problems, and links to other math sites. Last update: April 26, 2009.

(Ahmed Roman) Nathan and Abi are playing a game. Abi always goes first. The players take turns changing a positive integer to a smaller one and then passing the smaller number back to their opponent. On each move, a player may either subtract one from the integer or halve it, rounding down if necessary. Thus, from 28 the legal moves are to 27 or to 14; from 27, the legal moves are to 26 or to 13. The game ends when the integer reaches 0. The player who makes the last move wins. For example, if the starting integer is 15, Abi might move to 7, Nathan to 6, Abi to 3, Nathan to 2, Abi to 1, and now Nathan moves to 0 and wins. (However, in this sample game Abi could have played better!)
1. Assuming both Nathan and Abi play according to the best possible strategy, who will win if the starting integer is 1000? 2000? Prove your answer.
2. As you might expect, for some starting integers Abi will win and for others Nathan will win. If we pick a starting integer at random from all the integers from 1 to n inclusive, we can consider the probability of Nathan winning. This probability will fluctuate as n increases, but what is its limit as n tends to infinity? Prove your answer.
(Serdar Tasiran) We have an n boxes, k of them have a ball in them (k<=n), the others are empty. We start opening the boxes in a random order and stop when we find a ball. What is the expected number of boxes we will open?
(Ertem Esiner) Two mathematicians meet an old friend who has two kids and ask her what their ages are. The mother writes the sum of the two ages on a piece of paper and gives it to the first mathematician, and gives the product of the two ages to the second mathematician. The mathematicians think for a minute and claim the information is not sufficient. The woman says "think again". At that moment the mathematician with the product figures out the answer. How old are the two kids?
(Ertem Esiner) Five pirates are trying to divide up 1000 gold pieces among themselves. They decide to take turns making offers. An offer by a pirate is accepted if at least half of the other pirates agree to it. Otherwise the pirate making the offer is killed, and the next one makes an offer. Each pirate is greedy, but none wants to die. If you are the first pirate, what offer do you make?
(Drake) A professor announces that there will be surprise exam the following week, specifically that the students will not know what day the exam is going to take place. The students reason that the exam cannot take place on Friday, because by Thursday night they would know what day the exam is going to take place. If the exam cannot be on Friday it cannot be on Thursday either, because they would know by Wednesday night and so on. They finally decide the exam cannot take place and forget to study. The professor gives the exam on Wednesday to everybody's surprise. What went wrong?
(Mackay) Fred rolls an unbiased six-sided die once per second, noting the occasions when the outcome is a six.
1. What is the mean number of rolls from one six to the next six?
2. Between two rolls, the clock strikes one. What is the mean number of rolls until the next six?
3. Now think back before the clock struck. What is the mean number of rolls, going back in time, until the most recent six?
4. What is the mean number of rolls from the six before the clock struck to the next six?
5. Is your first answer different from your last answer? Explain.
(Deniz) You have two independent random variables between 0 and 1. How do you decide which one is more likely to be larger than the other?
(Deniz) You have two arbitrary random variables between 0 and 1. How do you decide if they are independent or not looking at their joint pdf density plot?
(Dennis Eriksson) Find all solutions to the diophantine equation: 1+2+3+...+n=m^2, where n and m are positive integers.
(Feyz) You have a deck of n cards numbered from 1 to n. dealt and shuffled randomly. What is the probability that none of the i-th card is on the i-th position?
(Sonny) Prove that there is a natural number n, for which 2^n starts with the numbers 3141592, i.e., show that there is a number of the form 3141592.... which is a power of 2 (in base 10 representation).
(Alkan) Let n, k be integers greater than 1.
1. Show that 1/1 + 1/2 + 1/3 +...+ 1/n cannot be an integer.
2. Show that 1/k + 1/(k+1) + ... + 1/(k+n) cannot be an integer.
(Will,Minsky) These problems have something in common:
1. A monk leaves to ascend to the temple on top of a mountain at 9am and arrives at 5pm. The next day he leaves the temple at 9am and arrives back at the foot of the mountain at 5pm. Prove that there is a point in time where he was at the same location on the path at the same time.
2. Prove that on a 2D earth, there exists a diameter such that the temperature at the endpoints is equal.
3. Prove that on a 3D earth, there exists a diameter such that the temperature and humidity of the endpoints are equal.
4. Does every convex closed curve in the plane contain all four vertices of some square?
(Ben) Two nice algorithm questions: Given a shuffled array of numbers from 1 to 10,000, find the three that are missing in one pass. Given an array of positive and negative integers, find the subarray with the highest sum in linear time.
(Winston) Four people want to pass a bridge dark at night. They can walk the bridge in 1, 2, 9, and 10 minutes respectively. The bridge can carry at most two people at a time. There is a single flash-light, and they need the flash-light to walk on the bridge. What is the shortest time for all four to pass across? (This was apparently a popular Microsoft interview question).
(Beril) You have a glass of tea and a glass of milk. You take a spoonfull of milk, mix it with the tea. Then you take a spoonfull of this mixture and mix it with the milk. Is there more milk in the tea or more tea in the milk at the end?
(Mine) Construct a square from: (a) Three identical squares, (b) Any two squares, (c) A rectangle. (d) Divide a square into any given two squares with the same total area. (e) Divide a circle into 6, 7, 8, and 10 equal pie-slices.
(IMO practice) m+n people are standing on a movie line. m people have 5 dollar bills, n people have 10 dollar bills. The movie is 5 dollars. The cashier opens with no money. It will close if it does not have enough change to give one person. How many possible lines are there that will get through without closing the cashier?
Note: (Deniz, Mar 10, 1998) I just discovered that this problem is equivalent to finding the number of full binary trees with m leaves when n=m-1. A full binary tree is a tree where each node has 0 or 2 children. The number of binary trees is equivalent to the number of shift-reduce sequences that parse them. For such a sequence to be valid the number of shifts need to always be ahead of the number of reduces, which turns this into our movie problem. The binary tree problem can also be solved using a generating function and the relation b[n] = sum[k=1..n-1](b[k] b[n-k]). The movie problem can be solved by using random walks and the reflection principle. The two solutions seem to give different answers but they turn out to be equivalent. This constitutes an indirect proof of the following combinatorial identity: (2n-1)!! = 2n!/(n! 2^n). Everything is related to everything else in math :-)
(Oguz) Find a function f on real numbers such that f(f(x)) = -x.
(Boris) You meet many women in your life. After meeting each one, you decide how good she is and whether you want to marry her. If you decide to marry her, you lose your chance with future candidates. If you decide to move on, you lose your chance with her. Assuming you will meet at most n women, find the optimum strategy for marrying the best bride.
(The Azeri mathematician Gussein-Zade is apparently the first one to solve this problem.)
(Alkan) A small rectangle is cut out of a large rectangle. Find a line that divides the remaining figure into two equal areas using an unmarked ruler.
(IMO) Let A be a set of ten two-digit integers. Prove that one can always find two subsets of A with the same sum.
(IMO) 17 people correspond with each other. Each pair discusses one of three possible topics. Prove that there are three people that discuss the same topic with each other.
(Alkan) Five couples meet in a party. Everyone starts shaking hands with everyone else except their partners. At some point the host stops them and asks how many handshakes each had. Everyone gives a different number. How many hands did the host's wife shake?
(IMO-75/4) When 4444 ⁴⁴⁴⁴ is written in decimal notation, the sum of its digits is A. Let B be the sum of the digits of A. Find the sum of the digits of B. (A and B are written in decimal notation.)
(Murat Fadiloglu) What is the probability of two randomly selected integers being mutually prime?
(Alkan) An old lady buys a plane ticket to visit her son. She goes to the airport and people let her board first. Since she can't read her seat number, she sits on a random seat. Rest of the passengers sit on their own seats, unless it is occupied in which case they randomly choose one of the emtpy seats. What is the probability that the last passenger will sit on his own seat?
(Alkan) sqrt(1 + 2*sqrt(1 + 3*sqrt(1 + 4*sqrt(1 + 5*sqrt(1 + ... ))...) = ?
(Rota) Given a sequence of (n ² + 1) distinct integers, show that it is possible to find a sequence of (n+1) entries which is increasing or decreasing.
(Minkowsky) Consider a two dimensional lattice with grid points unit distance apart. Show that a convex shape that is symmetric around a grid point has to include at least three grid points if its area is 4.
(Science Museum, unsolved) Which rectangles can be divided into unequal squares?
(Alkan) Consider permutations of an array which contains n copies of each integer from 1 to n. Two permutations are defined as orthogonal if their corresponding elements form distinct pairs. What is the maximum number of permutations such that any two are orthogonal? For example, here is a possible set of mutually orthogonal permutations for n=3: {111222333, 123123123, 123231312, 123312231}.
(Ian) My new favorite algorithm: Find an algorithm that discovers if a linked list has a cycle in it using bounded memory.
(Uttrash) You are in prison and they give you n red balls, n green balls and two boxes. You are to place the balls in the two boxes in any way you like. The next day they will pick a ball from one of the boxes, and if it is green you will be set free. How do you arrange the balls?
(Will) You randomly throw k balls into n bins. What is the expected number of occupied bins.
(Will) You randomly throw k points on the unit interval. What is the expected length of the longest segment.
(Michael, unsolved) You distribute 100 balls to 10 buckets. What is the expected value of the number of balls in the bucket with most balls.
(Lon) Draw 2 circles, 1 completely inside the other (but not necessarily concentric.) What is the probablility that a line intersecting the outer circle also intersects the inner circle. Now, do the same with rectangles.
(Thurston and Conway) An angel is stuck on an infinite sheet of graph paper, he can hop from square to adjacent square. Everytime the angel hops, the devil can knock out any square, so the angel can't ever go there. Can the devil trap the angel? What if the graph paper is a positive quadrant (i.e. is bounded on two sides).
This is not really math, but here are my two favorite algorithms: (1) Find an algorithm for perfect shuffling of an array. (2) Find an algorithm that will pick a perfectly random element from a list in one pass without knowing the size of the list beforehand.
(Alkan) Given two points find the point midway between them using only a compass (no ruler).
(Alkan) You are sitting at point [0,0] and looking towards right into a tunnel bounded by y=1/x and y=-1/x curves. The walls of the tunnel are reflecting. Prove that if you send a light beam into the tunnel in any direction other than straight to the right, the beam will be reflected back towards left.
(Deniz) Let x be a random variable which can take positive integer values. P(x)=1/2^x. We draw n random elements from this distribution. What is the probability that the n+1st element will be different from the first n?
(Alkan) Let A be the set of all rectangles that have one integer side. Prove that any rectangle constructed by concatenating rectangles from A will also be a member of A.
(Neal) Take a randomly shuffled deck. Open the cards one by one. At one point stop and predict that the next card is red. Is there a strategy that has more than 1/2 chance.
Pick two random points in the unit line segment. What is the expected distance between them?
Pick two random points in the unit circle. What is the expected distance between them?
(Umit) Suspend a rope from two points on the ceiling. What shape does it take?
(Bernoulli brothers) A ball is rolling from point A to a lower point B. What is the ideal curve for the path between A and B that minimize the travel time?
(Alkan) There are 100 light poles with switches on a street. In the beginning all lights are off. One person goes through pole number 1, 2, 3, ... and flips the switches. Then he goes back and goes through 2, 4, 6, ... and flips the switches. Then he goes back and goes through 3, 6, 9, ... and flips the switches. So at n'th round he flips the multiples of n. Which lights are on after 100 rounds?
(Deniz) There is a set A of n0 elements, and we randomly pick a subset B of n1 elements. We know that r0 of the elements in A were red. We are interested in finding out the number of red elements in B, r1. To find out we start picking random elements from B. We pick n2 elements, and r2 of them turn out to be red. Now what is the best estimate for r1?
(Minsky) I bring you three flipped cups and tell you there is gold under one of them. Furthermore, each cup has a number giving the probability that the gold is under that one. You immediately go to the one with highest probability. I tell you that you have amnesia and I may have tried this on you a million times. What is your best strategy?
(Minsky) An ant leaves a repeated binary pattern behind as it walks through the desert. What is the length of the shortest pattern that would let you distinguish which way the ant was going?
(Feyzu) Two points are chosen at random on a line AB, each point being chosen according to the uniform distribution on AB, and the choices being made independently of each other. The line AB may now be regarded as divided into three parts. What is the probability that they may be made into a triangle?
(IMO practice) The entries for a competition is locked in a safe. There are 11 judges. We would like them to be able to open the safe when more than half get together. How many locks / keys do we need?
(IMO practice) Given three parallel lines, show that an equilateral triangle can always be constructed with a vertex on each line.
(IMO-72/6) Given four distinct parallel planes, prove that there exists a regular tetrahedron with a vertex on each plane.
(Umit) A method for two people to share a pie fairly is to let one cut the other one pick. Generalize this method to n people.
You are making a random walk on an n-dimensional grid. What is the probability that you will ever return to the origin? (Hint: It is 1 for 1-D and 2-D! It is 0.3405 for 3-D).
(Ivanie) A rabbit hopping up the stairs can hop either one or two steps at a time. How many different ways can it climb n steps?
Show that if you cut off two opposite corner squares of a chess board, you cannot cover the rest with dominoes.
Show that n squares with total area less than 1/2 can always be fit into a unit square (non-overlapping).
Show that n squares with total area greater than 3 can always cover the surface of the unit square (non-overlapping).
You color all points of a plain with three colors. Show that I can always find two points of the same color that are a given distance apart.
You color all points on an equilateral triangle with two colors. I try to find a right triangle with its vertices on the edges of your triangle and all vertices having the same color. Can you find a coloring that prevents this?
How many 1's are there in the digits of numbers from 1 to 1 million? (one minute time limit).
(Michael) There is a piece of candy on every node of a binary tree. Find the shortest path through the binary tree that lets you collect all of the candies.
(Ihsan) Two men, x distance apart, start walking toward each other with speed v. At that instant a fly starts flying from one men's nose to the other with 2v speed. The fly keeps flying back and forth between the two noses until the guys meet. How much distance has the fly flown when they meet? (There is an easy way and a hard way to solve this).
(Ihsan) A coin is flipped until the first head appears. If you get a head in n flips you win $2ⁿ. How much are you willing to pay to play this game?
(Bilim ve Teknik) You need to paint the area under the curve 1/x. How can you do it with a finite amount of paint?

Dennett in Istanbul

2009-04-04T19:11:00.014+03:00

As part of Sabanci University's Darwin Year Celebration activities, Prof. Daniel C. Dennett is going to give a talk entitled "Darwin's strange inversion of reasoning" at the Sakip Sabanci Museum on April 10, 2009 at 16:00.

Dennett's 1995 book Darwin's Dangerous Idea argues that natural selection is a blind and algorithmic process sufficiently powerful to account for the generation and evolution of life, minds, and societies. I am looking forward to his talk, an earlier version of which I had seen at MIT when the book first came out.

These days he has taken on religious fundamentalism (see Breaking the Spell). One of his proposed solutions to fight ignorance and intolerance is to teach children about ALL of world's religions instead of brainwashing them with a single system of thought, or leaving them vulnerable by not teaching them about religion at all.

If you have not had the pleasure of listening to Dennett before, I recommend his many recorded talks available at the following websites: TED talks, Wikipedia, Reitstoen.com, and his homepage.

Dennett is quite popular in the Artificial Intelligence / Cognitive Science community due to his refreshingly rational explanations of perplexing issues like consciousness and free will. You may not agree with the specifics of his theories, but at least he makes a convincing case that there is no need for "magic dust" to explain these natural phenomena. Talking about interesting psychological results in Sweet Dreams he says:

I often discover skeptics who are quite confident that I am simply making these facts up! But we must learn to treat such difficulties as measures of our frail powers of imagination, not insights into impossibility.

Yet some of his adversaries take the failure of their imagination for a physical model of the mind as evidence of its impossibility, succumb to mysterianism, take comfort in the assumption that some questions will never be answered, or look for magic dust in the depths of quantum theory. Dennett thinks one day we will find a psychological explanation for their defect.

Many of Dennett's books that I have mentioned in this blog are on the mysteries of the mind. If you get sleepy when you read philosophy, then I especially recommend Mind's I which is one of my favorite collections of philosophical fiction. Here is a list of his books which I hope to turn into an annotated bibliography at some point:

Content and Consciousness (1969)
Brainstorms: Philosophical Essays on Mind and Psychology (1978)
Mind's I: Fantasies and Reflections on Self and Soul (1981)
Elbow Room: The Varieties of Free Will Worth Wanting (1984)
The Intentional Stance (1987)
Consciousness Explained (1991)
Darwin's Dangerous Idea: Evolution and the Meanings of Life (1995)
Kinds of Minds: Towards and Understanding of Consciousness (1996)
Brainchildren: Essays on Designing Minds (1998)
Freedom Evolves (2003)
Sweet Dreams: Philosophical Obstacles to a Science of Consciousness (2005)
Breaking the Spell: Religion as a Natural Phenomenon (2006)

Matematik nereden gelir

2009-03-22T18:00:00.001+02:00

Uzun zamandır rafımda toz tutan Lakoff ve Núñez'in Where Mathematics Comes From (Matematik nereden gelir) kitabını yeni okumaya başlamıştım. Geçen Perşembe de (serendipity'nin Türkçesi nedir?) Alexandre Borovik'in Bilgi Üniversitesinde aynı konuda verdiği Shadows of the Truth seminerine gitme şansını buldum, Emre sağolsun. İnsan aklının matematiği nasıl ortaya çıkardığı sorusunu soran bu iki çalışma benzer bir sonuca varıyorlar: en soyut düşüncelerimiz bile metaforlarla somut, fiziksel, görsel, bedensel bilgilere bağlanıyor. Sanırım dört işlem için parmaklarını kullanan, ya da bir üçgenin açıortaylarının aynı noktada kesiştiğini görebilmek için eline kağıt kalem alma ihtiyacı hisseden hiç kimse için bu sürpriz olmamalı. Şaşırtıcı olan matematik eğitiminde bu bağlantıların daha yapıcı şekilde kullanılmaması.

Özellikle çocuklarda henüz soyutla somutun arası çok açılmadığı için bu bağlantılar son derece açık. Örneğin Lakoff ile Núñez temel aritmetiğin dört zihinsel işleve dayandığını iddia ediyorlar: farklı cisimleri bir araya getirmek, parçalarından bir cisim oluşturmak, cetvelle bir uzunluk ölçmek, ve bir yol üzerinde hareket etmek. Borovik'in dört işlem örneklerinde çocukların sayı kavramını henüz saydıkları cisimlerden soyutlayamadıkları için aslında aritmetikten çok daha zor bir problemle uğraştıkları vurgulanıyor. Örneğin elmalarla armutları toplayamayız derken, 10 elmayı 5 insana bölmek kurallara aykırı sayılmıyor okul kitaplarında. Hele hele 10 elmayı ikişer ikişer paylaştırdığımızda beş insana yeteceğini hesaplarken (10/2=5), sol tarafta elmaları bölerken sağ taraftan insanların çıkmasına ne demeli? Benzer örnekleri ve çocukların bunları nasıl kavramlaştırdığı konusundaki teorilerini Borovik'in web sayfasındaki iki kitap çalışmasında okuyabilirsiniz.

Lakoff ve Núñez'in kitabının son bölümü tek bir örneğe ayrılmış. Euler'in meşhur e^πi + 1 = 0 eşitliği. Yazarlar haklı olarak matematiğin en meşhur sayılarını bir araya getiren bu eşitliğin 3^6=729 gibi rastgele bir rakamsal eşitlik olmadığını belirtiyorlar. Euler'in eşitliğindeki her sabitin uzun bir metaforlar zinciriyle desteklenen derin birer anlamı var. Bu zinciri bir noktada kaybeden öğrenci eşitliğin ispatını anlasa bile ne demek olduğunu anlamıyor. Yazarların 70 sayfada sabırla çözümlediği bu metaforlar zincirini burada hakkıyla anlatmam zor. Ama aşağıdaki sorulardan bazıları sizin de kafanızı karıştırıyorsa okumanızı tavsiye ederim:

1. Eğer a^b işlemi a sayısını b defa kendisiyle çarpmak demek ise e sayısını kendisiyle pi defa çarpmak ne demek?

2. i sayısı nereden gelir, neden sanaldır, bir sayıyı i ile çarpmak ya da i'nci üssünü almak ne demek?

3. e sayısı niye 2.718281828459045... değerine sahip?

4. pi sayısı dairelerle ilgili birşey değil miydi? Euler'in eşitliğinin dairelerle ne ilgisi var?

5. İçinde e ve pi gibi iki tane sonsuz kesir olan bir işlem bize nasıl -1 gibi basit bir sonuç verebilir?

6. Matematikte niye e, pi, i, 1 ve 0 sayıları durmadan ortaya çıkıyor ama çoğu sayı (örneğin 192563948.98542129) pek görünmüyor? Bu sayıların sembolize ettiği fikir ve kavramlar nedir?

Classification of semantic relations between nominals

2009-03-03T11:21:00.005+02:00

Roxana Girju, Preslav Nakov, Vivi Nastase, Stan Szpakowicz, Peter Turney and Deniz Yuret. Language Resources and Evaluation, 2009, 43(2), 105-121. (PDF, PDF, HTML).

Abstract: The NLP community has shown a renewed interest in deeper semantic analyses, among them automatic recognition of semantic relations in text. We present the development and evaluation of a semantic analysis task: automatic recognition of relations between pairs of nominals in a sentence. The task was part of SemEval-2007, the fourth edition of the semantic evaluation event previously known as SensEval. Apart from the observations we have made, the long-lasting effect of this task may be a framework for comparing approaches to the task. We introduce the problem of recognizing relations between nominals, and in particular the process of drafting and refining the definitions of the semantic relations. We show how we created the training and test data, list and briefly describe the 15 participating systems, discuss the results, and conclude with the lessons learned in the course of this exercise.

Incandescence by Greg Egan

2009-03-01T18:45:00.016+02:00

Greg Egan's latest novel Incandescence is a great thought experiment exploring how a primitive alien race living inside the tunnels of an asteroid orbiting around a neutron star can find evidence for Newtonian physics and even general relativity using simple experiments inside their closed world. The motion around the star causes a nontrivial field of forces inside the asteroid. There is no weight at the center. Away from the center, the amount and direction of the weight depends on the location relative to the center. Zak, the alien Newton, starts to explain this state of affairs with a simple assumption: "Weight is the difference between preferred and actual motion."

For example, when an object is placed north or south of the center, it is pulled towards the center. Here is what an object left to free fall from the north of the center looks like to an observer inside the asteroid:

However from a different perspective, one can see that the object is actually moving around its own slightly tilted orbit around the star. And if the object is supported by a floor and is prevented from moving toward the center, it will experience a gravitational pull toward the center -- thus an example of the maxim: "Weight is the difference between preferred and actual motion."

When two object are placed toward and away from the sun with respect to the center of the asteroid, they feel a pull away from the center:

Again, from a different perspective, this can be seen as the objects trying to follow their own natural orbits, and weight being the difference between preferred and actual motion:

As a final example, suppose an object at the center is given a radial push. Unlike the objects in the previous example, this object will not accelerate away from the center, but keep cycling in an elliptical course as seen from inside the asteroid:

The standard explanation is in terms of Coriolis force due to the object's motion balancing the tidal acceleration. From the orbital perspective, our radial push places the object in an elliptical orbit crossing the circular orbit of the planet:

Starting with these and many other interesting observations, Zak and his friends uncover the secrets of their universe before ever stepping outside their closed world and ever seeing their sun, their orbit, or fixed stars. The book is a treat for aficionados of gedankenexperiments and qualitative physics.

P.S. I'd like to thank Greg Egan for allowing the use of these animations from his page, which hosts a treasure of information about science and science fiction.

Ergun's English-Turkish machine translation notes

2009-02-16T16:50:00.006+02:00

Here are some useful notes from Ergun Bicici on getting started with Turkish-English machine translation, followed by some suggestions by Murat Alperen on collecting Turkish-English parallel text data.

Turkish English parallel text from Kemal Oflazer, Statistical Machine Translation into a Morphologically Complex Language, Invited Paper, In Proceedings of CICLING 2008 -- Conference on Intelligent Text Processing and Computational Linguistics, Haifa, Israel, February 2008 (lowercased and converted to utf8):
en-tr.zip

The Turkish part of the dataset is "selectively split", i.e. some suffixes are separated from their stems, some are not.

Here is the Turkish text to develop the language model:
lm.tr.gz

The directions for the Moses baseline system:
http://www.statmt.org/wmt09/baseline.html

The link for the scripts:
http://www.statmt.org/wmt08/scripts.tgz

Be careful to put the stems and suffixes back together before computing the BLEU score. Splitting them artificially increases the score.

To compute the score do not use the mteval scorer at http://www.statmt.org/wmt09/baseline.html - because it retokenizes the input and splits all the '+' characters that are used to denote suffixes. Either use the multi-bleu perl script, or comment out the language-dependent part of NormalizeText in mteval.

For Turkish dictionaries and other resources please see Turkish language resources.

Turkish morphology presentation

2009-02-11T18:46:00.010+02:00

Please click on "Full Post" to view an introductory Turkish morphology presentation. To learn more about Turkish morphology I recommend this paper by Kemal Oflazer. For morphological disambiguation check out Haşim Sak's webpage or this paper by Deniz Yuret and Ferhan Türe. You can try analyzing a Turkish word here:

İngilizce Türkçe otomatik tercüme

2009-02-02T21:41:00.004+02:00

Google sonunda otomatik tercüme yaptığı dillere Türkçe'yi de
ekledi. Denemek isterseniz: http://translate.google.com

Bu teknolojinin İngilizce bilmeyen Türk nüfusunun internetteki
bilgi birikimine ulaşımı için önemli olduğunu düşünüyor ve birkaç
yıldır üzerinde ben de çalışıyorum. En büyük engellerden biri
araştırma amacıyla kullanılabilecek yüklü miktarda
İngilizce-Türkçe paralel metne ihtiyaç olması (yaklaşık 100 milyon
kelime = 1000 kitap). Bu metni toplayabilmek için bir iki yıl
telefonla devlet kurumları, uluslararası kuruluşlar, yayınevi,
haber kurumu, hukuk ve tercümanlık şirketleri, üniversite
bölümleri vs ile görüşüp pozitif bir cevap alamayınca yoruldum ve
vazgeçtim. İşin üzücü tarafı karşılaştığım büyük engelin yayın
hakkı, fikir mülkiyeti gibi hukuksal bir konu değil, insanların
ilgisizliği olması. Şimdilik bir iki milyon kelimelik metinden
geliştirilmiş oyuncak bir sistemle uğraşıyorum öğrencilerimle.
Google'ın sistemini ben yazmış olmak isterdim. Ama henüz yarışma
bitmiş değil, sistemin kalitesine bir örnek olarak bu paragrafın
bir tercümesini veriyorum...

This technology does not speak English in the Turkish population
on the Internet access to knowledge is important to think and a
few years, I am working on. One of the biggest obstacles can be
used for research purposes in the amount of installed
English-English parallel text is needed (about 100 million word =
1000 books). This text to be able to collect a two-year phone and
the state institutions, international organizations, publishing,
news agency, law and translation companies, universities sections
and with a positive answer so do not get tired and I've given
up. The major obstacle faced by the unfortunate job of
broadcasting the The right to legal issues such as property, not
the ideas, people is indifference. Currently, one of two million
words of text I'm dealing with a system developed for students
with toys. I would like it to Google's system. But the contest
yet not finished, as an example of the quality of the system of
this paragraph I give a translation...

Neşe Aral, M.S. 2009

2009-01-28T12:12:00.004+02:00

Dynamics of Gene Regulatory Cell Cycle Network in Saccharomyces Cerevisiae
Neşe Aral. M.S. Thesis, Koç University Department of Physics, January 2009.

Abstract: In this thesis, the genetic regulatory dynamics within the cell cycle network of the yeast Saccharomyces Cerevisiae is examined. As the mathematical approach, an asynchronously updated Boolean network is used to model the time evolution of the expression level of genes taking part in the regulation of the cell-cycle. The attractors of the model’s dynamics and their stability are investigated by means of a stochastic transition matrix. It is shown that the cell cycle network has unusual dynamical properties when compared with similar random networks. Furthermore, an entropy measure is employed to monitor the sequential evolution of the system. It is observed that the experimentally identified cell cycle phases G1, S, G2 and M correspond to the stages of the network where the entropy goes through a local extremum.

Download PDF

Show and Tell

2008-12-03T16:41:00.008+02:00

Here is a little demo video of some work I did with Sajit at MIT CSAIL this summer. The computer watches us play with a ball and produces live commentary. For now the detection of actions (like give, drop, move) are hand coded, the next step would be to learn them from examples. The step after that is "tell and show", i.e. to go from words to pictures. This would complete the imagination-perception loop which may underlie much understanding and problem solving.

I think one of the coolest things about the current implementation is how the computer starts a sentence and cuts it in half to say something more important. There is always tons of possible things to say and possible words to say them with, and a similar competition must be going on in our heads.

Morphological cues vs. number of nominals in learning verb types in Turkish: Syntactic bootstrapping mechanism revisited

2008-10-31T16:03:00.007+02:00

Deniz Yuret, A. Engin Ural, Nihan Ketrez, Dilara Koçbaş and Aylin C. Küntay. In The Boston University Conference on Language Development (BUCLD) (Long abstract, poster, PDF)

Abstract: The syntactic bootstrapping mechanism of verb classification was evaluated against child-directed speech in Turkish, a language with rich morphology, nominal ellipsis and free word order. Machine-learning algorithms were run on transcribed caregiver speech (12,276 and 20,687 utterances) directed to two Turkish learners (one hour every two weeks between 0,9 to 1;10) of different socioeconomic backgrounds. The corpora contained 12,276 and 20,687 child-directed utterances. Study 1 found that the number of nominals in child-directed utterances plays some role in classifying transitive and intransitive verbs. Study 2 found that accusative morphology on the noun is a stronger cue in clustering verb types. Study 3 found that verbal morphology is useful in distinguishing between different subtypes of intransitive verbs. These results suggest that syntactic bootstrapping mechanisms should be extended to include morphological cues to verb learning in morphologically rich languages.

Parser Training and Evaluation using Textual Entailments

2008-09-20T22:55:00.004+03:00

A task proposal for SemEval-2010 by Deniz Yuret and Önder Eker. For example sentences and the bibliography, please download the original PDF.

Description of the Task

We propose a targeted textual entailment task designed to train and evaluate parsers. The typical parser training and evaluation methodology uses a gold treebank which raises several issues: (1) The treebank is built around a particular linguistic representation which makes parsers that use different representations (e.g. phrase structure vs. dependency) difficult to compare. (2) The parsers are evaluated based on how much of the linguistic structure dictated by the treebank they can replicate, some of which may be irrelevant for downstream applications. (3) The annotators that create the treebank not only have to understand the sentences in the corpus, but master the particular linguistic representation used, which makes their training difficult and leads to inconsistencies (see Carroll1998 for a review and Parseval2008 for more recent work on parser evaluation).

In the proposed method, simple textual entailments like the following will be used to fine-tune and evaluate different parsers:

Final-hour trading accelerated to 108.1 million shares, a record for the Big Board.
- 108.1 million shares was a record. -- YES
- Final-hour trading accelerated a record. -- NO
Earlier the company announced it would sell its aging fleet of Boeing Co. 707s because of increasing maintenance costs.
- It would sell the fleet because of increasing costs. -- YES
- Selling the fleet would increase maintenance costs. -- NO
Persistent redemptions would force some fund managers to dump stocks to raise cash.
- The managers would dump stocks to raise cash. -- YES
- The stocks would raise cash. -- NO

The entailment examples will be generated based on the following criteria: (1) It should be possible to automatically decide which entailments are implied based on the parser output only, i.e. there should be no need for lexical semantics, anaphora resolution etc. (2) It should be easy for a non-linguist annotator to decide which entailments are implied, reducing the time for training and increasing inter-annotator agreement. (3) The entailments should be non-trivial, i.e. they should focus on areas of disagreement between current state of the art parsers. The above examples satisfy all three criteria.

Training and evaluating parsers based on targeted textual entailments address each of the issues listed in the first paragraph regarding treebank based methods: The evaluation is representation independent, therefore there is no difficulty in comparing the performance of parsers from different frameworks. By focusing on the parse differences that result in different entailments, we ignore trivial differences that stem from the conventions of the underlying representation which should not matter for downstream applications. Finally our annotators will only need a good understanding of the English language and no expertise on any linguistic framework.

Generating Data

The example entailment questions can be generated by considering the differences between the outputs of different state of the art parsers and their gold datasets. Some of the detected parse differences can be turned into different entailments about the sentence. The example entailments in the previous section were generated comparing the outputs of two dependency parsers, which are included in the appendix. The generated entailments will then be annotated by multiple annotators and the differences will be resolved using standard techniques.

Generating entailment questions out of parser differences allow us to satisfy conditions 1 and 3 easily: the entailments can be judged based on parser output because that is how they were generated, and they are non-trivial because some state of the art parsers disagree on them.

In our experience the most difficult condition to satisfy is 2: that it should be easy for a non-linguist annotator to decide which entailments are implied. In most of the example sentences we looked at, the differences between the parsers were trivial, e.g. different conventions on how to tag coordinating conjunctions, or whether to label a particular phrase with ADVP vs. ADJP etc. These differences are trivial in the sense that it is impossible to generate different entailments from them, thus it is hard to see how they would matter in a downstream application.

The trivial differences between parsers make example generation using our process difficult. The efficiency of example generation may be improved by pre-filtering candidate sentences which contain structures that involve non-trivial decisions by the parser such as prepositional phrase attachments. In addition some types of entailment generation can be automated. On the other hand the requirement of expressing differences in entailments will hopefully focus the training and the evaluation on non-trivial differences that actually matter in applications.

Evaluation Methodology

The participants will be provided with training and test sets of entailments and they will be evaluated using the standard tools and methodology of the RTE challenges (Dagan2006). The main difference is that our entailment examples focus exclusively on parsing. This should make it possible to write simple tree matching modules that decide on the entailments based on parser output alone. Example tree matching modules for standard formats (Penn Treebank (Marcus1993) format for phrase structure parsing, and CoNLL (Nivre2007) format for dependency parsing) will be provided as examples which should make preparing an existing parser for evaluation relatively easy.

The training part will be more parser specific, so individual participants will have to decide how to best make use of the provided entailment training set. It is unlikely that we will be able to generate enough entailment examples to train a parser from scratch. Therefore the task will have to be open to using other resources. The participants will be free to use standard resources such as treebanks to train their parsers. We can also consider restricting the outside training resources (e.g. Penn Treebank only) and the domain of the entailments (e.g. finance only). The entailment training set can then be used to fine tune the parser by focusing the evaluation on important parser decisions that effect downstream applications.

Discriminative vs. Generative Approaches in Semantic Role Labeling

2008-08-16T15:52:00.007+03:00

Deniz Yuret, Mehmet Ali Yatbaz and Ahmet Engin Ural. In Proceedings of The Twelfth Conference on Natural Language Learning (CoNLL-2008) (PDF, ACM)

Abstract: This paper describes the two algorithms we developed for the CoNLL 2008 Shared Task “Joint learning of syntactic and semantic dependencies”. Both algorithms start parsing the sentence using the same syntactic parser. The first algorithm uses machine learning methods to identify the semantic dependencies in four stages: identification and labeling of predicates, identification and labeling of arguments. The second algorithm uses a generative probabilistic model, choosing the semantic dependencies that maximize the probability with respect to the model. A hybrid algorithm combining the best stages of the two algorithms attains 86.62% labeled syntactic attachment accuracy, 73.24% labeled semantic dependency F1 and 79.93% labeled macro F1 score for the combined WSJ and Brown test sets.

Ahmet Engin Ural, M.S. 2008

2008-08-01T13:00:00.002+03:00

Evolution of Compositionality with a Bag of Words Syntax
Ahmet Engin Ural, M.S. Thesis, Koç University Department of Computer Engineering, August 2008.

In the last two decades, the idea of an emerging and evolving language has been studied thoroughly. The main question behind this kind of studies is how a group of humans reaches an agreement on the phonology, lexicon and syntax. The improvements in computational tools led the researchers build and test models that have been ran computer simulations to answer the question. Although the models are mere reflections of the reality, the results have been often useful and insightful. This dissertation follows the same line and proposes a new model, tested in a game based simulation methodology. Besides, this work tries to fill the gap in the studies of lexicon compositionality and proposes a plausible explanation for the transition from single word naming to multi word naming. The direction of the results is in line with the previous research such as the emergence of a stable and communicative language. Moreover compositionality in lexicon is observed with a very simple bag of words syntax. The parameters influencing the results are analyzed in depth. Even though the model does not meet the standards of the real world, future work hints insightful facts about the transition from single word naming to syntax.

Download thesis.

A selection of Evolution of Language Resources

Biannual Evolution of Language Conference: evolang 2008

University of Edinburgh, Language Evolution and Computation Research Unit

A literature overview by Simon Kirby

The book Language Evolution by Morten Christiansen and Simon Kirby

A PhD thesis by Joris van Looveren, Design and Performance of Pre-Grammatical Language Games

Smoothing a Tera-word Language Model

2008-06-15T16:07:00.010+03:00

Deniz Yuret. In The 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-08: HLT) (Download PDF)
Download the software used in this study: glookup.tgz reads ngram patterns (possibly containing wildcards) from stdin, finds their counts in one pass from Google Web1T data, and prints the results. glookup.pl quickly searches for a given pattern in uncompressed Google Web1T data. Use the first one for bulk processing, the second one to get a few counts quickly.

Abstract: Frequency counts from very large corpora, such as the Web 1T dataset, have recently become available for language modeling. Omission of low frequency n-gram counts is a practical necessity for datasets of this size. Naive implementations of standard smoothing methods do not realize the full potential of such large datasets with missing counts. In this paper I present a new smoothing algorithm that combines the Dirichlet prior form of (Mackay and Peto, 1995) with the modified back-off estimates of (Kneser and Ney, 1995) that leads to a 31% perplexity reduction on the Brown corpus compared to a baseline implementation of Kneser-Ney discounting.

Olasılık ve kehanet

2008-04-24T21:24:00.002+03:00

Diyelim finans danışmanınız bir gün geldi ve borsanın yönünü
yüksek oranda doğru olarak tahmin edebilen bir algoritma bulduğunu
iddia etti. Algoritma girdi olarak son on günün hareketlerini
(aşağı ya da yukarı) alıyor ve çıktı olarak yarınki yönü (aşağı ya
da yukarı) belirliyor. Danışman son dört yılın datasını (yaklaşık
1000 gün) kullanarak algoritmayı geliştirdiğini ve aynı dönemde
simüle edildiğinde algoritmanın %90'ın üzerinde başarılı olduğunu
açıklıyor. Paranızı yatırır mısınız?

İpuçları:
1. Eğer borsanın yönü yazı tura ile belirlense bu algoritmadan nasıl bir performans beklerdiniz?
2. Eğer algoritma ilk iki yıla bakarak geliştirilse ve son iki yıl üzerinde test edildiğinde bu başarıyı gösterse fikriniz değişir miydi?
3. Eğer algoritma son 10 güne değil son 5 güne bakarak bu başarıyı gösterse fikriniz değişir miydi?

SRILM ngram smoothing notes

2007-12-31T16:39:00.013+02:00

This is a unix man page I wrote explaining the smoothing methods used in the SRILM statistical language modeling toolkit.

ngram-discount

NAME

ngram-discount - notes on the N-gram smoothing implementations in SRILM

NOTATION

a_z: An N-gram where a is the first word, z is the last word, and "_" represents 0 or more words in between.
p(a_z): The estimated conditional probability of the nth word z given the first n-1 words (a_) of an N-gram.
a_: The n-1 word prefix of the N-gram a_z.
_z: The n-1 word suffix of the N-gram a_z.
c(a_z): The count of N-gram a_z in the training data.
n(*_z): The number of unique N-grams that match a given pattern. "(*)" represents a wildcard matching a single word.
n1,n[1]: The number of unique N-grams with count = 1.

DESCRIPTION

N-gram models try to estimate the probability of a word z in the context of the previous n-1 words (a_), i.e., Pr(z|a_). We will denote this conditional probability using p(a_z) for convenience. One way to estimate p(a_z) is to look at the number of times word z has followed the previous n-1 words (a_):

(1) p(a_z) = c(a_z)/c(a_)

This is known as the maximum likelihood (ML) estimate. Unfortunately it does not work very well because it assigns zero probability to N-grams that have not been observed in the training data. To avoid the zero probabilities, we take some probability mass from the observed N-grams and distribute it to unobserved N-grams. Such redistribution is known as smoothing or discounting.

Most existing smoothing algorithms can be described by the following equation:

(2) p(a_z) = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z)

If the N-gram a_z has been observed in the training data, we use the distribution f(a_z). Typically f(a_z) is discounted to be less than the ML estimate so we have some leftover probability for the z words unseen in the context (a_). Different algorithms mainly differ on how they discount the ML estimate to get f(a_z).

If the N-gram a_z has not been observed in the training data, we use the lower order distribution p(_z). If the context has never been observed (c(a_) = 0), we can use the lower order distribution directly (bow(a_) = 1). Otherwise we need to compute a backoff weight (bow) to make sure probabilities are normalized:

 Sum_z p(a_z) = 1

Let Z be the set of all words in the vocabulary, Z0 be the set of all words with c(a_z) = 0, and Z1 be the set of all words with c(a_z) > 0. Given f(a_z), bow(a_) can be determined as follows:

(3) Sum_Z  p(a_z) = 1
 Sum_Z1 f(a_z) + Sum_Z0 bow(a_) p(_z) = 1
 bow(a_) = (1 - Sum_Z1 f(a_z)) / Sum_Z0 p(_z)
         = (1 - Sum_Z1 f(a_z)) / (1 - Sum_Z1 p(_z))
         = (1 - Sum_Z1 f(a_z)) / (1 - Sum_Z1 f(_z))

Smoothing is generally done in one of two ways. The backoff models compute p(a_z) based on the N-gram counts c(a_z) when c(a_z) > 0, and only consider lower order counts c(_z) when c(a_z) = 0. Interpolated models take lower order counts into account when c(a_z) > 0 as well. A common way to express an interpolated model is:

(4) p(a_z) = g(a_z) + bow(a_) p(_z)

Where g(a_z) = 0 when c(a_z) = 0 and it is discounted to be less than the ML estimate when c(a_z) > 0 to reserve some probability mass for the unseen z words. Given g(a_z), bow(a_) can be determined as follows:

(5) Sum_Z  p(a_z) = 1
 Sum_Z1 g(a_z) + Sum_Z bow(a_) p(_z) = 1
 bow(a_) = 1 - Sum_Z1 g(a_z)

An interpolated model can also be expressed in the form of equation (2), which is the way it is represented in the ARPA format model files in SRILM:

(6) f(a_z) = g(a_z) + bow(a_) p(_z)
 p(a_z) = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z)

Most algorithms in SRILM have both backoff and interpolated versions. Empirically, interpolated algorithms usually do better than the backoff ones, and Kneser-Ney does better than others.

OPTIONS

This section describes the formulation of each discounting option in ngram-count(1). After giving the motivation for each discounting method, we will give expressions for f(a_z) and bow(a_) of Equation 2 in terms of the counts. Note that some counts may not be included in the model file because of the -gtmin options; see Warning 4 in the next section.

Backoff versions are the default but interpolated versions of most models are available using the -interpolate option. In this case we will express g(a_z) and bow(a_) of Equation 4 in terms of the counts as well. Note that the ARPA format model files store the interpolated models and the backoff models the same way using f(a_z) and bow(a_); see Warning 3 in the next section. The conversion between backoff and interpolated formulations is given in Equation 6.

The discounting options may be followed by a digit (1-9) to indicate that only specific N-gram orders be affected. See ngram-count(1) for more details.

-cdiscount D

Ney's absolute discounting using D as the constant to subtract. D should be between 0 and 1. If Z1 is the set of all words z with c(a_z) > 0:

 f(a_z)  = (c(a_z) - D) / c(a_)
 p(a_z)  = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z) ;Eq.2
 bow(a_) = (1-Sum_Z1 f(a_z)) / (1-Sum_Z1 f(_z))  ;Eq.3

With the -interpolate option we have:

 g(a_z)  = max(0, c(a_z) - D) / c(a_)
 p(a_z)  = g(a_z) + bow(a_) p(_z) ;Eq.4
 bow(a_) = 1 - Sum_Z1 g(a_z)      ;Eq.5
         = D n(a_*) / c(a_)

The suggested discount factor is:

 D = n1 / (n1 + 2*n2)

where n1 and n2 are the total number of N-grams with exactly one and two counts, respectively. Different discounting constants can be specified for different N-gram orders using options -cdiscount1, -cdiscount2, etc.

-kndiscount and -ukndiscount

Kneser-Ney discounting. This is similar to absolute discounting in that the discounted probability is computed by subtracting a constant D from the N-gram count. The options -kndiscount and -ukndiscount differ as to how this constant is computed.
The main idea of Kneser-Ney is to use a modified probability estimate for lower order N-grams used for backoff. Specifically, the modified probability for a lower order N-gram is taken to be proportional to the number of unique words that precede it in the training data. With discounting and normalization we get:

 f(a_z) = (c(a_z) - D0) / c(a_)  ;; for highest order
 f(_z)  = (n(*_z) - D1) / n(*_*) ;; for lower orders

where the n(*_z) notation represents the number of unique N-grams that match a given pattern with (*) used as a wildcard for a single word. D0 and D1 represent two different discounting constants, as each N-gram order uses a different discounting constant. The resulting conditional probability and the backoff weight is calculated as given in equations (2) and (3):

 p(a_z)  = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z) ;Eq.2
 bow(a_) = (1-Sum_Z1 f(a_z)) / (1-Sum_Z1 f(_z))  ;Eq.3

The option -interpolate is used to create the interpolated versions of -kndiscount and -ukndiscount. In this case we have:

 p(a_z) = g(a_z) + bow(a_) p(_z)  ;Eq.4

Let Z1 be the set {z: c(a_z) > 0}. For highest order N-grams we have:

 g(a_z)  = max(0, c(a_z) - D) / c(a_)
 bow(a_) = 1 - Sum_Z1 g(a_z)
         = 1 - Sum_Z1 c(a_z) / c(a_) + Sum_Z1 D / c(a_)
         = D n(a_*) / c(a_)

Let Z2 be the set {z: n(*_z) > 0}. For lower order N-grams we have:

 g(_z)  = max(0, n(*_z) - D) / n(*_*)
 bow(_) = 1 - Sum_Z2 g(_z)
        = 1 - Sum_Z2 n(*_z) / n(*_*) + Sum_Z2 D / n(*_*)
        = D n(_*) / n(*_*)

The original Kneser-Ney discounting (-ukndiscount) uses one discounting constant for each N-gram order. These constants are estimated as

 D = n1 / (n1 + 2*n2)

where n1 and n2 are the total number of N-grams with exactly one and two counts, respectively.
Chen and Goodman's modified Kneser-Ney discounting (-kndiscount) uses three discounting constants for each N-gram order, one for one-count N-grams, one for two-count N-grams, and one for three-plus-count N-grams:

 Y   = n1/(n1+2*n2)
 D1  = 1 - 2Y(n2/n1)
 D2  = 2 - 3Y(n3/n2)
 D3+ = 3 - 4Y(n4/n3)

Warning:

SRILM implements Kneser-Ney discounting by actually modifying the counts of the lower order N-grams. Thus, when the -write option is used to write the counts with -kndiscount or -ukndiscount, only the highest order N-grams and N-grams that start with <s> will have their regular counts c(a_z), all others will have the modified counts n(*_z) instead. See Warning 2 in the next section.

-wbdiscount

Witten-Bell discounting. The intuition is that the weight given to the lower order model should be proportional to the probability of observing an unseen word in the current context (a_). Witten-Bell computes this weight as:

 bow(a_) = n(a_*) / (n(a_*) + c(a_))

Here n(a_*) represents the number of unique words following the context (a_) in the training data. Witten-Bell is originally an interpolated discounting method. So with the -interpolate option we get:

 g(a_z) = c(a_z) / (n(a_*) + c(a_))
 p(a_z) = g(a_z) + bow(a_) p(_z)   ;Eq.4

Without the -interpolate option we have the backoff version which is implemented by taking f(a_z) to be the same as the interpolated g(a_z).

 f(a_z)  = c(a_z) / (n(a_*) + c(a_))
 p(a_z)  = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z) ;Eq.2
 bow(a_) = (1-Sum_Z1 f(a_z)) / (1-Sum_Z1 f(_z))  ;Eq.3

-ndiscount

Ristad's natural discounting law. See Ristad's technical report "A natural law of succession" for a justification of the discounting factor. The -interpolate option has no effect, only a backoff version has been implemented.

         c(a_z)  c(a_) (c(a_) + 1) + n(a_*) (1 - n(a_*))
 f(a_z)= ------  ---------------------------------------
         c(a_)        c(a_)^2 + c(a_) + 2 n(a_*)

 p(a_z)  = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z) ;Eq.2
 bow(a_) = (1-Sum_Z1 f(a_z)) / (1-Sum_Z1 f(_z))  ;Eq.3

-count-lm

Estimate a count-based interpolated LM using Jelinek-Mercer smoothing (Chen & Goodman, 1998), also known as "deleted interpolation." Note that this does not produce a backoff model; instead of count-LM parameter file in the format described in ngram(1) needs to be specified using -init-lm, and a reestimated file in the same format is produced. In the process, the mixture weights that interpolate the ML estimates at all levels of N-grams are estimated using an expectation-maximization (EM) algorithm. The options -em-iters and -em-delta control termination of the EM algorithm. Note that the N-gram counts used to estimate the maximum-likelihood estimates are specified in the -init-lm model file. The counts specified with -read or -text are used only to estimate the interpolation weights.

-addsmooth D

Smooth by adding D to each N-gram count. This is usually a poor smoothing method, included mainly for instructional purposes.

 p(a_z) = (c(a_z) + D) / (c(a_) + D n(*))

default

If the user does not specify any discounting options, ngram-count uses Good-Turing discounting (aka Katz smoothing) by default. The Good-Turing estimate states that for any N-gram that occurs r times, we should pretend that it occurs r' times where

 r' = (r+1) n[r+1]/n[r]

Here n[r] is the number of N-grams that occur exactly r times in the training data.
Large counts are taken to be reliable, thus they are not subject to any discounting. By default unigram counts larger than 1 and other N-gram counts larger than 7 are taken to be reliable and maximum likelihood estimates are used. These limits can be modified using the -gtnmax options.

 f(a_z) = (c(a_z) / c(a_))  if c(a_z) > gtmax

The lower counts are discounted proportional to the Good-Turing estimate with a small correction A to account for the high-count N-grams not being discounted. If 1 <= c(a_z) <= gtmax:

                   n[gtmax + 1]
  A = (gtmax + 1) --------------
                      n[1]

                          n[c(a_z) + 1]
  c'(a_z) = (c(a_z) + 1) ---------------
                            n[c(a_z)]

            c(a_z)   (c'(a_z) / c(a_z) - A)
  f(a_z) = --------  ----------------------
             c(a_)         (1 - A)

The -interpolate option has no effect in this case, only a backoff version has been implemented, thus:

 p(a_z)  = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z)  ;Eq.2
 bow(a_) = (1-Sum_Z1 f(a_z)) / (1-Sum_Z1 f(_z))   ;Eq.3

FILE FORMATS

SRILM can generate simple N-gram counts from plain text files with the following command:

 ngram-count -order N -text file.txt -write file.cnt

The -order option determines the maximum length of the N-grams. The file file.txt should contain one sentence per line with tokens separated by whitespace. The output file.cnt contains the N-gram tokens followed by a tab and a count on each line:

 a_z <tab> c(a_z)

A couple of warnings:

Warning 1: SRILM implicitly assumes an <s> token in the beginning of each line and an </s> token at the end of each line and counts N-grams that start with <s> and end with </s>. You do not need to include these tags in file.txt.
Warning 2: When -kndiscount or -ukndiscount options are used, the count file contains modified counts. Specifically, all N-grams of the maximum order, and all N-grams that start with <s> have their regular counts c(a_z), but shorter N-grams that do not start with <s> have the number of unique words preceding them n(*a_z) instead. See the description of -kndiscount and -ukndiscount for details.

For most smoothing methods (except -count-lm) SRILM generates and uses N-gram model files in the ARPA format. A typical command to generate a model file would be:

 ngram-count -order N -text file.txt -lm file.lm

The ARPA format output file.lm will contain the following information about an N-gram on each line:

 log10(f(a_z)) <tab> a_z <tab> log10(bow(a_z))

Based on Equation 2, the first entry represents the base 10 logarithm of the conditional probability (logprob) for the N-gram a_z. This is followed by the actual words in the N-gram separated by spaces. The last and optional entry is the base-10 logarithm of the backoff weight for (n+1)-grams starting with a_z.

Warning 3: Both backoff and interpolated models are represented in the same format. This means interpolation is done during model building and represented in the ARPA format with logprob and backoff weight using equation (6).
Warning 4: Not all N-grams in the count file necessarily end up in the model file. The options -gtmin, -gt1min, ..., -gt9min specify the minimum counts for N-grams to be included in the LM (not only for Good-Turing discounting but for the other methods as well). By default all unigrams and bigrams are included, but for higher order N-grams only those with count >= 2 are included. Some exceptions arise, because if one N-gram is included in the model file, all its prefix N-grams have to be included as well. This causes some higher order 1-count N-grams to be included when using KN discounting, which uses modified counts as described in Warning 2.
Warning 5: Not all N-grams in the model file have backoff weights. The highest order N-grams do not need a backoff weight. For lower order N-grams backoff weights are only recorded for those that appear as the prefix of a longer N-gram included in the model. For other lower order N-grams the backoff weight is implicitly 1 (or 0, in log representation).

BUGS

Work in progress.

AUTHOR

Verimli Düşünce Alışkanlıkları

2007-12-16T15:42:00.002+02:00

TÜSİAD'ın Eleştirel Düşünce Üzerine Raporundan
Özet: Belirsiz bir gelecek karşısında doğru kararlar alabilmek için
elimizdeki bilgilerden uygun sonuçlara ulaşabilmemiz gerekir.
Bunun için önemli problemleri ilk başta keşfetmeli ve öncelik
sırasına koyabilmeli, yaratıcı çözümler üretebilmeliyiz. Bu
çözümler arasında seçim yapabilmek için arkalarındaki varsayımları
ve getirdikleri sonuçları görerek doğruluklarını tespit edebilmeli
ve farklı çözümlerin destekledikleri çelişen değerler arasında
denge kurabilmeliyiz. Doğru düşünme konusunda bir eğitim programı
planlarken hedef belirlemek, tam olarak ne istediğimizi anlamak
önemlidir düşüncesindeyim. Mantık, bilim, hukuk gibi disiplinler
fikirleri değerlendirme konusunda kendilerine özgü düşünce
yöntemleri geliştirmiştir. Bu raporda amacım farklı disiplinlerin
bize kazandırdıkları bu yöntemleri örneklendirmek, bu örneklerle
geliştirilebilecek eğitim programları için değerlendirme
kriterleri oluşturmaktır. Raporun sonundaki ekte ise düşünce
eğitimi konusunda dünyadan bulabildiğim uygulamaları
özetleyeceğim.

DARPA Urban Challenge

2007-11-03T21:18:00.002+02:00

Bir süredir heyecanla takip ettiğim bir yarışmadan bahsetmek
istedim. DARPA uzun zamandır kendi kendine şoförsüz gidebilen
arabalar geliştirmek istiyor: http://www.darpa.mil/grandchallenge

Bu amaçla 2004 ve 2005'de iki yarışma düzenlediler. İlk yarışmada
150 millik çöl parkurunu sağ salim bitirebilen bir araç çıkmadı.
İkinci yarışmada ise 4-5 araba verilen zaman süresi içerisinde
parkuru tamamladılar. Birinci olan Stanford takımından Sebastian
Thrun'un konuşması izlemeye değer:

http://video.google.com/videoplay?docid=8594517128412883394&q=engedu

Bir sene içinde Stanford ve CMU'nun gösterdiği gelişmeyi görünce
ben 2020'lerde ise giderken araba kullanmayacağımıza kani oldum.

Bu sene üçüncü yarışma düzenleniyor. Bu sefer çölde değil şehir
içinde trafikte yarışacak katılanlar. MİT ilk kez katılıyor.
Yarışma bugün 8am'de (California time). Elemelerden görüntüler
için aşağıdaki siteyi tavsiye ederim:

http://www.tgdaily.com/content/view/34686/113/

King Kong ve Fizik

2007-10-21T21:11:00.000+03:00

Hollywood filmlerinde görsel efektler için küçük maketler sıkça
kullanılır. Örneğin bir evin patlamasını çekmek için gerçek bir
evi parçalamak yerine küçük bir maket patlatılıp sonra film
yavaşlatıldığında doğru izlenimi verir.

Gelgelelim içerisinde su olan sahnelerde bu numara çalışmıyor.
Water world filmi gelmiş geçmiş en çok para kaybeden filmlerden
biri oldu bu yüzden, çünkü sahnelerin çoğu gerçek boyutta şu
üzerinde çekilmek zorunda idi. Bir küvete küçük kayıklar koyup
biraz suyu çalkalayın. Filme çekip sonra yavaşlatın. Dalgaların
ve hareketlerin çok gerçekçi görünmediklerini farkedeceksiniz.
Emrah'ın bahsettiği transformasyonlar nokta kütlelerden oluşan ve
sadece yerçekiminin etkili olduğu sistemler için 100% çalışıyor,
ama suyun akışkanlığı işi bozuyor.

Bu örneği öğrendiğimden beri bu tip simetrilerin korunduğu ya da
bozulduğu örnekler hep ilgimi çekmekte. Geçenlerde canlıların
boyutlarıyla ilgili çok güzel iki yazı keşfettim:

1. Favori bilim adamlarımdan JBS Haldane'nin hayvanların boyutlarının getirdiği fiziksel sınırlamalarla ilgili bir yazısı.

2. Bu fiziksel sonuçların ucuz hollywood sci-fi filmlerindeki devlere ve cücelere uygulanması.

Özetle canlıları düşünürken temel kavram şu: bir yaratığın boyunu
orantılı olarak iki katına çıkardığınızda, yüzey alanları dört
katına, hacim ve kütleler sekiz katına çıkıyor. Bunun ilginç
etkileri var. Örneğin büyük hayvanlar yüksek yerlerden
bırakıldıklarında daha hızlı düşüyorlar (Aristo'ya geri mi döndük
ne :) Sebebi yerçekiminin uyguladığı kuvvetin kütle ile ama hava
direncinin alan ile orantılı olması. Dolayısıyla yüksekten atlayan
bir insan olurken, bir fareye hiç birşey olmuyor (terminal
velocity 10km/h gibi). Bir at ise çorbaya dönüyor - eskiden
bizanslılar katapultlarla hastalıklı atları kale duvarlarından
içeriye fırlatıp hastalık yayarlarmış işgal sırasında. Filleri
hayvanat bahçelerinde hapis tutan etraflarındaki zayıf çitler
değil (onlar insanları dışarıda tutmak için), kazılmış olan 1m'lik
hendek (fil oraya düşerse hayatta kalamayacağını biliyor).

Diğer örnekleri kızım Asya'da (20 aylık) gözleyebiliyorum. Çok
üşüyor (enerji üretimi kütle ile, işi kaybı ise deri yüzeyiyle
doğru orantılı), dolayısıyla çok yiyor (orantılı olarak benim
günde 15-20 lt süt içmem gibi), ve ağırlığına göre çok güçlü (kas
ve kemik gücü kesit yüzey alanlarıyla, ağırlık ise hacimle
orantılı).

Bu basit ilişkileri kullanarak King Kong'un niye mümkün olmadığını
(ilk zıpladığında tüm kemikleri kırılırdı), Brontosaurus'un niye
kafasını yere yakın tutmak zorunda olduğunu (yukarıya uzatsa bacak
damarları sıvı basıncına dayanamayıp patlar, beynine kan çıkmadığı
için bayılırdı), dev böceklerin niye var olmadığını (akciğerleri
olmadığı için hava almaları özmosa bağlı, oksijen o kadar derine
penetre etmiyor), insanların niye sihirli ışınlarla mikroskopik
boyutlara küçültülemeyeceğini (brownian motion, ışığın dalga boyu,
enerji üretimi vs vs) açıklayabiliyoruz.

Ne dersiniz, fizik 101 finalinde sorayım mı bunları bizim
öğrencilere? ;)

Simetri üzerine

2007-10-21T21:09:00.000+03:00

Simetri üzerine Emrah'ın bir yazısının düşündürdüğü bazı fikirler:

1. Enerji, momentum ve açısal momentumun korunumunu zaman ve mekan
simetrileriyle açıklama konusu: bunu hep fizikçi arkadaşlardan
duyarım ama bir türlü derivasyonunu göremedim, bunun hepimizin
anlayacağı basit bir derivasyonu var mı? Varsa niye liselerde bunu
öğretmezler?

2. Simetri kavramı matematik ve fizikte başlı başına bir eğitim
konusu olabilir. Burada sadece not olarak simetrinin bu bağlamda
günlük değil genelleştirilmiş anlamıyla, yani "yapılan bir
değişiklikten sonra ilgilendiğimiz şeylerin aynı kalması" olarak
kullanıldığını not düşmek isterim. Ama hala "simetri kaybı" gibi
bazı terimlerin tam ne anlama geldiğini tam anlamış değilim.

3. Bilimin başarısı lokal deneylerin bize çok uzak ve çok farklı
ortamlarla ilgili geçerli bilgiler vermesine dayalı diyoruz.
Psikoloji ve sosyolojinin başarısızlığının sebebini burada
arayabilir miyiz? Örneğin bir insan, bir ülke, ya da bir tarih
için gözlediğimiz şartlar başka bir insan, ülke, veya tarihte aynı
sonucu vermiyorlar genelde (tabi "şartlar"ı yeterince ayrıntılı
almamamızdan olabilir). Dolayısıyla ortada basit bir insan, yer,
ve zaman simetrisi yok gibi - bu da bilimin elindeki en güçlü
araçlardan birini alıyor. Tarih ve ekonomi gibi bilimlerde "deney"
yapmanın zorluğundan hep bahsedilir, ama belki esas problem deney
yapabilsek bile bunların benzer sonuçlar vermeyecek oluşu. Bu
olaylara belli simetrilerin olduğu seviyelerde bakmadığımız sürece
durum ümitsiz gibi görünüyor.

4. Neyin bilimsel olarak açıklanabilir neyin açıklanamaz olduğu
konusunda önceki yazdılarımda "algorithmic complexity"'ye gönderme
yaptım. Bir dizi (olaylar, sayılar, bitler dizisi), ya bir miktar
açıklanabilir (compress edilebilir, predict edilebilir), ya da
tamamiyle random'dur (random'luğun tanımını böyle yapıyor
teori). Ama bu potansiyel olarak uzayabilecek tartışmayı sonraya
bırakıyorum.

Düşünce deneylerine iyi bir örnek

2007-10-21T20:42:00.002+03:00

Üniversitede fizik hocamdan duyduğum bir düşünce deneyi hikayesi
geldi aklıma. Düşünce deneylerinin iyi düşünüldüğü zaman ne kadar
etkili olabileceğine bir örnek:

Aristo'nun fiziğinde düz giden cisimler ittirilmezlerse bir süre
sonra dururlar. İki cisim bırakıldığında ağır olan önce
düşer. Bunlar günlük deneyimimizle tutarlı gibi görünen
sonuçlar. Ayrıntılı bir deney yapılmadığında bir çocuğa da
sorsanız bu cevapları alırsınız basit düşünce deneylerinden. Bugün
Aristo'yu suçluyoruz, adam niye bir kuleye çıkıp da denememiş
diye. Ama suç gerçekten düşünce deneyinde mi?

Dikkatle tasarlanmış bir düşünce deneyi bize gerçeği gösterebilir.
Örneğin Pisa kulesinin tepesinden bir tuğla bıraktığımızda
diyelim yere düşmesi 10 saniye sürsün. Birincisine eş ikinci bir
tuğla bıraktığımızda onun da 10 saniyede düşeceğine herhalde
Aristo'nun da bir şüphesi yoktu. Peki iki tuğlayı aynı anda
bıraksak? Birbirlerini etkilediklerini düşünmediğimize göre yine
birlikte on saniye sonra yere çarpacaklar. Şimdi çarpıcı noktaya
geldik: iki eş tuğlanın arasına bir damla japon yapıştırıcısı
damlatıp bunları iki kat büyüklükte tek bir kütle haline
getirelim. Bu yeni kütleyi bıraktığımızda kaç saniyede düşmesini
bekliyoruz? Bunun bir önceki deneyden gerçekten bir farkı var mı?
Birinde iki tuğla yanyana düşüyor, diğerinde yine yanyana
birbirlerine yapışık düşüyorlar. Sanırım Aristo vaktiyle bu
deneyi düşünse Galileo'dan 2000 yıl önce doğru çözümü gorebilirdi.

Bilim budalalığı

2007-10-21T20:25:00.002+03:00

Bilim budalalığı konusunda geçenlerde seyrettiğim Adam Curtis'in
Pandora's Box belgeselini tavsiye ederim.

Altı bölümlük bu belgeselde yapımcı, komünist Rusya'nın rasyonel
ve mekanik bir toplum kurma hayalinden, atomik enerji konusunda
uğradığımız fiyaskolara, çevre sorunlarından, ekonomistlerin
skandallarına kadar uzanan geniş bir yelpazede bilimin bize
yaşattığı hayal kırıklıklarını incelemiş.

Anlattığı altı hikayenin hepsinde benim görebildiğim senaryo
benzer: belki geliştirilip olgunlaştırılması için on yıllar ya da
yüz yıllar gerekebilecek teknolojiler bilim adamları tarafından
kişisel sebeplerle over-sell ediliyor. Politikacılar gördükleri
prototiplere güvenip halka tutamayacakları sözler
veriyorlar. Sonuçta büyük bir zaman baskısı altında olgunlaşmamış
teknolojiler üretime geçiyor. Riskler hakkında yalanlar
söyleniyor, doğruyu söylemeye çalışan dürüst bilim adamları
susturuluyor. Sonunda beklenen felaket gerçekleştiğinde insanlar
bilimi suçluyorlar.

Bu senaryonun gösterdiği problemin çözümünü bilimde değil
sosyoloji ve politikada aramak gerek diye düşünüyorum. Bilim
sonuçta sadece "bilmek" kökünden gelen bir kelime, bilmenin de
kimseye bir zararı yok (eğer Popper'ın açık toplumuna, Mill'in
düşünce özgürlüğüne inanıyorsanız). Tüm felaketler bilmediğimiz
konularda biliyormuş gibi davranmaktan ya da bildiğimiz bazı
şeyleri saklamaktan geliyor.

Nuray Mert'in bilimle ilgili yazısını ise neresinden tutayım
bilemiyorum. Memduh sanki sırf benim tüylerimi diken diken etmek
amacıyla göndermiş. Sanki çok bilime gark olmuş bir ülkeymişiz
gibi... Aşağıda bir iki kavram karmaşası ve factual error
konusunda yorum yapacağım sadece:

1. "bilimin nefesinin tükendiği konular": burada bugünkü bilimin
açıklayamadığı şeyler mi kasıt, yoksa prensipte açıklanamayacak
şeyler mi emin değilim. Her halükarda yazının genelinden bilimsel
yöntemle, günümüzün bilimsel bilgilerinin birbiriyle
karıştırıldığı izlenimindeyim. Bugün bildiklerimizin yanlışlığının
her an ispatlanabileceği bilimin tanımında var zaten. Ama
yapabildiğimizin en iyisi bu, daha iyisini bilen varsa hodri
meydan.

2. "bu gayret bugüne kadar varoluşa dair temel soruları çözmekte
işe yaramadı" ilginç bir gözlem. Sonuçta modern insan 150,000
yıldır bu dünyada dolaşıyor. Üç yüz yıllık bir çaba sonucu evrenin
en uzak noktalarıyla, maddenin en küçük yapıtaşlarıyla ilgili
fikirler üretiyor, cansız moleküllere can verme noktasına
geliyoruz. Nuray hanımı tatmin etmek için hangi "temel sorulara"
cevap vermemiz gerekecek acaba?

3. "Aydınlanma felsefesi, bilimsel düşünceyi temel alan dünya
görüşünün, toplumsal siyasal meseleleri de halledeceğini iddia
ediyor, umuyordu. Öyle olmadı." Bu, eğer cümlenin öznesini yanlış
okumadıysam "aydınlanma felsefesi" nin bir problemi, bilimin değil
:) Tabi iki paragraf sonra yazarımız bilime karşı felsefeyi
savunarak benim kafamı temelli karıştırıyor: "bu sorular hâlâ
felsefi düzeyde tartılması gereken konularmış."

Toplumsala bilimin uygulanması konusu yukarıda bahsi geçen
belgeselin ilk bölümünde Rusya örneğiyle ele alınıyor. Bilim şu
anda gerek insan psikolojisini gerek toplum davranışını başarılı
bir şekilde açıklamaktan çok uzak. Bu gerçeği çarpıtıp
bilmediğimiz konularda birşeyler biliyormuşuz gibi davranmak ancak
insanların zayıflığı ve irrasyonelliğinin sonucu, fazla
rasyonelliğin değil.

4. "İnsanlar, ortaçağda da birbirlerinin gözünü oyuyordu, bugün de
bu noktadan uzaklaşmış falan değiller." Bu noktada Steven
Pinker'in vahşetin tarihsel düşüşü ile ilgili TED konuşmasını
tavsiye ediyorum. Burada Nuray hanımın söyledikleri tamamiyle
yanıltıcı. 20. yüzyılın dünya savaşlarını bile düşündüğümüzde
eğer ölüm oranı eski dünyanın kabile savaşları ile aynı olsaydı
100 milyon değil 2 milyar insanın ölmesini beklerdik. Tanıdığınız
erkeklerin yarısının 30 yaşını fazla geçmeden başka bir erkeğin
eliyle ölmesi normdu birkaç yüzyıl öncesine kadar.

5. "Okullarda bilimsel bilgi öğretilmesin diyen yok, ama bilimsel
bilgi mutlak gerçek yerine konulmasın deme hakkımız yok mu?"
Bilimsel bilginin mutlak gerçek olduğunu iddia eden var mı acaba?
Bunun bilimin tanımına aykırı olduğunu açıklayarak okuyucularımın
zamanını almayacağım.

Belki de beni en rahatsız eden yazarın alternatif sunmayarak olan
gelişmeleri tek taraflı eleştirmesi. Onu değil de şunu yapsaydık
demiyor, geleceğe yönelik bir tavsiyede bulunmuyor. Hayata dair
bilgilenme çeşitlerine başka başarılı örnekler sunmuyor.
İnsanların ve kurumların yapılarından kaynaklanan bir takım
sorunları bilimin suçuymuş gibi sunup her türlü alternatif
crackpot felsefeye yeşil ışık yakıyor. Tam da günümüzde
ihtiyacımız olan bakış açısı (!).

Nedenciler ve Nasılcılar

2007-10-21T20:22:00.001+03:00

Nedenci nasılcı ayrımı konusunda bir süredir kafama takılan bir
soru var. Memduh'un deyimiyle:

> Ama galiba bütün bu sorgulamaların sonunda cevap ya
> (i) fiziksel bir sebebe bağlanacak, veya
> (ii) (bireyin. evrimin, Tanrının) aklıyla, isteğiyle olacak

Burada fiziksel bir sebepten kasıt eminim bugünkü bilimsel
bilgimizle sınırlı bir açıklama değil. Örneğin bugün evrende dört
ayrı kuvvet olduğunu düşünüyor tüm gözlemlerimizi bu dört kuvvetin
bir sonucu olarak açıklamaya çalışıyoruz. Ama yarın bu dört
kuvvetin açıklayamadığı bir deney yapılsa bu bilimin sonu olmaz,
ya beşinci bir kuvvet eklenir, ya da kuvvetlerin ötesinde bambaşka
bir kavram çatısı bulunur.

Bilimi bu geniş anlamıyla aldığımızda bir olgunun (örneğin bilinç
gibi) bilimsel yöntemle açıklanması ne demek önce ona bakalım:
Başarılı bir bilimsel açıklama bize o güne kadar yapılmış
gözlemlerle tutarlı ve gelecekte yapabileceğimiz gözlemlere
yönelik test edilebilir tahminlerde bulunabileceğimiz bir hipotez,
bir teori sunuyor. Dolayısıyla örneğin başarılı bir psikolojik
teori bulduğumuz zaman (şu an böyle bir teori henüz yok) bu benim
hangi koşullarda neyi isteyeceğimi, nelere inanacağımı, nasıl
davranacağımı prensipte başarılı şekilde tahmin etmemizi
sağlayabilir. Bu teoriyi kullanarak benzer özelliklere sahip
robotlar, simülasyonlar geliştirebiliriz vs.

Bu noktada ilk sorum şu: nedencilerin açıklama olarak
kastettikleri şey tam olarak nedir? Örneğin tanrı istedi de öyle
oldu, ya da ben istedim de öyle yaptım gibi ifadeler birer
açıklama mı? Eğer öyle ise bu iki grup insanın "açıklama" kavramı
ile kastettikleri çok ayrı şeyler. Dolayısıyla bu yanlış bir
dikotomi, iki grup aynı sorulara cevap aramıyor. Nedencilerin
açıklamalarında gelecekle ilgili tahminlerde bulunabilme isteği ya
da potansiyeli yok. Zaten böyle tahminlerde bulunabilsek (örneğin
bireylerin ya da Tanrı'nın yarın ne isteyeceği üzerine başarılı
bir teorimiz olsa), o zaman nasılcılardan bir farkımız kalmazdı.

Bir ihtimal nedenciler bazı şeylerin prensipte bilimsel yöntemle
açıklanamayacağına inanıyorlar. Peki o zaman bir olgunun bilimsel
yöntemle prensipte açıklanamaması ne demek? Örneğin Penrose
bilinci açıklamak için yeni kuantum özellikler ararken bugünkü
bilimin yetersiz olduğuna mı inanıyor, yoksa bilimin genel olarak
bilinci açıklayamayacağına mı? Bilimsel açıklama ve tahminlere bir
bakış açısı bugüne kadar gözlenmiş bir sayı dizisinin bundan
sonraki terimlerini tahmin etmek olarak özetlenebilir. Bu durumda
bu tahminin prensipte yapılamayacağını iddia etmek bu dizinin
tamamiyle rastgele (random) olduğunu iddia etmeye denk. Bu durumda
nedenciler Tanrı'nın ya da insan bilincinin bir seviyede püre
randomness'dan geldiğine mi inanıyorlar?

Diğer bir ihtimal, nedencilerin bilimsel açıklamalarla bir alıp
veremedikleri yok, sadece bu tip açıklamalar onları
ilgilendirmiyor, ya da onları tatmin etmiyor. Buna söyleyecek
birşey yok tabi, ama o zaman ortada kavramsal olarak önemli bir
dikotomi yerine kişisel tercihler var dememiz lazim...

Mehmet Ali Yatbaz, M.S. 2007

2007-10-01T12:54:00.007+03:00

Stretch: A Feature Weighting Method for The k Nearest Neighbor Algorithms
Mehmet Ali Yatbaz. M.S. Thesis, Koç University Department of Computer Engineering, October 2007.

Abstract: The k nearest neighbor learning algorithm (kNN) is one of the well studied nonparametric learning algorithms. kNN assumes that the underlying joint probability density function of the training set is unknown and it estimates the underlying joint probability density functions using the labeled data set (training set). Although this is a realistic assumption in terms of the real world problems, it introduces some limitations on the predictive
accuracy, the storage complexity and computational compexity of the kNN.

The goal of this thesis is to understand kNN and techniques that are used to increase the predictive accuracy of kNN. This thesis mainly focuses on the effect of the irrelevant features on the predictive accuracy of the kNN and introduces the Stretch method, a new preprocessing method to increase the predictive accuracy of kNN by doing linear transformation on the training data matrix. The method incrementally constructs a linear transformation that maximizes the nearest neighbor classification accuracy on the training set. At each iteration the method picks an instance from the data set, and computes a transformation that moves the instance closer to the instances with the same category and/or away from the instances in other categories. The composition of these iterative linear transformations can lead to statistically significant improvements in kNN learning algorithms.

Download PDF

Düşünce deneyleri

2007-09-26T15:29:00.000+03:00

Bu aralar bilinç üzerine ne varsa okuyorum. Tartışmaların çoğu
düşünce deneyleri üzerine dönüyor. Birkaç örnek vermek gerekirse:

* Eğer bir yarasa olsak kendimizi nasıl hissederdik?

* Star trek usulü bir scanner ile tüm atomlarınızı tarayıp sizi
başka bir yerde yeniden oluştursak hangi sız gerçek siz olurdunuz?

* Benimle aynı fiziksel konfigürasyona sahip olan (atomlar,
moleküller) ama içinde bir "ben" olmayan bir yaratık (zombie)
olabilir mi?

* Gelecekte beynin tüm sırlarını çözmüş olalım. Mary, bir renk
uzmanı, insanın renk algılarıyla ilgili bütün mekanizmaları en
ince ayrıntısına kadar biliyor olsun. Ama Mary ömrü boyunca siyah
beyaz bir odada oturup dünyayı siyah beyaz bir monitörden
izlesin. Sonunda bir gün dışarı çıkıp gerçek renkleri gördüğünde
yeni birşey öğrenir mi?

Beni bu konuda düşünmeye iten küçük bir deneyi blog'uma koydum:

http://denizyuret.blogspot.com/2007/09/hearing.html

Düşünce deneylerinin kötü tarafı fiziksel deneyler gibi
kendilerini tutarlı bir gerçeğe bağlayan güçlü bir bağ
olmaması. (Fiziksel gerçeğin neden tutarlı olduğu ayrı bir
tartışma konusu - elmanın dünyaya düşmesini sağlayan mekanizma ile
ayı dünyanın etrafında döndüren mekanizmanın aynı kurallarla
açıklanması, bu yüzyılda yaşamasak hayli şaşırtıcı olurdu.) O
zaman düşünce deneylerinin gördüğü fonksiyon birer sezgi pompası
(intuition pump) rolü oynayıp kafamızda zaten var olan bir takım
sezgileri daha ön plana çıkararak eldeki probleme uygulamamızı
sağlamak. Tabi başlangıçtaki sezgilerimiz yanlışsa vardığımız
sonuçlar da yanlış oluyor.

Tabi tüm düşünce deneyleri yukarıdakiler gibi yanıltıcı değil.
Einstein usulü fiziksel "gedankenexperiment" lar fiziksel olarak
yapılması mümkün olmayan (en azından o gün için) deneylerle
insanların düşüncelerini organize etmeye yarayabiliyorlar.

Yine de dikkatli olmak lazım. Sadece bazı filozofların zombie'ler
olduğunu hayal edebiliyor olması zombie'lerin gerçekten
olabileceğini ya da bilincin fizik dışı bir komponenti olduğunu
ispatlamıyor. Ya da bazı filozofların "hisseden robot"
yapılabileceğini hayal edemiyor olması da onların hayal gücünün
bir problemi, herhangi bir gerçeğin ispatı değil.

"Bir gün bir adaya düştüğünde..." diye başlayan düşünce
deneylerinde de problem hayal gücümüzün sınırları ile bağımlı
olmaları. Bir adaya düştüğümüzde gerçekten olabilecek pek çok şeyi
şu anki sınırlı deneyimimizle hayal edemiyor olabiliriz. Fiziksel
deneylerin güzelliği deneyi yapanın hayal gücüne bağımlı
olmamaları ve bazan hayal etmeyi aklımızdan geçirmediğimiz
sonuçlar verebilmeleri.

Belki bundan da önemlisi Galile'nin İtalya da 1650'de yaptığı
deneyin şu an İstanbul'da 2007'de (ya da Andromeda Galaksisinde,
bundan bir milyar yıl sonra) da aynı sonucu vermesi. Bunu biliyor
muyuz, inanıyor muyuz, iman mı ediyoruz orası tartisilir.

Hearing

2007-09-23T22:27:00.004+03:00

In his book "Auditory Scene Analysis", author Albert S. Bregman likens the ear canals to two narrow channels on the edge of a lake and sound waves to water waves:

"Your friend digs two narrow channels up from the side of the lake. Each is a few feet long, and a few inches wide, and they are spaced a few feet apart. Halfway up each one, your friend stretches a handkerchief and fastens it to the sides of the channel. As waves reach the side of the lake they travel up the channels and cause the two handkerchiefs to go into motion. You are allowed to look only at the handkerchiefs and from their motions to answer a series of questions: How many boats are there on the lake, and where are they? Which is the most powerful one? Which one is closer? Is the wind blowing? Has any large object been dropped suddenly into the lake?"

As impossible as this task sounds, it is analogous to the work performed by your auditory system.

Here is a small experiment. Listen to this first recording and try to guess what it is:

No, it is not some wild animal or an alien. It is just human speech (singing) and some instruments, slowed down. Here is the original, if you are curious:

Now try to listen to the first recording again and see if you can figure out what the words are and where they start and end. People in general do not have a good appreciation of how difficult the problems of perception are (unless they are trying to build a machine to solve these problems). We have been working on speech recognition for decades but the best programs still do not perform very well except in very restricted contexts. Yet we recognize speech so effortlessly that it is difficult to see what the big deal is. Trying to recognize the words in the first recording may help you appreciate the computer's difficulty.

The thing that struck me about the first recording when I first heard it was how different it "felt" than human speech. Although it contained exactly the same information as the original its "quale" was different in philosopher-speak. This reminded me of a famous thought experiment devised by philosopher Frank Jackson: Mary the color scientist.

Mary lives in the far future when neuroscience is complete and scientists know everything there is to know about the physical processes in the brain. She has studied and learned everything there is to know about color perception: the optics of the eye, the properties of colored objects, the processing of color information in the visual system, and how this information leads to actions, memories, feelings etc. But Mary has been brought up all her life in a black and white room, she has never seen any colors at all. One day Mary is let out of her black and white room and sees colors for the first time. What happens? Does she learn anything new?

Frank Jackson argues that she obviously learns something fundamentally new: what red is like, its raw feel, its quale.

When I listen to the first recording I think of an alien speech scientist, trying to decipher the message hidden in the signal. The alien can train itself and become an expert at recognizing the words upon hearing the signal. But will it ever get the same "quale" as we get when we listen to the original recording?

Philosopher Dan Dennett argues that there are no such things as qualia and Mary will not learn anything new when she sees the colors for the first time. That is, of course, if we take the premises seriously: that she knows EVERYTHING there is to know about color perception. As counterintuitive as this sounds, I find that when the subject is the "mind", familiar and intuitive is usually wrong.

Tanrının işine karışmak

2007-07-25T14:59:00.002+03:00

Nicholas D. Kristof taşıyıcı annelik ve genetik manipülasyonlar
konusunda yazdığı yazısını şöyle bitiriyor:

"What should cross the line into illegality is fiddling with the
heritable DNA of humans to make them smarter, faster or more pious
or more deaf. That is playing God not just with a particular embryo
but with our species, and we should ban it."

"Playing God" deyimi bu tip tartışmalarda çok geçmeye başladı. Ne anlama geldiği belirsiz, içi boş, ama negatif duygular uyandıran ve dolayısıyla her türlü önyargıyı içinde barındırmaya açık bir deyim. Temiz argümanlar kullanmanın önemli olduğunu düşünüyorum ve Kristof'un yazısının bu testi geçtiğine çok emin değilim.

Bana Craig Venter'e son projesi için izin verip vermemeye karar veren
grubun içinde bütün büyük dinlerden temsilcilerin olmasını
hatırlatıyor. Temsilciler kendi inandıkları kitapları yorumlayıp
"cansızdan canlı yaratma" konusunda bir yasak olup olmadığına karar
vermeye çalıştılar. Din konusundaki görüşünüz ne olursa olsun, umarım
bu tip konularda karar verirken ne gibi kriterler kullanacağımızın
hepimizin üzerinde anlaşabileceğimiz şekilde daha net belirlenmesi
gerektiği konusunda bana katılıyorsunuzdur.

Bu kriterlerin ne olması gerektiği konusunda anlaşabilir miyiz?
Ekonomik kriterlerin daha dikkatli analizi çözümün bir parçası
olabilir. Dennett ve Drescher gibi filozofların üzerinde uğraştığı
"Getting ought from is", yani temel gerçeklerden başlayıp etik
prensiplere akıl yoluyla ulaşma projesi belki bir diğer parçası.

Problemin zor tarafı hedefin ne olduğunu belirlemek gibi geliyor bana.
Hedef tam olarak belirlendiğinde bunun uygulamaya nasıl döküleceği
bir sosyal mühendislik problemi. İnsanların neslinin sürdürülmesi,
refah içinde yaşanması, sağlık, mutluluk, nedir tam olarak amacımız.
Önümüzdeki yüzyılda transhümanistlerin rüyaları gerçek olmaya başlarsa
iki bin yıldır çok değişmeyen bazı temel hedefleri sorgulamamız
gerekecek mi?

Net bir hedef üzerinde anlaştığımızda ve bu hedefe bizi götürecek
mühendislik çözümler bulunduğunda "playıng God" gibi içi boş
terimlerle birbirimizi oyalamayı bırakacağız diye umuyorum.

The CoNLL 2007 Shared Task on Dependency Parsing

2007-06-28T16:31:00.005+03:00

Joakim Nivre, Johan Hall, Sandra Kübler, Ryan McDonald, Jens Nilsson, Sebastian Riedel and Deniz Yuret. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)

Abstract: The Conference on Computational Natural Language Learning features a shared task, in which participants train and test their learning systems on the same data sets. In 2007, as in 2006, the shared task has been devoted to dependency parsing, this year with both a multilingual track and a domain adaptation track. In this paper, we define the tasks of the different tracks and describe how the data sets were created from existing treebanks for ten languages. In addition, we characterize the different approaches of the participating systems, report the test results, and provide
a first analysis of these results.

Evrenin israfkarlığı

2007-06-26T15:23:00.001+03:00

İnsan genetiği belirlendiginde ilginç bir gerçek ortaya çıktı:
Proteinleri tanımlayıp özelliklerimizi belirleyen genler DNA'nın
sadece yüzde üçünü kaplıyorlar. Bu biraz israf gibi gelmiyor mu
insana?

1. Micro-RNA'leri kodlayan DNA bölümleri de var, fakat
micro-RNA'lerin sayısı protein kodlayan genlerin sayısı ile aynı
büyüklükte gibi. Micro-RNA'lerin boyları da daha küçük olduğundan
3% hadi çıkmış olsun 10%'a. Hala bir 90% var sanki "junk" olarak.

2. Tabi bu bölge başka şeyler kodlayabilir, RNA kodlayan yerlerin
birden fazla kopyası olabilir vs. Fakat DNA'de hiç birşey
kodlamadığı belli olan uzun tekrarlayan diziler olduğunu biliyorum
(ATATATATATA) gibi. İşten anlayanlarımız bunların DNA'nın ne
kadarını kapsadığını belki bize bulabilir.

3. İşin garibi bazı bakteriler bu konuda bizden çok daha verimli
kodlama yapıyor, DNA'larının neredeyse 100%'unu kullanıyorlar
(yanlış hatırlıyorsam düzeltin). 3% rakamı insanlara ve diğer
gelişmiş hayvanlara özel.

4. Konuyla alakası yok ama bazı basit bitkilerin insanlardan çok
daha fazla gene sahip olması da ilginç değil mi?

5. Peki insan vücudunun 60% su olmasına ne demeli.

6. Ya da atomların içinin 99.9999999% boş olmasına? Katı madde
dediğimiz şeylerin büyük oranda boş olması 20. yüzyıl fiziğinin en
ilginç bulgularından biri. Eğer çekirdek bir sinek ise,
elektronlar onun etrafında futbol sahası boyunda yörüngelerde
dolaşıyorlar.

7. Son olarak eğer çok-evrenli kuantum yorumları doğru ise evren
her an neredeyse sonsuz dala ayrılmakta, bu dalların her biri
diğerleri kadar gerçek, biz ise sadece bunlardan birini
algılayabiliyoruz (tabi diğer kopyalarımız diğerlerini
algılıyorlar) diğerleri ile ancak dikkatli fizik deneyleri
sırasında etkileşebiliyoruz. Ne büyük israf demek geliyor insanın
içinden. Ama elinde sonsuz miktarda kaynak olan bir Tanrı için
israf anlamsız bir kavram olmalı :)

Düşünceleri okuyabilmek

2007-06-26T14:25:00.002+03:00

Prague'daki Association for Computational Linguistics
konferansındayım. Açılış konuşmasını Mitch Marcus yaptı. Kendisi
"Machine Learning" alanındaki çalışmaları ve klasik ders kitabı
ile tanınır. Son zamanlarda uğraştığı işleri anlattı, ilginç
bulduğum için paylaşmak istedim:

Araştırmada beyninizi tarayan fMRI aletinin içine giriyorsunuz.
Karşınıza her on saniyede bir okumanız için bir kelime çıkıyor.
fMRI'in çektiği beyin aktivite filminizi gördüğünüz kelimelerle
ilişkilendirip daha sonra sadece beyin aktivitenizden düşündüğünüz
kelimeyi bulmaya çalışıyorlar.

İlk deneylerde iki grup kelime ile başlamışlar: araçlar
(tornavida, çekiç vs), ve yerler (ev, ofis vs). Modeller
düşündüğünüz kelimenin hangi sınıfa ait olduğunu 100% ayırt
edebiliyor. Tam olarak hangi kelimeyi düşündüğünüz konusunda şu an
performans biraz daha düşük. İnsandan insana değişmesine rağmen
70% - 95% arasında gibi sınırlı sayıda kelime kümeleri için. Daha
sonra yapılan deneyler kelime okuma yerine aynı objelerin
resimlerine bakma (performans bu durumda daha da iyi), resimlere
bakarken öğrenilen beyin aktiviteleriyle daha sonra okuduğunuz
kelimeleri tahmin etme (bu gözlenen aktivitenin tek bir modalıty'e
(yazı, ses, görüntü gibi) özel olmadığını ve gerçekten o
kavramları gösterdiğine işaret), bir insandan öğrenilen modellerle
diğer insanın ne düşündüğünü tahmin etme (performans biraz daha
düşse de hala çok fena değil), bir dilde kelimeler okuyarak
öğrenilen modellerle başka dilde düşünülen kelimeleri ayırt etme,
ilgili kelimelerden elde edilen bir modelle daha evvel görünmeyen
kelimeleri sınıflandırma vs gibi.

Tabi üç yaşından beri beyin okuma aletleri hayal eden bendeniz
için çok heyecan verici bir konuşmaydı. Türkiye'ye döner dönmez
Amerikan Hastanesine gidip fMRI aleti ile nasıl oynayabileceğimin
yollarını araştırmak istiyorum.

İşin ilginci herkes benim kadar heyecanlı değildi. Bazı
arkadaşların bu teknolojinin gideceği yerleri düşünüp çok rahatsız
olduklarını farkettim. fMRİ taşınabilir derecede küçülüp
hassasiyet düşünülen cümleleri ayırt edecek kadar artırıldığında
kafalarına aluminyum folyo sarıp dolaşmaları gerekecek.

Bense bu mahremiyet konusunda artık teslim olmuş durumdayım. Nasıl
olsa uzun vadede ümit yok, buna ne kadar erken alışırsak o kadar
iyi. İnsanlar kendi doğalarını kabul edip standartlarını ona göre
ayarlamalı. Internet trafiğinin 50% porno olacağını Tim Berners
Lee tahmin edemezdi herhalde. Ama başımıza taş yağdığı falan yok.

Bu konuda bildiğim bir David Brin ilginç birşeyler düşünüyor -
açılma güçlüler-güçsüzler, devlet-vatandaşlar vs arasında tek
yönlü olursa problem büyük. O tek yönü engelleyemeyeceğimize göre
en azından çift yönlü olması için bir kültür devrimine başlamamız
gerek. İngiltere'de sokak kameralarını izleyen karakollardaki
memurları vatandaşların da kameralarla izleyebilmesi önerisi
gibi. Neyse bu konu başka bir mesaj eder.

Bu teknolojinin beni heyecanlandıran getirileri ise saymakla
bitmez. Birincisi beyinde kavramların ve anlamların ne şekilde
saklandığı konusunda 2500 senedir herkes birşeyler atıp tutuyor,
hala en ufak bir fikrimiz yok. Önümüzdeki senelerde bu konuda
büyük ilerleme sağlanabilir. Kurzweil'in her zaman iddia ettiği
gibi Aİ'i önümüzdeki 50 yılda biz çözemesek de beyin resmetme
aletleri yeterince hassaslaştığında reverse-engineering daha kolay
bir çözüm olabilir. Daha yakın dönemde bilgisayarlar, internet,
ve hatta diğer insanlarla iletişimimiz için klavye, fare, cep
telefonu gibi gereçlere gerek kalmayabilir - beyne enjekte
edilecek küçük bir wireless internet çipi ile telepatı sonunda
gerçek olabilir. (Tabi call-waiting ve answering-machine benzeri
filtreler bu durumda daha da önem kazanıyor). Politika ve hukuk
konusundaki potansiyeller - yalan makineleri yerine sanığın
düşüncelerini okuyan bir laptop düşünün. Amerikan başkanı seçimi
kazandığında elini incile koyup standart laflar edeceğine,
seçmenler kafasını fMRİ'in içine sokup gerçekten ne düşündüğünü
öğrenmek isteyebilirler. Daha sayayım mi?

Targeted Textual Entailments - A Proposal

2007-06-25T22:58:00.003+03:00

1. Definition: A targeted textual entailment (TTE) task uses entailment questions to test a specific competence of a system, such as word sense disambiguation, semantic relation recognition, or parsing. Even if we do not know the best theory underlying a competence, we know what having that competence enables people to do. For example:

1.1 WSD
"They had a board meeting today."
==> "They had a committee meeting today." [yes]
==> "They had a plank meeting today." [no]

1.2 SemRel
"John opened the car door."
==> "The door is part of the car." [yes]
==> "The car produced the door." [no]

1.3 Parsing
"I saw the bird using a telescope."
==> "I used a telescope" [yes]
==> "The bird used a telescope" [no]

2. Motivation: Targeted textual entailment tasks address the following issues:

2.1 Currently most shared tasks use or favor a specific inventory, representation, or linguistic theory. In WSD, WordNet is often used as the sense inventory although everybody complains about it. We have FrameNet, Propbank, Nombank, various logical formalisms and different sets of noun-noun relations people work on in the semantic relations area. The parsing community is split into a constituency group and a dependency group that rarely compare results. Formulating TTE tasks in these fields will help test systems on a level playing field no matter which inventory, presentation, or linguistic theory they use.

2.2 Large annotation efforts struggle to achieve high inter annotator agreement (ITA). My hypothesis is most annotators understand the sentences they are supposed to annotate equally well, but do not understand the formalism good enough for consistent labeling. By asking simple entailment questions where all they need to do is choose yes/no/uncertain, it is hoped that (i) no education in a particular formalism will be needed for annotators, (ii) annotation will proceed faster, and (iii) final ITA will be higher. (We throw away the examples that get a lot of "uncertain" answers).

3. Methodology: For a TTE task to be useful and challenging the examples should be chosen close to the border that separates the positives from the negatives. In other words, the positive examples should have non-trivial alternatives and the negative examples should be "near-misses". (My examples in Section 1 are not all very good according to this criteria). For example in the WSD TTE task (which is basically lexical substitution), the substitute should be chosen such that (i) it is a near-synonym for one of the target's senses, and/or (ii) it has a high probability of occuring in the given context. In the parsing task, examples should be based on decision points where a typical parser can go either way or where the n-best parses disagree. This suggests that examples can be generated automatically by taking the best automated systems of the day and focusing on decisions about which they are least confident. This type of "active learning" methodology will uncover weaknesses that the next generation systems can focus on.

KU: Word Sense Disambiguation by Substitution

2007-06-23T16:24:00.006+03:00

Deniz Yuret. In Proceedings of the Fourth International Workshop on Semantic Evaluations (SemEval-2007)

Abstract: Data sparsity is one of the main factors that make word sense disambiguation (WSD) difficult. To overcome this problem we need to find effective ways to use resources other than sense labeled data. In this paper I describe a WSD system that uses a statistical language model based on a large unannotated corpus. The model is used to evaluate the likelihood of various substitutes for a word in a given context. These likelihoods are then used to determine the best sense for the word in novel contexts. The resulting system participated in three tasks in the SemEval 2007 workshop. The WSD of prepositions task proved to be challenging for the system, possibly illustrating some of its limitations: e.g. not all words have good substitutes. The system achieved promising results for the English lexical sample and English lexical substitution tasks.

SemEval-2007 Task 04: Classification of Semantic Relations between Nominals

2007-06-23T16:20:00.007+03:00

Roxana Girju, Preslav Nakov, Vivi Nastase, Stan Szpakowicz, Peter Turney and Deniz Yuret. In Proceedings of the Fourth International Workshop on Semantic Evaluations (SemEval-2007)

Abstract: The NLP community has shown a renewed interest in deeper semantic analyses, among them automatic recognition of relations between pairs of words in a text. We present an evaluation task designed to provide a framework for comparing different approaches to classifying semantic relations between nominals in a sentence. This is part of SemEval, the 4th edition of the semantic evaluation event previously known as SensEval. We define the task, describe the training/test data and their creation, list the participating systems and discuss their results. There were 14 teams who submitted 15 systems.

İrade üzerine

2007-06-03T14:19:00.002+03:00

Uzun zamandır bilinç ilintili konularda kafamı en çok kurcalayan
problem "irade" (ya da "istek", "motivasyon", "dürtü") problemi.
Sabah uyandığımızda neden hiç bir şey yapmamaktansa birşeyler
yapmayı yeğliyoruz? Davranışlarımızı üreten temel kaynak nedir?
Herhangi birşey yaptığımda "neden yaptım" diye düşünürsem, bir iki
rasyonalizasyondan sonra son cevabım "canım öyle istedi de ondan"
oluyor. Bu cevap (ya da genel olarak "canın birşey istemesi"
kavramı) sizde de derin bir beyin sansürü şüphesi yaratmıyor mu?
Eğer ben insanları kontrol etmek isteyen kötü bir uzaylı olsam,
onlara zorla birşey yaptırmaya çalışmak yerine, beyinlerinin "can
istemesi" sistemleri ile oynardım - böylece benim amaçlarımı kendi
"canları istediği" için yerine getirirler ve canlarının neyi neden
istediği konusunda bir fikre sahip olmadıkları için de varlığımdan
şüphelenmezlerdi.

Bu problemin önemi arada bir çalışma motivasyonumu yitirdiğimde
kafama dank ediyor. İnsanın "istediği" birşeyi yapmasıyla
"istemediği" birşeyi kendine zorla yaptırması arasında büyük fark
var - ortaya çıkan "davranış" Skinner'in bakışıyla ayırdedilemez
olsa da.

Geçen sene ünlü biyolog J.B.S. Haldane'nin aşağıdaki sözünü
bulunca bu konudaki merakımda yanlız olmadığımı farkettim:

"Kendi motivasyonuma dair şahsi açıklamalarımın hemen her durumda
tamamen uydurma olduğu sonucuna varmış bulunuyorum. Neyi neden
yaptığımı bilmiyorum." -- J.B.S. Haldane

İşin üzücü tarafı benim geldiğim yapay zeka kültüründe böyle bir
problemin önemi vurgulanmıyor. Klasik bir yapay zeka sisteminde
algılarla dünyanın durumu belirlenir, amaçlar doğrultusunda plan
yapılır ve bu planlar davranışa dönüştürülür. Peki amaçlar nereden
gelir? Programı yazandan tabi ki. Dolayısıyla üzerinde en az
düşünülen kısım olagelmiş motivasyon. Geçenlerde kurzweilai.net'de
modern YZ'cılardan Ben Goertzel'in kendi cognitive modeli üzerine
yazdıklarını okurken aşağıdaki paragrafı gördüm (kötü olduğu için
çevirmeye uğraşmayacağım):

"And if a system can recognize itself, it can recognize
probabilistic relationships between itself and various effects in
the world. It can recognize patterns of the form "If I do X, then
Y is likely to occur." This leads to the pattern known as will."
-- Ben Goertzel

Kısacası davranışlar ve olası sonuçları hakkındaki bilgiler ile bu
davranışların hangilerinin ne zaman ne sebeple aktive edildiği
konuları birbirine karıştırılmış.

Bu genel bir körlük bilgisayarcılar arasında belki. Düşünürseniz
dünyanın en sofistike programları vakitlerinin çoğunu sizin bir
düğmeye basmanızı bekleyerek harcıyorlar! Kendi kendine günler
boyunca ilginç birşeyler yapabilen bir program yazamadık bugüne
kadar. Örneğin Doug Lenat'ın doktora tezinde yazdığı ilginç
matematiksel varsayımları otomatik olarak keşfetmeye çalışan AM
programı toplama çıkarmadan başlayıp 1700'lerin matematiğine
birkaç saat içinde geliyordu. Yıllar boyunca matematik düşünebilen
ve ilginç şeyler bulmaya devam eden bir program yok. Uzun süre
çalışan programlarımız proteinlerin fiziksel simülasyonunu yapmak,
interneti indekslemek, uzaydan gelen mesajlarda düzen aramak gibi
monoton, kendini devamlı tekrarlayan işler yapıyorlar. Belki
istediklerimizi eksiksiz ve hatasız şekilde yerine getiren
makineler tasarlama saplantısından kurtulmadığımız sürece,
makinelerimizin bizim hayal edebildiklerimiz ötesinde birşey
yapamaması son derece doğal.

Motivasyon konusunda her ne kadar basit de olsa açıklayıcı
modeller üreten tek grup "ethology" (hayvan davranışı)
bilimi. Tinbergen, Lorenz gibi öncüler en azından basit
hayvanların neyi neden yaptığıyla ilgili mekanik modeller
geliştirmeye başlamışlar. Gallistel'in yazdığı "The Organization
of Action" kitabı uzun zamandır rafimda, bu aralar okuyup ilginç
birşeyler bulursam yazacağım.

İnsanlarda ise bu probleme yaklaşmak ve düşünmek özellikle zor,
çünkü "canım istedi" hissi öyle tatmin edici ki bunun arkasında
birşeyler olduğunu düşünmeye karşı sanki beyinde bir oto-sansür
mekanizması var.

Not: Burada aradığım açıklamanın doğasıyla ilgili bir not düşeyim.
Onur son mesajında bazı bilimsel kavramlarla dini kavramların
temelde farkı olup olmadığına değinmiş. Çok basit bir fark
var. Birini kullanarak gelecekte olacaklara dair (örneğin bir
deneyde) tutarlı tahminlerde bulunabiliyoruz, diğeriyle
bulunamıyoruz (bkz. bilim nedir tartışmamız). Benim
"açıklamak"'tan kastettiğim bu. Örneğin benim motivasyonumu bir
"ruh" modeliyle açıklamaya kalkarsak, sadece soruyu ertelemiş
oluruz - "ruh"'un motivasyonunu nasıl açıklayacağız? Üstelik
fiziksel "ben"'in motivasyonunu birgün açıklayabilme ümidimiz var
- atomlarımı açıklayan kuantumun kuralları kolay anlaşılmaz da
olsa sonuçta bağlayıcı, üstelik virgülden sonra dokuz basamağa
kadar. "Ruh"'un davranışını belirleyen bağlayıcı kurallar
bildiğim kadarıyla yok. Meteryalizm insanların körü körüne
inandığı birşey değil, sadece bu tip sorulara, aynı soruyu bir
adım öteye ertelemeden cevap vermeye çalışan tek alternatif. Neyin
"açıklama" olup neyin olmadığı konusunda iyi anlaşalım.

A New Kind of Science - Stephen Wolfram

2007-05-22T14:10:00.001+03:00

Geçenlerde Stephen Wolfram'ın (Mathematica'nın yaratıcısı) $25000
ödüllü bir soru koyduğunu duydum web'e (http://www.wolframprize.org).
Bu da beni bir süre önce aldığım ama 1000 sayfa olduğu için
korkudan hiç açmadığım "A New Kind of Science" kitabına bakmaya
ikna etti.

Ana konu her işi yapabilen (hesap anlamında), düşünebileceğiniz
her makineyi simüle edebilen evrensel makinelerin var
oluşu. Fiziksel cisimlerle uğraşmaya alışık dimağlarımız için bu
inanması zor bir durum. Bir makine düşünün, istediğiniz zaman bir
arabayı, istediğiniz zaman bir tornavidayı, istediğiniz zaman bir
telefonu simüle edebiliyor! Bir kere A makinesinin B makinesini
simüle edebilmesi için A'nın daha kompleks bir makine olması gerek
gibi bir sezgimiz var. Eğer bu sezgi doğru olsaydı, evrensel bir
makine mümkün olamazdı, her zaman ondan daha kompleks makineler
tasarlayabilirdik. (Asal sayıların sonsuz olmasının ispatı ile
olan analojiye dikkatinizi çekerim).

Ama Alan Turing 1936'da sanal alemde böyle bir makinenin mümkün
olabileceğini gösterdi. İşin ilginç tarafı Turing'in evrensel
makinesi oldukça basit. Sonsuz bir şerit üzerinde bir daktilonun
kafası gibi ileri geri hareket edebilen yazıcı bir kafa düşünün
(1936'da henüz PC'ler icat olunmamıştı, ama daktilolar vardı). Bu
kafanın yapabildiği tek şey şeritte üzerinde bulunduğu sembolü
okuyabilmek, ve sonlu sayıda kurala göre yeni bir sembol yazıp
sağa ya da sola doğru bir pozisyon hareket edebilmek. Turing bu
makinenin diğer tüm makineleri simüle edebileceğini ispatladı.

Evrensel olan tek makine tabi bu daktilo bozması şey değil, Turing
makineleri sadece evrenselliği ilk ispatlanan (gerçi Godel'in
1931'deki meşhur ispatında da evrensel bir makine gizli olduğu
söylenebilir). "A new kind of science" kitabının üçüncü chapterini
okursanız iyi bir basit makineler listesi ve güzel tarifleri var
(http://www.wolframscience.com/nksonline):

- cellular automata
- mobile automata
- turing machines
- substitution systems
- tag systems
- cyclic tag systems
- register machines
- symbolic systems

Ve tabi bugün kullandığımız tüm bilgisayar dilleri ve CPU'larını
da (sonsuz bir memory ekledikten sonra) bu evrensel makineler
listesine koyabiliriz.

Tüm bu makine çeşitleri içinde belli bir karmaşıklığa ulaştıktan
sonra evrenselliği görmek mümkün - bu evrensel makinelerden
herhangi birisi diğer hepsini simüle edebiliyor. Fakat her Turing
makinesi evrensel değil. Örneğin sadece iki çeşit sembol okuyup
yazabilen, ve sadece iki çeşit kurala göre hareket edebilen Turing
makinelerinin evrensel olamayacağı gösterilmiş. Turing'in orijinal
makinesinde tam kaç sembol ve kaç kural olduğunu bilmiyorum. Ama
1960'larda Marvin Minsky 4 sembol ve 7 kural ile evrensel bir
Turing makinesi yapılabileceğini göstermiş. Uzun zaman basit
Turing makineleri konusu ile kimse uğraşmazken, 1990'larda Wolfram
5 sembol ve 2 kural kullanarak evrensel bir makine
yapılabileceğini göstermiş. Yani bu makinenin kendini içinde
bulabileceği 10 farklı durum var. Bu 10 farklı durum için
bulunduğu pozisyona ne yazacağına ve sağa mı sola mı hareket
edeceğine karar veriyorsunuz, o kadar. Ve bu makine dünyada
yazılmış tüm programları simüle etmek için yeterli! (Sadece
programınızın uygun bir tercümesini makinenin şeridine başta
yazmanız gerek, tabi simülasyonun biraz yavaş olduğunu da akıldan
çıkarmamak lazım).

Ödüllü soru ise Wolfram'ın seçtiği 2 kural ve 3 renkli bir Turing
makinesinin evrenselliğini ispatlamak. Var mı gönüllü?

Bilinç üzerine bir okuma listesi

2007-05-22T13:53:00.001+03:00

Uzun zaman sonra "bilinç" konusunu düşünmeye ve okumaya başladım. Aşağıda küçük bir okuma listesi gönderiyorum ilgilenen için. Ama öncelikle bu konuda "temel soru nedir" sorusuna kendi fikrimce bir cevap yazayım dedim. Belki tatmin edici olmayacak ama konuya bir yerinden girelim.

Galileo ve Newton "evrensel kanunları" keşfetmeden ve Laplace
cinini (Laplace's demon) icat etmeden önce "bilinç" bugün
oluşturduğu kadar ciddi bir sorun değildi sanki. Hayatı özgür
irademiz, isteklerimiz ve inançlarımız cinsinden açıklayabiliyor,
ruhun gerçekliğine maddeninkine olduğundan daha güçlü bir şekilde
bağlanabiliyorduk. Neden olmasın ki, Descartes'in de dediği gibi
en emin olduğumuz şeyler sonuçta kendi düşüncelerimiz,
algılarımız, isteklerimiz - başka herşey yalan olabilir sonuçta...
Bilim konusuna fazla ilgisi olmayan arkadaşlara bilinç konusunu
açmaya çalıştığımda genelde benzer bir tepkiyle karşılaşıyorum:
"problem nedir ki" diyorlar sanki, "ben neyin (irademin,
algılarımın, inançlarımın) gerçek olduğunu biliyorum, senin
bilimin bunları henüz açıklayamıyorsa bu bilimin sorunu..."

Tabi bilimsel olarak kimse daha bilinç ve benzer psikolojik
kavramları beynin fonksiyonları olarak açıklayabilmiş değil. Bazı
filozoflar temelde böyle bir açıklamanın mümkün olabileceğine
karşılar. Fakat yine de sonuçta herşeyin fiziğin temel kanunları
cinsinden açıklanabileceğine dair yaygın bir inanç var. Fiziğin
temel kanunları ise dışarıdan bir etki kabul etmiyor (enerjinin
korunumu vb). Bu durumda bizim birşeyleri kontrol ediyor olmamız
(ki en güçlü inançlarımızdan biri), imkansız gibi
görünüyor. Sonuçta hepimiz atomların köleleri durumundayız
gibi. Ama ben hiç de kendimi atomların oraya buraya ittirdiği bir
madde bulutu gibi hissetmiyorum.

Bu durumdan çıkmak için iki yol var. Birincisi irade, algı, istek
ve inançların temel oluşundan taviz vermemek. Bir ihtimal fiziği
modifiye etmemiz gerekebilir (Penrose metodu). Ya da fiziğin
boşlukları içinde (kuantum belirsizlik, kaos, vs) iradeye yer
aramak. Ya da "bilinç" diye madde ve enerji dışında yeni bir
temel olgu olduğunu varsayıp baştan başlamak.

İkinci yol ise fizikten taviz vermemek. Bu pozisyondaki insanların
yapması gereken ise "nasıl oluyor da bize böyle gözüküyor"
sorusuna cevap vermek. Mesajın sonundaki listede verdiğim tüm
kitaplar bu ikinci yolu takip etmeye çalışan insanların
yazdıkları. Ama o zaman gerçekten atomların oraya buraya ittirdiği
bir bulutsam (ya da Sagan'ın deyimiyle yıldız tozu isek) --

1. Nasıl oluyor da ben istediğim zaman kolumu oynatabiliyorum?

2. Kırmızı bana belli bir şekilde gözüküyor, beynimin her detayını
bilseniz bile kırmızının bana nasıl gözüktüğünü anlayabilir
misiniz?

3. İnsanların (ve bazı diğer canlıların) davranışlarını "istek",
"inanç", "irade" vb kavramları ile hayli iyi açıklayabilmek ve
tahmin edebilmek nasıl mümkün. "istek" gibi kavramların fiziksel
karşılığı nedir?

4. Aynı benim gibi tepki veren bir robot yapsak onun da içinde
dışarıya bakıp gerçekten birşeyler gören "birisi" olur mu? Yoksa
içi boş olabilir mi? Bu robota sen bilinçli misin desek, o da
benim gibi evet dese, yalan mı söylüyor olur?

5. Eğer hepimiz yıldız tozu isek bir grup tozun diğer grup tozu
yok etmesi, acı çektirmesi (zaten acı ne demek?) gibi konularda
niye bu kadar hassasız? Ki böyle kötü şeyler olduğunda, oraya
buraya ittiren atomlar sorumlu ise ceza sistemi saçma değil mi?

6. Ben niye kendimi isteyen, yapan, belli şeylere inanan bir
varlık gibi hissediyorum?

Bu listeyi uzatmak mümkün. Ama dikkat ederseniz hemen her soru
Laplace'in mekanik evreni ile psikolojik ve ahlaki kavramlarımızın
çatışmasından türüyor. En son (ve bence en önemli) soru için
Wittgenstein'ın bilinen bir anektodu gayet aydınlatıcı bence:

Wittgenstein bir arkadaşına sormuş: "Hep merak etmişimdir,
insanlar niye bu kadar uzun zaman güneşin dünyanın etrafında
döndüğünü sanmışlar?" Arkadaşı cevap vermiş: "Neden olacak,
buradan bakınca öyle gözüküyor da ondan..." Wittgenstein'ın
cevabı: "Peki dünya kendi etrafında dönüyor olsaydı nasıl
gözükecekti?"

Peki hepimiz gerçekten trilyonlarca molekülün itişmesinden oluşan
karmaşık yaratıklar olsaydık, kendimizi nasıl hissedecektik?

======
Okuma listesi:

[1] Brainstorms, Daniel C. Dennett 1978
- Dennett malesef Russell kadar temiz düşünüp ifade edebilen bir
yazar değil, ama sanki fuzzy konularda doğru yönlere ışık tutuyor
gibi.

[2] Godel, Escher, Bach, Douglas Hofstadter 1979
- AI'cıların pek övdüğü klasik eser. Okuduğum en güzel tasarlanmış
(estetik olarak) kitaplardan biri (diyaloglar, anagramlar,
resimler). Tercümesi çok zor olmasına rağmen birileri uğraşıp
Hofstadter'in yardımıyla Türkçe'ye çevirmiş, fakat hiç satmadığını
duydum. Her fırsatta bir iki tane alıp öğrencilerime hediye
ediyorum :)

[3] Mind's I, Hofstadter and Dennett 1981
- Okuması kolay güzel hikayelerden (philosophical fiction?)
oluşuyor - bir bilinç mesnevi'si denebilir - bence grubun mecburi
okuma listesinde olmalı ki kompleks fikirleri anlatmak için bi
sürü uğraşacağımıza bu hikayelere gönderme yapabilelim.

[4] Social Brain, Gazzaniga 1987
- Bilincin aslında göründüğü gibi olmadığını (?) en güzel gösteren
neuroscience öykülerinden biri. En büyük problem bilinci herkes
anladığını hissediyor, gerçekten anlama yolunda ilk yapılması
gereken bu "sanılan" anlayışın böyle güzel deneylerle yavaş yavaş
yıkılması. Bu arada Aslı'nın gönderdiği görsel illüzyon linki de
iyi bir başlangıç.

[5] Consciousness Explained, Daniel C. Dennett 1991
- Dennett sonunda orada burada ağzında gevelediği tüm düşünceleri
bir araya koymuş. Ama tabi "bilinç nedir?"->"bilinç ilüzyondur",
"qualia nedir?"->"qualia yoktur" gibi cevaplardan oluştuğu için
rakipleri kitaba "Consciousness explained away" ismi vermişler.

[6] Consciousness: A Very Short Introduction, Susan Blackmore 2005
- Diğerlerini çok güzel özetleyen kısa ve güzel bir
başlangıç. Sadece bir kitaba bakabilecekseniz bunu okuyun derim.

[7] Good and Real, Gary L. Drescher 2006
- Mekanik evren modeli içerisinde sadece bilinci, zamanı ve kaderi
değil, aynı zamanda ahlaki da açıklayabileceğimizi savunan iddialı
bir eser.

[8] I am a Strange Loop, Douglas Hofstadter 2007
- Bunu yeni okuyorum daha, ama Hofstadter'in kendi deyimiyle [2]
GEB'de anlatmak istediklerini tam anlamayanlar için yazılmış bir
kitap.

Locally Scaled Density Based Clustering

2007-04-11T12:01:00.004+03:00

Ergun Biçici and Deniz Yuret. In International Conference on Adaptive and Natural Computing Algorithms (ICANNGA 2007), LNCS 4431, Part I, Springer-Verlag. (PDF, PS, Presentation, Code, Readme)

Abstract: Density based clustering methods allow the identification of arbitrary, not necessarily convex regions of data points that are densely populated. The number of clusters does not need to be specified beforehand; a cluster is defined to be a connected region that exceeds a given density threshold. This paper introduces the notion of local scaling in density based clustering, which determines the density threshold based on the local statistics of the data. The local maxima of density are discovered using a k-nearest-neighbor density estimation and used as centers of potential clusters. Each cluster is grown until the density falls below a pre-specified ratio of the center point’s density. The resulting clustering technique is able to identify clusters of arbitrary shape on noisy backgrounds that contain significant density gradients. The focus of this paper is to automate the process of clustering by making use of the local density information for arbitrarily sized, shaped, located, and numbered clusters. The performance of the new algorithm is promising as it is demonstrated on a number of synthetic datasets and images for a wide range of its parameters.

Drexler quote

2007-03-19T22:31:00.000+02:00

It makes sense to think in terms of three levels of knowledge about a field:

Knowing what a field is about—knowing what sorts of physical systems and phenomena it deals with, and what sorts of questions it asks and answers.
Knowing the content of a field in a qualitative sense—having a good feel for what sorts of phenomena can be important in what circumstances, and knowing when you need answers from work in that field.
Knowing how to get those answers yourself, based on personal mastery of enough of the field's subject matter.

If one has enough knowledge at levels (1) and (2) in enough fields, then one can steer clear of problems in those fields while doing work in a related field where you have knowledge at level (3). And this is a good thing, because knowledge at levels (1) and (2) takes far less time to acquire. But to make proper use of knowledge at levels (1) and (2) requires a harsh discipline: attempt to assume the worst about what you don't know. Don't assume that a poorly-understood physical effect will somehow save your design; do assume (until finding otherwise) that it may utterly ruin it. Without this discipline, you'll become an intellectual hazard. With it, you'll be able to make a real contribution.

Technology and society

2007-03-11T13:42:00.001+02:00

Two interesting articles on technology and its impact on society. I received the first one from Ergun Bicici. The second one came from Emrah Çevik.

U.C. Berkeley Graduation Speech by Peter Norvig
Economic Possibilities for our Grandchildren by JM Keynes (1930)

Bilinç üzerine

2007-02-22T13:26:00.001+02:00

Kavram uzayımızda "göründüğü gibi olmama" ödülleri dağıtılsa
herhalde "bilinç" birincilik ödülüne layık görülürdü.

İnsanın aklına gelen "peki bilgileri algılayan kim" sorusu belki
bilinci anlama konusunda bizi en çok uğraştıran soru. İçeride
algıları izleyen bir küçük bilinç (homunculus) varsaymak yetmiyor
çünkü o zaman aynı soruyu küçük bilinç için sormak gerek. Kaldı
ki beyin hakkında bildiklerimiz algıların yakınsandığı bir merkez
fikrini pek desteklemiyor. Desteklese bile bu tatmin edici
olmazdı: beyninizi açıp, işte şuradaki nöron kümesi senin bilincin
deseler bu size çok şey ifade etmeyecek. Örneğin şu an dinlediğim
müziğin işitme merkezimde bir seri nöron tıklaması olarak kod
edildiğini biliyorum ama bu duyduğum müziğin öznel kalitesini
açıklamaya yetmiyor.

Bir alternatif bilinci beynin dışında aramak. Tüm büyük dinler
(Budizm dışında sanırım) manevi bir dünyanın gerçekliğini kabul
ediyor. Bu dualist pozisyon Descartes'tan beri pek çok ciddi
filozof tarafından da savunuldu. Başka konularda düşüncelerine çok
saygı duyduğum Popper bu akımın en son örneklerinden biri
[3]. Buradaki en büyük problem artık her ciddi filozofun enerjinin
korunumu gibi fiziksel kanunlara inanması ve bu da fizik dışında
bir olgunun fiziksel cisimleri (elimiz kolumuz gibi) etkilemesini
imkansız hale getiriyor.

Tabi bu "bilinç" meteryali her ne ise illa fizik dışında olmak
zorunda değil. Dualist pozisyonu korumak için fiziği genişletmeye
ve fizik içerisinde bilinç için yer açmaya çalışanlar da var. Bu
forumda da bahsi geçti daha evvel, örneğin Roger Penrose [4].

Bugünkü bilgimiz ile en tutarlı pozisyon ise bilinç için yeni bir
meteryal aramak yerine bilincin beyindeki işlemlerden ibaret
olduğunu kabul etmek olurdu. Malesef bu meteryalist yaklaşımın
önündeki en büyük psikolojik engel başta sorduğumuz soru: "peki
bilgileri algılayan kim"...

Bu konuda yazılmış çizilmiş çok şey var. Özellikle [1], [2] ve
[5]'i tavsiye ederim. Bilincin bir ilüzyon olduğuna insanın
kendini dürüstçe inandırabilmesi kolay değil (bu arada ilüzyon
"yok", "yalan" anlamında değil, sadece "aslı göründüğü gibi değil"
anlamında).

Başka konularda ilüzyonları yıkmak bir nebze daha kolay. Örneğin
şu an görme duyum bana masami, bilgisayarımı, telefonumu, rafları,
kısaca odamın bu köşesindeki hemen her şeyi rahatça algıladığımı
söylüyor. Fakat basit bir deneyle aslında başparmağımın tırnağı
kadar bir alan dışında hemen hemen kör olduğumu görmem
kolay. Yemekte pilav mercimek vs yediğiniz bir gün, tabağınızda
son kalan tanecikleri tek gözünüzü kapatıp diğerini belli bir
noktaya sabitleyerek saymaya çalışın - ne kadar imkansız olduğunu
göreceksiniz. Ya da eğer partneriniz razı olursa deneyin:
bacağınızın arkasına tek bir sivri cisimle mi dokunulduğunu yoksa
aynı anda aralarında 2-3 cm olan iki farklı cisimle mi
dokunulduğunu ayırdedemeyeceksiniz.

Eğer Memduh haklı ise ve bilinç de zamanı algılamamızı sağlayan
bir duyu oranıysa belki yukarıdakilere benzer ilüzyon yıkıcı
testler tasarlayabiliriz, ne dersiniz?

Susan Blackmore meditasyon tavsiye ediyor. Benim için dönüm
noktası bir gün bana tüm dürüstlüğü ile "evet ben bilinçliyim"
diyecek bir robot yapabileceğime inanmam oldu. Etrafında olup
bitenleri algılayıp hatırlayabilen; başka canlıları, onların niyet
ve isteklerini modelleyebilen; neler yaptıklarını hatırlayıp neler
yapacaklarını tahmin edebilen bir robot, bu analiz gücünü kendi
üzerine çevirdiğinde ne görür tahmin edersiniz? Acaba onu mekanik
bir robot olduğuna inandırabilir miyiz kolay kolay?

[1] Consciousness, A Very Short Introduction -- Susan Blackmore
[2] Consciousness Explained -- Daniel C. Dennett
[3] The Self and Its Brain -- Karl Popper and John Eccles
[4] The Emperor's New Mind -- Roger Penrose
[5] Mind's I -- Douglas Hofstadter and Daniel Dennett

Akıllı Tasarım

2007-02-21T13:18:00.001+02:00

Bugüne Berkin'in gönderdiği Türkiye'nin ilk "Akıllı Tasarım"
(intelligent design) konferansı ile ilgili mesajı okuyarak
başladım.

http://www.mustafaakyol.org/archives/2007/02/post_1.php

İstanbul Büyük Şehir Belediyesini tebrik ediyorum. Duyduğum
tepkinin kaynağı akıllı tasarım fikrinin yanlış olduğunu
düşünmemden ziyade, bu tip anti-bilim propogandayı bile
Amerika'nın "bible belt"'inden ithal ediyor olmamız. Bir otomobil
tasarımı yaparken orijinal olamamamızı anlıyorum, McDonalds ve El
Torito'yu İstanbul'a getirmemizi anlıyorum, ama sofu fikirler
üretirken lütfen Amerika'nın yardımına ihtiyacımız olduğunu
söylemesin kimse. Bu işte onlardan yüzlerce yıl daha tecrübeliyiz,
daha yaratıcı olabiliriz...

Son fiziksel toplantımızda Memduh tüm bulguları kabul edip açık
fikirli olmasına rağmen evrime inanmakta güçlük çeken birine nasıl
bir argüman sunulabileceğini sorgulamıştı. Bu konuda okuduğum
kitaplar malesef çoğunlukla karşı tarafın straw-man argümanlarıyla
uğraşıyor. Bir yandan aklımı bu kurcalamakta.

Tabi bu arada ders saatim geldi 60 mühendislik öğrencisine
olasılık öğretmek için (günün konusu permutasyon, kombinasyon)
girdim sınıfa. Tahmin edebileceğiniz gibi dersin yarısından
fazlası evrim konusundaki örneklere gitti :)

Şu maymunların rastgele daktilo tuşlarına basarak Shakespeare
yazma örneğini ele alalım. Genelde canlılarda görülen karmaşık
yapıların (göz, beyin, karaciğer) "rastgele" ortaya çıkması bizim
maymunların edebi yetenekleriyle karşılaştırılır. Bu argümandaki
ilk zayıf noktayı öğrenciler hemen buldu: dünyada çok sayıda canlı
çok uzun zamandır evrim oyununu oynamaktaydı bu iş bir iki
maymunun işi gibi değildi. Fakat bu zayıf nokta çökertici
değil. 100,000 harflik tipik bir Shakespeare oyununu rastgele
yazma ihtimali 30^-100,000 gibi bir sayı ki evrenin tüm
parçacıkları big-bang'den beri bu işle uğraşıyor da olsa
yetmiyor. Zayıf nokta maymunların rastgele tuşlara bastığı
varsayımı. Evrimde yanlış tuşa basan maymun vefat ediyor, yazdığı
harf siliniyor, yerine başka maymun geçiyor. Ta ki doğru tuşa
basana kadar. Bu şekilde her harf için ortalama 30 maymun telef
etsek, 3 milyon maymun bir Shakespeare oyununu rahat yazar. Bu
kadar maymun İstanbul'da bile rahatça bulunur.

Fakat tüm bunlar boş. Esas nokta bu değil. Evrime inanmak
istemeyen bir insan bence ikna edilemez. Daha basit bir örnek
vereyim. Eğer ben evrenin bir gün önce başladığına inanmak
istiyorsam kimse beni bunun aksine ikna edemez. Hatıralarım mı?
Ben beynimde o hafızalarla üretildim. Dünyadaki fosiller mi? O
kayalar da o şekilde üretildi. Karbon tarihleme mi? Dün bu işleri
yapan zat o cisimlerdeki C-12 ve C-14 oranını o şekilde
ayarladı. Söyleyebileceğiniz hiçbir şey evrenin dünden önce var
olmadığını ya da yarından sonra var olmayacağını ispatlayamaz bana
- çünkü mantıksal bir delik yok varsayımımda.

Peki o zaman neden olası varsayımlardan biri (evren 14 milyar yıl
önce big-bang ile başladı vs vs) bana diğer varsayımlardan daha
çekici geliyor? Geçenlerde bu forumda bilim nedir ne değildir
(yanlışlanabilirlik vs) konusunu tartıştık. Fakat
yanlışlanabilirlikten kime ne? Benim ne zorum var her söylediğim
yanlışlanabilir olsun diye yırtınayım? Niye bu düşünce sistemini
diğer düşünce sistemlerine tercih ediyorum?

Sonunda iki sebebi olduğuna karar verdim.

Birincisi merak ve estetik. Küçüklükten beri ne nasıl çalışır
merak ediyorum. Canlıları cansızlardan ayıran nedir, dinazorlar
nereden geldi, nereye gittiler, genler nasıl çalışır, hücrelerin
içinde ne olup bitiyor, tüm bileşenlerini bir araya getirsek canlı
hücre yapabilir miyiz - bunların hepsi birbirine bağlı kafamda
dönen sorular. Birilerinin gelip bana böyle oldu çünkü akıllı biri
böyle tasarladı demesi, "bu soruyu sorma" demesinden farklı değil
- dolayısıyla merakımı tatmin etmiyor - ayrıca fikir olarak bir
gecekondu mahallesi kadar estetiği yok.

İkinci sebep fayda. Bilimsel yöntemi kullanarak problemleri
çözebileceğimize, hastalıkları yenebileceğimize, doğayı daha iyi
kontrol edebileceğimize vs. inanıyorum. Hatta bu fikir bana evren
dünden önce var olmasaydı bile cazip geliyor. Sadece evrenin
yarından sonra da var olacağına inanmam merak etmem ve
problemlerle uğraşmam için yeterli. Gerçi yarın evren sona erecek
olsa da matematikle uğraşırdım herhalde.

İşin ilginç tarafı eğer bu son söylediğim doğru ise bilime ve
dolayısıyla evrime inanmayanların teknolojide, tıpta geri kalması
ve evrim kanunlarına göre elimine olmaları beklenebilirdi. Tabi
kurduğumuz sosyal düzen insanların bilimsel inançlarıyla çocuk
yapma sayılarını pek correlated tutmuyor. İronik olurdu öyle
olsa. Sanki evrime inanmayanları evrim cezalandırıyormuş gibi...

Tabi bu da akıllı tasarımcılara karşı ikna edici bir argüman
değil. Çünkü onlar da benim gibilerin pek yakında kutsal bir
felaket sonucu ortadan kaldırılacağına inanıyorlar :)

Reckoning with Risk by Gerd Gigerenzer

2007-02-21T10:44:00.000+02:00

This is the last one of the new breed of "innumeracy" books I have read. Not one of the better ones. Still ok for generating examples for my probability course. Other examples of the genre include:

- Innumeracy by Paulos
- A mathematician reads the newspaper by Paulos
- How to lie with statistics by Huff

Not in the same genre but the following books on the history of probability and statistics may also be useful for stories and examples:

- Games Gods and Gambling by David
- The Probabilistic Revolution by Kruger et.al.
- The History of Statistics by Stigler.
- The Lady Tasting Tea by Salsburg.

The website
http://www.planetqhe.com/beta/information/home.htm contains nice problems and animations as well as some book recommendations and links.

- The Magical Maze by Ian Stewart
- Chance Rules by Brian Everitt
- Inevitable Illusions by Massimo Piattelli-Palmarini
- Taking Chances by John Haigh
- Fifty Challenging Problems in Probability by Frederick Mosteller
- Cartoon Guide to Statistics by Gonick and Smith

Sigara ve özgürlük

2007-02-14T13:08:00.001+02:00

Amartya Sen'in Unrestrained smoking is a libertarian half-way house makalesi üzerine düşünceler...

Libertarian söylem içinde delik bulacağım derken, Amartya Sen'in
argümanlarında içinden tren geçirilecek boşluklar bırakması ilginç
tabi. Bu boşluklardan biri Emre'nin bahsettiği Platon limitinden
bahsedilmeden geçmiş gelecek ben çatışmasına devletin burnunun
sokulması, bir diğeri de herkesin sosyal yardımı bir takım
özgürlüklerin kısıtlanmasına tercih edeceğinin tartışmasız
varsayılması (hatta alternatif "monstrously unforgiving society"
olarak betimlenip bu konuda çözüm düşünmek isteyebilecekler baştan
damgalanmış).

Devlet eğer sosyal bir anlaşmanın ürünü olacaksa beni neden
koruyup neden kormayacağına da ben karar verebilmeliyim. Korunmak
istediğim ölçüde özgürlüklerimin kısıtlanmasına da
katlanmalıyım. Örneğin beni kimsenin öldürmesini istemiyorsam
devleti de beni koruması için görevlendirdiysem, benim de
başkalarını öldürme özgürlüğümün elimden alınmasına ses çıkarmamam
gerek. (Tabi farklı insanlar farklı şeylerden korunmak
isteyecekler, durum karışacak vs.)

Peki gerçekten gelecek benleri bugünkü benden korumasını istiyor
muyum ben üçüncü bir kişinin? Bu bana bir kabus gibi
geliyor. Bugünkü ben geçmiş beni yaptığı bütün hatalarla (belki
özellikle hatalarla) kabul edip seviyor. Birileri bana onu yapma
bunu yapma deyip beni "korusaydı" karşınızda bu Deniz olmayacaktı
(ana babama sorun, çok denediler, dinletemediler). Farklı
ben'lerin farklı bireyler olarak kabul edilmesine bir itirazım
yok, ama lütfen aramızdaki anlaşmazlıklara başkası
karışmasın. Hatta biraz daha ileri gidersek, ben yakın ailem ve
yakın arkadaşlarım arasındaki anlaşmazlıklara da devletin
karışmasını tercih etmem, en azından o durumlarda uygulanan
kurallarla hiç tanımadığım insanlarla aramdaki ilişkilere
uygulanan kuralların aynı olması bana saçma geliyor.

Sosyal konularda ne zaman basit prensiplere (aksiyomlara) dayalı
çözümler üzerinde düşünmek istesem, bu konulara benden çok kafa
yoran bazı tanıdıklarım konunun böyle basit olmadığını, insanların
karmaşık olduğunu, benim basit teknik kafamla düşünüp önerdiğim
çözümlerdeki delikleri işaret ederek gösterir, naivete'me
gülerler. Ben yine de sosyal konularda basit prensiplerden
çıkarılan ideallere aşımtotik olarak yaklaşmaya çalışmanın, fuzzy
güt feeling'lerle prensipsiz bir çözüm karmaşası üretmekten iyi
olduğu düşüncesindeyim. Doğru çözümlere bu şekilde daha kolay
ulaşabileceğimizi ispatlayamasam bile en azından neyin doğru neyin
yanlış olduğunu tartışabileceğimiz bir asgari müştereğimiz olur.

John Stuart Mill'in düşünceleri, ve Libertarianism benim bu
anlamda anlayabildiğim idealler. (Libertarian'lar sosyal yardım
olmasın demiyor bu arada, zorla olmasın diyorlar sadece) Pratikte
sorunları çıksa da oturup düşünebiliyorum nasıl bu ideallerle
consistent başka bir çözüm olabilir diye. Birisi Amartya Sen'in
aksiyomlarını bana anlatabilir mi?

Permutation City - Greg Egan

2007-02-12T12:53:00.001+02:00

Değişik "varoluş" çeşitlerinin virtiyozu Greg Egan'dan Permutation
City adında bir sci-fi hikaye okudum. Aslında Egan'a science
fiction demek haksızlık, philosophical fiction demek
lazım. Varoluş çeşitleri derken aklınıza gelebilecek biyolojik,
sentetik, yazılımla simüle edilmiş, ya da simüle edilen bir
evrenin içinde evrimleşmiş her türlü bilinç ve bunların
aralarındaki etkileşimler, kopyalamalar, zamanı algılamalarındaki
görece farklar doyasıya işlenmiş. İlgi çekebilecek birkaç konu:
1000 yaşına gelen insanlar long-term hafızalarındaki yavaşlamayla
nasıl başa çıkarlar, sizden 17 kat yavaş run edebilen
simülasyonunuzla nasıl iletişim kurarsınız, siz simülasyonu geriye
doğru çalıştırdığınızda simülasyondaki bilinçlerin zaman kavramına
ne olur, peki simülasyonu durdurduğunuzda o bilinçler için zaman
durur mu?

Fikir incileri

2007-02-12T02:07:00.000+02:00

Her konunun (okulda nefret ettiğim konuların bile) sahip olduğu
fikir incileri olduğuna inanıyorum. Okul hayatımızda iç bayıcı
mantıksal sıra yerine bu incilerle beslesek çocukları eminim pek
çok konuda daha meraklı olacaklar. Tabi hangi konunun derinine
inmek istese incilerle dolu kıyıyı aşıp güç bela yürünen
bataklıklarla uğraşması gerekiyor insanın. Ama bir kere incilerin
tadını almış olan insanlar için bu daha dayanılır bir işkence.

Ortaokulda arkadaşım Ünal, abisinden öğrendiği Pisagor teoreminden
bahsetmişti bigün otobüste giderken. İlk tepkim "hadi canım" oldu.
Matematikçiler her dik üçgen için a^2 + b^2 = c^2 olduğunu nasıl
bilebilirlerdi? Bir kere her üçgeni çizip ölçmeleri gerekirdi ki
bu da sonsuza kadar sürerdi. Üstelik bir sonraki üçgenin kurala
uymayacağını nasıl bilebilirdi kimse? Yani kısacası inanmadım.
Sonra tam olarak ne zaman bilmiyorum ama matematikçilerin sonsuz
sayıda cisimle ilgili kesin iddialarda bulunabildiklerini anladım.
Çok daha sonra da aslında matematiği diğer uğraşılardan ayıran
temel özelliğin bu olduğunu ve başka hiçbir şeyden emin
olmadığımızı...

Neden anlatıyorum bu hikayeyi? Çünkü o günden beri benim "inci"
olarak nitelendirdiğim fikirlerin özelliklerini çok güzel
örneklendiriyor. Bir inci ilk duyulduğunda yarattığı tepki "hadi
canım" olmalı. Bu his güzel bir sihirbazlık numarası gördüğümde
hissettiğim incredulity'nin aynısı. Te sonra bir zaman "Aha"
dedirtmeli anlayınca. Bilim ve matematikte doğru ve faydalı
fikirler çok, ama aralarında insana önce "hadi canım" sonra "aha"
dedirtenler az.

Bu açıdan bakınca bazı sorulara kesin cevaplar verebilmemiz de
prensipte cevaplanamayacak sorular olması da bana ilginç geliyor.
Bilincin, özgür iradenin, ve zaman akışının birer ilüzyon olabilme
olasılığı ilginç geliyor. Elektronların izlenip izlenmediklerine
göre bir o delikten bir bu delikten geçmeleri ilginç geliyor.
Dünyadaki elmalarla uzaydaki yıldızların aynı atomlardan oluşup
aynı yerçekimi kurallarına uyması ilginç geliyor. Sonlu sayıda
veriye bakıp, daha önce görmediğimiz şeylerle ilgili tahminlerde
bulunabilmemiz, kısaca "öğrenmenin" ve "bilimin" mümkün oluşu ve
limitlerinin ne olduğu ilginç geliyor. Borsada hayat boyu para
kazanamasam da, para kazanılamayacağını ispatlamanın imkansız
oluşu ya da pokerde her ne kadar hesaplayamasam da hiçbir zaman
para kaybetmeyecek bir stratejinin var oluşu ilginç geliyor. Kedi
yavrularının beyinlerinde görmelerini sağlayan center-surround
hücreler bulunması, daha sonra bunların aslında iki boyutlu türev
aldıklarını anlamamız, daha sonra rastgele bağlanmış bir sınır
ağına rastgele resimler gösterildiğinde hücrelerin basit bir
kuralla kendilerini bu şekilde bağlayabildiklerinin gösterilmesi
bana çok ama çok ilginç geliyor.

Ve bunların hiçbiri okullarda çocuklara anlatılmıyor! Tüm bu
bahsettiklerimi ilgili bir ortaokul öğrencisine çok rahat
anlatabileceğimi biliyorum. Bunu bildiğim halde Bilim ve Teknik
dergisinin mesajlarıma cevap yazmaması, Tübitak'ın kitap
çevirileri yaparken fikrimizi sormaması, kendi çocuğuma ne
öğretileceğine karar verecek milli eğitim bakanlığının zavallı
insanlar tarafından yönetilmesi, çalıştığım okulun öğrettiklerimin
kalitesiyle de içeriğiyle de pek ilgilenmemesi, ve ıvır zıvır
işlerle uğraşırken zamanın geçip gitmesi beni çileden çıkarıyor.

Project Orion by George Dyson

2007-02-07T16:40:00.000+02:00

"A universal library, whether of books, genotypes, or technologies, forms an expanding cloud of possibilities in a multidimensional space. The laws of nature form an outermost bound. A smaller cloud, condensed out of this atmosphere of possibilities, represents the organisms of technologies that can be assembled from available parts. Finally, a small central core - where we live - represents the books, organisms, or technologies that exist at the present time. Instead of building outward by small increments, Ted (Taylor) sought to develop Orion the other way around: start with the laws of nature; delineate the bounds first of possibility and then of practicality; finally, trace a path backward to existing technology so as to advance not by increments but by leaps and bounds." -- quote from pp. 98

About me

2007-02-01T14:19:00.000+02:00

I am an assistant professor in Computer Engineering at Koç University. Previously I have spent 12 years at the MIT AI Lab and co-founded Inquira, Inc. My research is in natural language processing and machine learning.

Currently I am one of the organizers of the SemEval3 semantic evaluation exercise, co-chair for the ACL 2011 semantics area, and an editor for the Computational Linguistics Journal.

I do research with both undergraduate and graduate students with a strong background in mathematics and programming. If interested, take a look at some of my project ideas, papers, classes, and past students.

For more information please visit my blog.

Koç Üniversitesi Bilgisayar Mühendisliği Bölümü'nde öğretim üyesiyim. Bundan önce MIT Yapay Zeka Laboratuarı'nda 12 yıl çalıştım ve Inquira, Inc. şirketini kurdum. Araştırmalarım doğal dil işleme ve otomatik öğrenme alanlarındadır.

Bu yıl SemEval3 anlamsal analiz yarışmasının organizatörlüğünü, ACL 2011 konferansı için anlamsal analiz alanında kurul başkanlığını ve Computational Linguistics dergisinin yayın kurulu üyeliğini yürütmekteyim.

Benimle araştırma yapmak isteyen lisans ve lisansüstü öğrencilere kendilerini matematik, programlama ve İngilizce alanlarında iyi yetiştirmelerini tavsiye ediyorum. İlgilenirseniz proje fikirlerime, makalelerime, mezun öğrencilerime ve verdiğim derslere bir göz atabilirsiniz.

Daha fazla bilgi için lütfen blog'umu ziyaret edebilir Türkçe yazılarıma bakabilirsiniz.

Classes

2007-02-01T10:53:00.006+02:00

Fall 2011
Comp341 Artificial Intelligence

Fall 2010
Ecoe554 Machine Learning

Spring 2010
Ecoe580 NLP Seminar

Fall 2009
Comp101 Structure and Interpretation of Computer Programs
Ecoe554 Machine Learning

Spring 2009
Comp101 Structure and Interpretation of Computer Programs
Engr200 Probability and Statistical Methods for Engineers
Ecoe580 Semisupervised Learning

Fall 2008
Comp101 Structure and Interpretation of Computer Programs
Ecoe554 Machine Learning

Spring 2008
Comp101 Structure and Interpretation of Computer Programs
Engr200 Probability and Statistical Methods for Engineers

Fall 2007
KUNLP Reading group
Comp101 Structure and Interpretation of Computer Programs
Comp131 Introduction to Programming

Spring 2007
Comp101 Structure and Interpretation of Computer Programs
Engr200 Probability and Statistical Methods for Engineers

Fall 2006
Comp101 Structure and Interpretation of Computer Programs

Spring 2006
Ecoe554 Machine Learning

Fall 2005
Comp101 Structure and Interpretation of Computer Programs
Engr200 Probability and Statistical Methods for Engineers

Spring 2005
Comp101 Structure and Interpretation of Computer Programs

Fall 2004
Engr200 Probability and Statistical Methods for Engineers
Ecoe554 Machine Learning

Spring 2004
Comp101 Structure and Interpretation of Computer Programs

Fall 2003
Comp100 Computer Applications
Ecoe554 Machine Learning

Spring 2003
Math102 Calculus

İmkansızı başarmak

2007-01-15T01:51:00.000+02:00

"İmkansızı başarmak" üzere yola çıkan mühendislerin kahramanlık
öykülerini okumayı severim. Richard Rhodes'un "The Making of the
Atomic Bomb", ya da Ben Rich'in "Skunk Works" kitapları bu açıdan
etkileyicidir. Malesef böyle öyküler genelde savaş sırasında ve
büyük devlet projeleri desteğinde ortaya çıkıyor, ama bunu başka
bir mesajda ele alırız. Amacım, her yeni fikrin "acaba dışarıda
böyle bir uygulama var mı" şüpheciliğinden geçirildiği, en büyük
firmaların bile argeye ciddi olarak girmekten korktuğu bu ülkede,
neyin imkanlı neyin imkansız olduğunu ve yeni fikirleri "başkası
yapmış mı"'nın ötesinde nasıl değerlendirebileceğimizi tartışmaya
açmak. Bakarsınız bir gün bir konuda liderliği ele geçiririz, ve
"başkası ne yapmış" diye kopya çekme imkanımız kalmaz ve geçmişe
değil geleceğe bakmak zorunda kalıveririz :)

Bu sefer George Dyson'un "Project Orion" kahramanlık öyküsünü
okurken, projedeki mühendislerin düşünce yapısıyla ilgili ilginç
bir paragraf dikkatimi çekti. Önce Borges'in "Evrensel Kütüphane"
fikrini açmalıyım. Değişik yazarların değişik şekillerde formüle
ettiği bu hayali kütüphane, tüm olası kitapların, tüm olası
teknolojilerin, tüm olası organizmaların raflarından birinde yer
aldığı bir olasılıklar evrenidir.

Dyson proje lideri Ted Taylor hakkında şöyle diyor (parantezler
benim): "Kitaplardan, genotiplerden, ya da teknolojilerden oluşan
bir evrensel kütüphane, çok boyutlu bir uzayda gittikçe genişleyen
bir olasılıklar bulutu gibidir. Doğa kanunları en dış sınırları
oluşturur (hiyerarşi #4). Bu olasılıklar atmosferinin ortasında
yoğunlaşmış daha küçük bir bulut halihazırda elimizde olan
parçalardan üretebileceğimiz organizma ve teknolojileri temsil
eder (hiyerarşi #2). Son olarak merkezdeki küçük bir çekirdek şu
anda var olan kitapları, organizmaları ve teknolojileri temsil
eder (hiyerarşi #1). Ted, Orion'u çekirdekten dışarı doğru küçük
adımlarla değil diğer yönde geliştirmek istiyordu: doğa
kanunlarıyla başlanacak; önce imkanlılık, daha sonra pratiklik
sınırları çizilecek; son olarak bulunan noktalardan geriye, şu an
elimizde olan teknolojilere doğru bir yol çizilecekti. Ancak böyle
küçük adımlarla değil dev hamlelerle ilerlemek mümkün olabilirdi."

Bir gün sınırlarımıza doğa kanunlarından başlayarak karar
verebilmek dilegiyle!

Deniz Yuret's Homepage

Gamma distribution

Ergun Biçici, Ph.D. 2011

RegMT System for Machine Translation, System Combination, and Evaluation

Instance Selection for Machine Translation using Feature Decay Algorithms

ACL 2011 Tutorials

Semantic Structures by Ray Jackendoff

The Noisy Channel Model for Unsupervised Word Sense Disambiguation

A tutorial on language modeling with SRILM

From Eternity to Here by Sean Carroll

Bologna Translation Service

Plausibility vs. Inference

Research focus

Naive Bayes is a joint Maximum Entropy Model

Next Generation Parser Evaluation

Computational Models of Narrative

Probability twisters

Anharmonicity, mode-coupling and entropy in a fluctuating native protein

Istanbul Marathon 2010

Adam's Tongue by Derek Bickerton

Author Alerts

Unsupervised Part of Speech Tagging Using Unambiguous Substitutes from a Statistical Language Model

SemEval-2010 Task 12: Parser Evaluation using Textual Entailments

L1 Regularized Regression for Reranking and System Combination in Machine Translation

The Trouble with Physics by Lee Smolin

Biçimbilimsel Çözümleme

CFP: Parser Evaluation using Textual Entailments (PETE)

Preprocessing with Linear Transformations that Maximize the Nearest Neighbor Classiﬁcation Accuracy

L1 Regularization for Learning Word Alignments in Sparse Feature Matrices

The Noisy Channel Model for Unsupervised Word Sense Disambiguation

Emacs Turkish mode

Permutasyon, Kombinasyon ve 12 kardeşleri

Unsupervised morphological disambiguation using statistical language models

How to speak

Turkish Language Resources

Önder Eker, M.S. 2009

ACL 2009 Notes

Modeling Morphologically Rich Languages Using Split Words and Unstructured Dependencies

Morphological cues vs. number of nominals in learning verb types in Turkish: The syntactic bootstrapping mechanism revisited

Natural Language Processing summer course at Sabanci University

Deniz Yuret's Math Problems

Dennett in Istanbul

Matematik nereden gelir

Classification of semantic relations between nominals

Incandescence by Greg Egan

Ergun's English-Turkish machine translation notes

Turkish morphology presentation

İngilizce Türkçe otomatik tercüme

Neşe Aral, M.S. 2009

Show and Tell

Morphological cues vs. number of nominals in learning verb types in Turkish: Syntactic bootstrapping mechanism revisited

Parser Training and Evaluation using Textual Entailments

Discriminative vs. Generative Approaches in Semantic Role Labeling

Ahmet Engin Ural, M.S. 2008

Smoothing a Tera-word Language Model

Olasılık ve kehanet

SRILM ngram smoothing notes

ngram-discount

NAME

NOTATION

DESCRIPTION

OPTIONS

FILE FORMATS

SEE ALSO

BUGS

AUTHOR

Verimli Düşünce Alışkanlıkları

DARPA Urban Challenge

King Kong ve Fizik

Simetri üzerine

Düşünce deneylerine iyi bir örnek

Bilim budalalığı

Nedenciler ve Nasılcılar

Mehmet Ali Yatbaz, M.S. 2007

Düşünce deneyleri

Hearing

Tanrının işine karışmak

The CoNLL 2007 Shared Task on Dependency Parsing

Evrenin israfkarlığı

Düşünceleri okuyabilmek