text:
Fixed-to-Variable Length Distribution Matching

Fixed-to-variable length (f2v) matchers are used to reversibly transform an input sequence of independent and uniformly distributed bits into an output sequence of bits that are (approximately) independent and distributed according to a target distribution. The degree of approximation is measured by the informational divergence between the output distribution and the target distribution. An algorithm is developed that efficiently finds optimal f2v codes. It is shown that by encoding the input bits blockwise, the informational divergence per bit approaches zero as the block length approaches infinity. A relation to data compression by Tunstall coding is established.

I. INTRODUCTION
Distribution matching considers the problem of mapping uniformly distributed bits to symbols that are approximately distributed according to a target distribution. In difference to the simulation of random processes [1] or the exact generation of distributions [2], distribution matching requires that the original bit sequence can be recovered from the generated symbol sequence. We measure the degree of approximation by the normalized informational divergence (Idivergence), which is an appropriate measure when we want to achieve channel capacity of noisy and noiseless channels [3,Sec. 3.4.3 & Chap. 6] by using a matcher. A related work is [4], [3,Chap. 3], where it is shown that variable-to-fixed length (v2f) matching is optimally done by geometric Huffman coding and the relation to fixed-to-variable length (f2v) source encoders is discussed. In the present work, we consider binary distribution matching by prefix-free f2v codes.

A. Rooted Trees With Probabilities
We use the framework of rooted trees with probabilities [5], [6]. Let T be the set of all binary trees with 2 m leaves and consider some tree T ∈ T . Index all nodes by the numbers N := {1, 2, 3, . . . } where 1 is the root. Note that there are at least |N | ≥ 2 m+1 − 1 nodes in the tree, with equality if the tree is complete. A tree is complete if any right-infinite binary sequence starts with a path from the root to a leaf. Let L ⊂ N be the set of leaf nodes and let B := N \ L be the set of branching nodes. Probabilities can be assigned to the tree by defining a distribution over the 2 m paths through the tree. For each i ∈ N , denote by P T (i) the probability that a path is chosen that passes through node i. Since each path ends at a different leaf node, P T defines a leaf distribution, i.e., This work was supported by the German Ministry of Education and Research in the framework of an Alexander von Humboldt Professorship. In (a), a uniform leaf distribution U T is chosen, i.e., for each i ∈ L, U T (i) = 1 4 . The leaf distribution determines the node probabilities and branching distributions. In (b), identical branching distributions are chosen, i.e., for each i ∈ B, Q i T = Q, where Q(0) =: q 0 = 2 3 and Q(1) =: q 1 = 1 3 . The branching distributions determine the resulting node probabilities, which we denote by Q T (i). Since the tree is complete, i∈L Q T (i) = 1 and Q T defines a leaf distribution.
i∈L P T (i) = 1. For each branching node i ∈ B, denote by P i T the branching distribution, i.e., the probabilities of branch 0 and branch 1 after passing through node i. The probabilities on the tree are completely defined either by defining the branching distributions {P i T , i ∈ B} or by defining the leaf distribution {P T (i), i ∈ L}. See Fig. 1 for an example.

B. v2f Source Encoding and f2v Distribution Matching
Consider a binary distribution Q with q 1 = Q(0), q 1 = Q(1), 0 < q 0 < 1, and a binary tree T with 2 m leaves. Let Q T (i), i ∈ N , be the node probabilities that result from having all branching distributions equal to Q, i.e. Q i T = Q for each i ∈ B. See Fig. 1(b) for an example. Let U T be a uniform leaf distribution, i.e., U T (i) = 2 −m for each i ∈ L, see Fig. 1(a) for an example. We use the tree as a v2f source code for a discrete memoryless source (DMS) Q. To guarantee lossless compression, the tree for a v2f source encoder has to be complete. Consequently, Q T defines a leaf distribution, i.e., i∈L Q T (i) = 1. We denote the set of complete binary trees with 2 m leaves by C. Each code word consists of log 2 2 m = m bits and the resulting entropy rate at the encoder output is where H(Q T ) is the entropy of the leaf distribution defined by Q T and where D(Q T U T ) is defined accordingly. From (1), we conclude that the objective is to solve The solution is known to be attained by Tunstall coding [7]. The tree in Fig. 1 is a Tunstall code for Q : q 0 = 2 3 , q 1 = 1 3 and m = 2 and the corresponding v2f source encoder is 000 → 00, 001 → 01, 01 → 10, 1 → 11.
The dual problem is f2v distribution matching. Q is now a binary target distribution and we generate the codewords defined by the paths through a (not necessarily complete) binary tree uniformly according to U T . For example, the f2v distribution matcher defined by the tree in Fig. 1 is Denote by i , i ∈ L the path lengths and let L be a random variable that is uniformly distributed over the path lengths according to U T . We want the I-divergence per output bit of U T and Q T to be small, i.e., we want to solve In contrast to (2), the minimization is now over the set of all (not necessarily complete) binary trees with 2 m leaves. Note that although for a non-complete tree we have i∈L Q T (i) < 1, the problem (5) is well-defined, since there is always a complete tree with leaves L ⊇ L and i∈L Q T (i) = 1. The sum in (5) is over the support of U T , which is L. Solving (5) is the problem that we consider in this work.

C. Outline
In Sec. II and Sec. III, we restrict attention to complete trees. We show that Tunstall coding applied to Q minimizes D(U T Q T ) and that iteratively applying Tunstall coding to weighted versions of Q minimizes D(U T Q T )/ E U T (L). In Sec. IV we derive conditions for the optimality of complete trees and show that the I-divergence per bit can be made arbitrarily small by letting the blocklength m approach infinity. Finally, in Sec. V, we illustrate by an example that source decoders are sub-optimal distribution matchers and vice-versa, distribution dematchers are sub-optimal source encoders.

II. MINIMIZING I-DIVERGENCE
Let R be the set of real numbers. For a finite set S, we say that W : S → R is a weighted distribution if for each i ∈ S, W (i) > 0. We allow for i∈S W (i) = 1. The I-divergence of a distribution P and a weighted distribution W is where supp denotes the support of P . The reason why we need this generalization of the notion of distributions and Idivergence will become clear in the next section.
Proposition 1. Let Q be a weighted binary target distribution, and let be an optimal complete tree. Then we find that i. An optimal complete tree T * can be constructed by applying Tunstall coding to Q. ii. If 0 ≤ q 0 ≤ 1 and 0 ≤ q 1 ≤ 1, then T * also minimizes D(U T Q T ) among all possibly non-complete binary trees T , i.e., the optimal tree is complete.
Proof: Part i. We write and hence Consider now an arbitrary complete tree T ∈ C. Since the tree is complete, there exist (at least) two leaves that are siblings, say j and j + 1. Denote by k the corresponding branching node. The contribution of these two leaves to the objective function on the right-hand side of (9) can be written as Now consider the tree T that results from removing the nodes j and j +1. The new set of leaf nodes is L = k ∪L\{j, j +1} and the new set of branching nodes is B = B \ k. Also Q T defines a weighted leaf distribution on L . The same procedure can be applied repeatedly by defining T = T , until T consists only of the root node. We use this idea to re-write the objective function of the right-hand side of (9) as follows. i∈L The right-hand side of (12) is clearly maximized by the complete tree with the branching nodes with the greatest weighted probabilities. According to [8, p. 47], this is exactly the tree that is constructed when Tunstall coding is applied to the weighted distribution Q. Part ii. We now consider q 0 ≤ 1 and q 1 ≤ 1. Assume we have constructed a non-complete binary tree. Because of noncompleteness, we can remove a branch from the tree. Without loss of generality, assume that this branch is labeled by a zero. Denote by S the leaves on the subtree of the branch. Denote the tree after removing the branch by T . Now, where the inequality follows because by assumption q 0 ≤ 1. Thus, for the new tree T , the objective function (11) is bounded as In summary, under the assumption q 0 ≤ 1 and q 1 ≤ 1, the objective function (11) that we want to maximize does not decrease when removing branches, which shows that there is an optimal complete tree. This proves the statement ii. of the proposition.

III. MINIMIZING I-DIVERGENCE PER BIT
The following two propositions relate the problem of minimizing the I-divergence per bit to the problem of minimizing the un-normalized I-divergence.
Let T ⊆ T be some set of binary trees with 2 m leaves and define Proposition 2. We have where Q ∆ T is the weighted distribution induced by Q • 2 ∆ := [q 0 2 ∆ , q 1 2 ∆ ].
Proof: By (15), for any tree T ∈ T , we have We write the left-hand side of (18) as Consider the path through the tree that ends at leaf i. Denote by 0 i and 1 i the number of times the labels 0 and 1 occur, respectively. The length of the path can be expressed as i = 0 i + 1 i . The term Q T (i)2 ∆ i can now be written as Using (20) and (19) in (18) shows that for any binary tree which is the statement of the proposition.

(22)
Then the optimal complete tree is constructed by applying Tunstall coding to Q ∆ T . Proof: The proposition is a consequence of Prop. 2 and Prop. 1.i.

2.T = argmin
By Prop. 3, if we know the I-divergence ∆, then we can find T * by Tunstall coding. However, ∆ is not known a priori. We solve this problem by iteratively applying Tunstall coding to Q • 2∆, where∆ is an estimate of ∆ and by updating our estimate. This procedure is stated in Alg. 1. We first show that ∆ is strictly monotonically decreasing. Let∆ i be the value that is assigned to∆ in step 1. of the ith iteration and denote byT i the value that is assigned toT in step 2. of the ith iteration. Suppose that the algorithm does not terminate in the ith iteration. We havê By step 2, we havê and since by our assumption the algorithm does not terminate in the ith iteration, we have Now assume the algorithm terminated, and letT be the tree after termination. Because of the assignments in steps 1. and 2., the terminating condition implies that for any tree T ∈ C, we have Consequently, we have We conclude that after termination, (∆,T ) is equal to the optimal tuple (∆, T * ) in Prop. 3. Finally, we have shown that ∆ is strictly monotonically decreasing so thatT i =T j for all i < j. But there is only a finite number of complete binary trees with 2 m leaves. Thus, the algorithm terminates after finitely many steps.

IV. OPTIMALITY OF COMPLETE TREES
Complete trees are not optimal in general: Consider m = 1 and Q : q 0 = 5 6 , q 1 = 1 6 . For m = 1, Tunstall coding constructs the (unique) complete binary tree T with 2 leaves, independent of which target vector we pass to it. The path lengths are 1 = 2 = 1. The I-divergence per bit achieved by this is Now, we could instead use a non-complete tree T with the paths 0 and 10. In this case, I-divergence per bit is In summary, for the considered example, using a complete tree is sub-optimal. We will in the following derive simple conditions on the target vector Q that guarantee that the optimal tree is complete.

A. Sufficient Conditions for Optimality
Proposition 5. Let Q be a distribution. If max{q 0 , q 1 } ≤ 4 min{q 0 , q 1 }, then the optimal tree is complete for any m ≥ 1 and it is constructed by Alg. 1.
Proof: According to Prop. 1.ii, the tree that minimizes D(U T Q ∆ T ) is complete if the entries of the weighted distribution Q • 2 ∆ are both less than or equal to one. Without loss of generality, assume that q 0 ≥ q 1 . Thus, we only need to check this condition for q 0 . We have We calculate the value of ∆ that is achieved by the (unique) complete tree with 2 leaves, namely For each m ≥ 1, this ∆ is achieved by the complete tree with all path lengths equal to m. Substituting the right-hand side of (32) for ∆ in (31), we obtain which is the condition stated in the proposition.
B. Asymptotic Achievability for Complete Trees Proposition 6. Denote by T (m) the complete tree with 2 m leaves that is constructed by applying Alg. 1 to a target distribution Q. Then we have and in particular, the I-divergence per bit approaches zero as m → ∞.
Proof: The expected length can be bounded by the converse of the Coding Theorem for DMS [8, p. 45] as Thus, we have The tree T (m) that minimizes the right-hand side is found by applying Tunstall coding to Q. Without loss of generality, assume that q 0 ≥ q 1 . According to the Tunstall Lemma [8, p. 47], the induced leaf probability of a tree constructed by Tunstall coding is lower bounded as We can therefore bound the I-divergence as We can now bound the I-divergence per bit as This proves the proposition.
C. Optimality of Complete Trees for Large Enough m Proposition 7. For any target distribution Q with q 0 < 1 and q 1 = 1 − q 0 , there is an m 0 such that for all m > m 0 , the tree that minimizes is complete.
Proof: Without loss of generality, assume that q 0 ≥ q 1 .
By Prop. 6, we have ∆ m ≤  V. SOURCE CODING VERSUS DISTRIBUTION MATCHING An ideal source encoder transforms the output of a DMS Q into a sequence of bits that are independent and uniformly distributed. Reversely, applying the corresponding decoder to a sequence of uniformly distributed bits generates a sequence of symbols that are iid according to Q. This suggests to design a f2v distribution matcher by first calculating the optimal v2f source encoder. The inverse mapping is f2v and can be used as a distribution matcher.
We illustrate by an example that this approach is suboptimal in general. Consider the DMS Q with Q : q 0 = 0.615, q 1 = 0.385. We calculate the optimal binary v2f source encoder with blocklength m = 2 by applying Tunstall coding to Q. The resulting encoder is displayed in the 1st column of Table I. Using the source decoder as a distribution matcher results in an I-divergence per bit of 0.039206 bits. Next, we use Alg. 1 to calculate the optimal f2v matcher for Q. The resulting mapping is displayed in the 2nd column of Table I. The achieved I-divergence per bit is 0.037695 bits, which is smaller than the value obtained by using the source decoder.
In general, the decoder of an optimal v2f source encoder is a sub-optimal f2v distribution matcher and the dematcher of an optimal v2f distribution matcher is a sub-optimal v2f source encoder.


The Impact of the Combination between Task Designs and Think-Aloud Approaches on Website Evaluation

The growth of the Internet and related technologies has enabled the development of a new breed of dynamic website and applications that are growing rapidly in use, which have had a significant impact on many businesses. Usability testing is a method widely used for measuring the usability of a system from the perspective of real users. The main aim of this paper is to explore the efficiency of three types of usability testing method by discovering usability problems through a combination of three proposed task designs and three types of ‘think-aloud’ approach, and to compare the results of these methods with those of the traditional usability testing method that has been published separately. This is a missing area in usability testing. The quantitative and qualitative data are collected and analysed in order to assess the efficiency of the three combinations in terms of the usability problems encountered and their severity, and the success rate and user satisfaction of the websites being tested, through the feedback received. The research findings show clearly that the task scenarios and how they are designed and combined with different types of ‘think-aloud’ approaches can influence the usability testing results by discovering different types of usability problems, and can affect the results of usability measures, such as success rate, errors number and time spent.

Introduction
The growth of the Internet and new technologies has created new dynamic websites that are growing rapidly in use and are having a significant impact on many businesses. These dynamic websites increasingly being developed in the midst of the Internet revolution and ever-improving information technologies. For example, e-learning websites are now essential for all universities that have a physical workplace. They have websites, and particularly those for e-learning, that have become an integral part of their businesses. The Internet revolution has even led to a large number of universities functioning solely online, without the need of a physical workplace. To keep pace with this development; some companies and organizations such as Intel® Education and the BBC seek to build free online learning websites that are oriented to world-class education at all educational levels. This development in lifelong learning has made the learners' intention to continue using e-learning an increasingly critical issue. Consequently, quality is considered crucial to education in general, and to e-learning in particular. Web design is a key factor in determining the success of e-learning websites, and the users should take priority in the designers' eyes because usability problems in educational websites can have serious ramifications over and above failing to meet the users' needs.
Usability is one of the most significant aspects affecting the user experience. The techniques for measuring the quality of users' experience have been classified under the heading of 'ergonomics' and 'ease-of-use', but more recently under the heading of 'usability' [Oztekin & Uysal, 2010]. ISO defines usability as "the extent to which the product can be used by specified users to achieve specified goals with effectiveness, efficiency, and satisfaction in a specified context of use" [ISO 9241-11, 1998]. During the past decade a variety of Usability Evaluation Methods (UEMs) have been developed, and a number of research studies have compared the effectiveness of different UEMs Alrobai et al., 2012;Ali et al., 2013;Ahmed et al., 2013]. UEMs can be categorized as analytic or empirical; analytic UEMs include techniques such as Heuristic Evaluation (HE), whereas empirical UEMs include a wide range of methods and procedures that are often referred to simply as 'usability (or user) testing' [Nielsen & Molich, 1990;.
Briefly, usability testing is labour-intensive, as it requires real users of the product to be examined whilst performing a set of tasks. These users need to be observed carefully by evaluators in order to record the usability problems encountered by them. Overall, the most important aim of usability testing is the compilation of a list of the usability problems encountered, which will then indicate the necessary changes to make in order to improve the product [Lawand & Hvannberg, 2002].
The recent literature has raised a number of questions and issues in the usability testing field that deserve further research from various viewpoints. For example, many researchers such as , and AlShamari and Mayhew (2010) have investigated the impact of task types on user testing results. However, the impact of task formulation and combining it with different 'think-aloud' approaches is a missing area in usability testing. This paper aims to investigate the efficacy of using three different combinations of task formulation and 'think-aloud' approaches in usability testing. Three out of nine combinations were chosen and tested, which were 'specific task with constructive interaction think-aloud', 'guess task with concurrent think-aloud', and finally, 'free task with retrospective think-aloud'. These were measured against the number of problems found, the users' performance and the overall user experience, as well as other usability measures. This paper is organized thus: Section 2 presents a brief literature review relating to this study; Section 3 describes the methodology and techniques adopted; Section 4 contains the data analysis; Section 5 presents a discussion and highlights interesting findings; and Section 6 presents the conclusion and suggestions for future work.

Literature Review
The concept of user experience has become central to interaction design; it defines how a product behaves and is used in the real world [Rubin & Chisnell, 2008].  describes user experience as what happens to the users when they interact with the system in question. Experience varies from person to person and from product to product because of something calling 'usability'. Usability is a one of the core concepts to have emerged from the human-computer interaction (HCI) field. The literature reveals that usability is not a single 'one-dimensional' property of a user interface; there are many usability attributes that should be taken into account and measured during experimental sessions. For example, whether or not it is easy to learn and to remember, efficient and subjectively pleasing to use, and whether or not there are errors. There are a variety of methods for measuring the usability of a system or product, and they can be divided into three categories: usability testing (below), usability inspection (e.g. Heuristic Evaluation), and inquiry methods (e.g. interviewing users). As mentioned before, the first is empirical and the other two are analytical.
Usability testing (or user testing) is the method addressed in this paper. This is considered to be the most important evaluation method for ensuring system quality, and particularly for websites, although it is claimed to be costly [Oztekin & Uysal, 2010]. It requires participants to perform a set of tasks, usually under laboratory conditions. These tasks are performed without including any information or clues as to how to complete the tasks or scenarios, and with no help provided to the user during the test session. The performance of these tasks are monitored through 'observation' and then assessed by the evaluator/researcher in order to record the usability problems encountered by the users. All the observed data, such as error numbers, time spent, success rate and user satisfaction, are recorded for analysis [Nielsen, 1994]. Dumas and Redish (1991) point out that a fruitful usability testing session requires careful planning and attention to detail. Thus, there is a general procedure for conducting user testing: 1) Planning a usability test; 2) Selecting a representative sample and recruiting participants; 3) Preparing the test materials and actual test environment; 4) Conducting the usability test; 5) Debriefing the participants; 6) Analysing the data of the usability test; and 7) Reporting the results and making recommendations to improve the design and effectiveness of the system or product. The aim of applying usability testing is to procure a list of usability problems, which are defined as flaws in the design of a system that make the attainment of a particular goal (through the use of the system) ineffective and/or inefficient, and thus lower the users' level of satisfaction in using it ]. These problems can be classified into different groups, in which a numeric scale from 0 to 4 is often used to measure the severity of each problem. 0 means "not a usability problem at all", 1 means "cosmetic problem that should be fixed if enough time is available", 2 means "minor problem with low priority", 3 means "major problem with high priority", and 4 means "catastrophic problem that is imperative to fix". Usability testing involves the collection of measurable data that can be compared with those of other websites; in particular, data on time spent, task success rate, error numbers, satisfaction rate and other metrics [Tan et al., 2009].
There are various factors affecting usability testing and its results, as Figure 1 shows. These factors include the number of users ('sample size'), the usability measures employed, the users' characteristics ('user profiling'), the use of the 'think-aloud' protocol (in its varying forms), the formulation of the tasks, and environment testing. Firstly, usability testing requires real users to perform realistic tasks; however, there is no agreement amongst researchers about the most appropriate number of users. Nielsen (2000) claims that five users are enough to reveal 85% of all the usability problems in a user interface, and that time and resources are wasted if more than five are involved. Rubin and Chisnell (2008) confirm that the first of the three to five users can detect the majority of the usability problems, and that each additional user is unlikely to uncover new ones. Several researchers have suggested that 5 to 12 users are sufficient for the purposes of website usability testing; however, others have suggested that 20 users, for the purpose of benchmarking, are needed for an experiment [Nielsen, 2006;Rubin & Chisnell, 2008]. Lindgarrd and Chattatichart (2007) confirm, in the findings of their paper which discusses user numbers and tasks, that "the result casts doubt on the role of the number of users in a usability test but confirms the important role of task coverage".
The second factor is 'usability measures'. This is the most important factor because any failure in measuring the level of usability means failure in the whole evaluation. There are three main ISO standards for measuring usability, and these are efficiency, effectiveness and user satisfaction. Efficiency can be calculated through measuring input rate, task completion time and other factors. Effectiveness can be worked out through measuring binary task completion, accuracy and the number of errors. Satisfaction can be measured by asking about the user's feelings towards the system or through conducting standardized questionnaires with the users after the test [Sauro & Kindlund, 2005;. However, there are other usability measures such as success rate, which is defined by Nielsen (2001) as the percentage of tasks that users complete correctly and successfully. He divides task completion into three categories, which are 'completed successfully without error', 'completed partially with some errors but with recovery from those errors', and 'failure to complete' [Nielsen, 2001]. Overall, usability measures can produce different types of result, but which system to measure, what to measure and how to measure it are critical questions in determining the most appropriate usability measures.
The third factor is 'user characteristics'; it is important to consider the user profile from all angles. Users differ in age, nationality, background, gender and, crucially, computing skills. Each one of these factors may play a significant role in usability testing. Molich et al., (2004) states, "usability testing effectiveness is dependent on the tasks given, the methodology used and the users' characteristics".

Please see figure 1 in the PDF version of the article
Regarding the fourth factor, there are various techniques that supplement usability testing, the 'think-aloud' protocol being the most widely used. It is employed during the test when the users are asked to think out loud whilst performing their tasks and their thoughts, feelings, and opinions are recorded. This technique can effectively help evaluators to capture how users interact with an interface and what is happening on the screen [Rubin & Chisnell, 2008]. It has been claimed that one-third of 'severe' usability problems can be discovered through this technique ]. However, the environmental setting of the usability test can sometimes influence the effectiveness of the 'think-aloud' protocol, and it does not always help when the users are not in their natural surroundings; this means that users may not feel as relaxed and may feel unable to talk or express their thoughts and ideas freely in a restricted and unfamiliar laboratory environment [Haak & Jong, 2004]. Furthermore, Rubin and Chisnell (2008) suggested that if the tasks are designed to assess the efficiency of a system (i.e. measuring time spent on tasks) then 'think-aloud' protocol should be avoided as it may negatively impact on the performance of the users. The 'think-aloud' protocol has been generally used in achieving three goals; firstly, to find evidence for models and theories of cognitive processes; secondly, to discover and understand general patterns of behaviour in the interaction with documents or applications in order to create a scientific basis for designing; and thirdly, to test specific new documents or applications in order to troubleshoot and revise them ].
There are three types of 'think-aloud' protocol, which are 'concurrent', 'retrospective' and 'constructive interaction'. The concurrent 'think-aloud' type is the most common; this involves participants verbalising their thoughts whilst performing tasks in order to evaluate a product. 'Retrospective think-aloud' is less frequently used; in this method participants perform their tasks silently, and comment on their work afterwards by means of recording of their performance. Constructive interaction is more commonly known as 'co-discovery learning', where two participants work together in performing their tasks, verbalising their thoughts through interaction (with each other?) [ Van den Haak et al., 2004]. On the one hand it has been argued that 'think-aloud' protocol should be avoided in certain circumstances, as mentioned above, but on the other hand, Tullis and Albert (2008) assess the degree to which it can actually influence users' performance, concluding that this technique can in fact enhance performance because it helps users to focus more on the tasks. However, some researchers when employing the concurrent type have concerns about reactivity, i.e. the possibility that the act of speaking concurrently may influence user performance through distracting their attention and concentration; the effort of fully verbalizing the steps taken in the task may change the ways that users attend to the task components. For this reason the retrospective 'think-aloud' type has been proposed in order to avoid the problems of 'concurrent think-aloud; it is assumed to be the most fruitful in terms of problems reported per participant [Van den Haak et al., 2004]. Furthermore, 'co-discovery learning' (constructive interaction) has been claimed to be the most suitable method for evaluating collaborative systems and also to be the most appropriate method for usability testing with children [Nielsen, 1994].
The fifth factor in usability testing is the design of the tasks. Many researchers are aware that task design is an important factor in the design of adequate Web usability tests. The tasks designed for Web usability testing should focus on the main functions of the system. The tasks should cover the following aspects: 1) Product page; 2) Category page; 3) Display of records; 4) Searching features; 5) Interactivity and participation features; and 6) Sorting and refining features. The tasks can be selected from four different perspectives. These are: 1) Tasks that are expected to detect usability problems; 2) Tasks that are based on the developer's experience; 3) Tasks that are designed for specific criteria; and 4) Tasks that are normally performed on the system. Researchers also recommend that the tasks should be short and clear, in the users' language, and based on the system's goals.  found that task design can play a vital role in the usability testing results, where it can be shown that changing the design of the task can produce differences in the results. They propose and examine three different types of task formulations, which are structured tasks, uncertain tasks and problem-solving tasks. They find that structured tasks are able to identify superficial and minor usability problems whereas the problem-solving tasks are able to identify usability disasters and major problems. Furthermore, , having designed two sets of tasks, which were 'simple tasks' and 'complex tasks', find that simple tasks impact differently on the website navigation structure, user performance, and perceptions of usability than complex tasks.
The sixth factor is the test environment. Generally, user testing takes place in a controlled laboratory. Tullis et al., (2002) discover several cases where the product works fine in the laboratory but not in the real world. They find that the conditions under which the product's use is tested are different to the conditions for actual use.  list four aspects when seeking to understand why a laboratory experiment sometimes fails: 1) The users' motivation can be greatly diminished or even destroyed by the atmosphere of a controlled laboratory; 2) A laboratory does not take into account the social context (of supporting and motivating the users if they need it); 3) A laboratory setting does not consider the time context where, in reality, users may leave their work and resume it later; and 4) A laboratory does not take into account the user's work context (users may feel disinclined to invest time and effort in something that they see as someone else's job). However, conducting experiments in a laboratory can increase their validity, can facilitate system comparisons, and can offer a controlled area where all interactions with the system can be closely recorded and monitored Nielsen, 2009].
In conclusion, further research should be carried out to investigate the impact of task formulation on usability testing, as recommended by  and .
Furthermore, there is no research that investigates the impact on the results of user testing of a combination of different types of task formulation and different types of think-aloud technique. Many researchers use traditional user testing which consist of simple tasks and observation Manzari and Trinidad, 2013]. This research will also compare the proposed combined methods here with the results of the traditional user testing in the paper written by AlRoobaea et al., (2013) on the same websites. This will help us discover which method can provide a better performance in the identification of usability problems. Consequently, this research will consider all these gaps and it will present useful information in the HCI field.

Research Methodology
The experimental approach was selected to achieve the research objectives outlined above. The educational domain was chosen, and three educational websites were selected for different reasons; firstly, they are all completely free educational websites; secondly, they are interactive and are supported by three wellknown companies with a wide range of users; and thirdly, they meet the research objectives and requirements through having various functions, processes and features. These websites are BBC KS3bitesize, Skoool, and Academic Earth. Three experiments were employed on each. Each experiment employed one design of task and one type of 'think-aloud' protocol. This section presents an explanation of the test procedures in these experiments, including the quantitative and qualitative data.

Testing procedures
The user testing was conducting by giving a quick introduction to the task designs; think-aloud approaches and the purpose of the study to each user. The next step was to explain the testing environment and how to use the equipment, followed by a quick demonstration of how to 'think aloud for each test' while performing the given tasks. Prior to the tests the users had to read and sign the consent letter and fill in a user sheet that included his/her demographic data, such as computer skills, nationality and gender. All the above steps took approximately ten minutes for each test session. The timing of each test started when the user was given the task scenario sheet and asked to read and then perform the task. Once they had finished the session they were asked to rate their satisfaction levels. This was followed by a brief discussion.

The Proposed Tasks
The literature suggests that further work on task design is needed [Lindgaard & Chattratichart, 2007;. This is because giving users only one task design may not achieve the testing goals; however, offering users different designs of task may reveal more usability problems. Three designs were proposed for the tasks to be employed in this study. These three types were: 1. Specific Task: this design of task will guide the users to finding specific information relating to a number of specific questions. This task involves constructive interaction 'thinkaloud' type (co-discovery learning), where two users work together in performing their tasks. This is designed to reveal potential usability problems. For example, the following task is to measure the usability of a website's registration process.
• Work with your friend and go to the website and register.
• Work with your friend and fill in the fields, following the instructions given.

Guess Task: in this task design the users should guess aloud,
saying what information they expect to find behind the functions targeted in the test. This design of task relies on the fact that users are usually uncertain as to whether they will find the information that they are looking for whilst surfing a website. The task involves the concurrent 'thinkaloud' type, which is the most commonly used. The following is an example of this task, which is to measure the usability of a website's post-a-question facility.
• Guess how you can post your question.
3. Free Task: in this task users are allowed to explore the target website freely, based on their own interests. This task involves the retrospective 'think-aloud' type, which means that users perform their tasks silently, and afterwards comment on their work by means of a recording of their performance. The following is an example of this task; it is to measure the usability of a website game.
• Go to the website and enjoy your favourite game in the English section.
Each of these tasks consists of four sub-tasks which represent the key functional aspects of the selected website; i.e. they represent the main features of the website. Although they have been formed differently, the task goals are the same.

Building the Questionnaire
After the users finish their tasks they will be asked to rate their level of satisfaction with the website and task formalization on a scale of 1 to 7, where 1 indicates 'highly unsatisfactory' and 7 indicates 'highly satisfactory'. This scale has been suggested to measure the levels of satisfaction felt by users truthfully following a test [Nielsen & Loranger, 2006]. Also, they will be asked to write down their comments and thoughts in a feedback questionnaire, explaining any reactions that they observed during the test.

User Characteristics
Selecting and recruiting participants must be done carefully; the selection must reflect real users of the targeted websites because engaging inappropriate users will lead to incorrect results, thereby invalidating the experiments. Appropriate users will give confident results; the selection of these users will also encourage them to take part in the experiment . In this experiment the majority of users of the targeted websites were students. They were divided into three groups consisting of 20 students in each; each group was mixed in terms of sex, age, education and computer skills. These conditions should deliver reliable and accurate results; they may also play a significant role in the accuracy of the usability testing results. Of the 60 students, 40 were pre-university, and 20 were a mix of undergraduates and postgraduates. The users performing the specific tasks were called SC-Group, the users performing the guess tasks were called GC-Group, and the users performing the free tasks were called FR-Group.

The Number of Users Participating in the Experiment
As mentioned in the literature review, 20 users are required for testing each design of task and 'think-aloud' type. This means that 60 students are needed for each website, and, therefore, 180 users were required to conduct this experiment [Nielsen & Loranger, 2006]. They were all introduced to the concept of the 'think-aloud' protocol and its three types, and how to perform the different task types.

Test Environment
The test environment was controlled; it was conducted in a quiet, child-friendly room. Also, we attempted to find out what our users regularly used, i.e. a familiar type of machine, browser and Internet connection speed, and set it up for them before the test.

The Observer
As mentioned above, usability testing requires an observer, and the researcher adopted this role in all the sessions, noting all the comments made by the users. He used a stopwatch to record the time spent by each user on each task, and an observation sheet to write down the behaviour of each user and the number of problems encountered.

Severity Rating Assessment
A severity assessment sheet was prepared in order to rank each usability problem on a scale of 0 to 4 in accordance with the literature review, and after listing all the usability problems they had encountered an evaluation was conducted for each user.
This severity scale was used by Nielsen for prioritizing usability problems, as the severity sheets can then be used to compare the problems discovered by each group [Nielsen, 1994].

Piloting the test
There are two objectives in conducting a pilot study. The first one is to assess all the materials, including tasks, questionnaires and procedures, checking the language (to avoid any ambiguities) and ensuring that all the tasks have the same goal (although with different formulation). This objective was achieved by engaging independent expert evaluators. The second one is to assess the time needed for each test. This objective was achieved by engaging three users, each one performing one type of task. The users' behaviour was monitored and all the usability measures were assessed; the post-test questionnaires were then given to them by the observer (researcher) as they would be in the real testing. All these steps resulted in useful corrections and adjustments to the real test.

Usability Measures Recorded
In the experiment three usability attributes were considered, which were efficiency, effectiveness and satisfaction. These attributes were measured as time spent, task success and user satisfaction, respectively.
• Time spent: the time spent on each task in seconds was recorded in order to measure the efficiency of the website.
• Task success rate: this was used to measure the effectiveness of the website. This was calculated using the following equation: The success rate = (Number of tasks completed successfully) + (Number of tasks completed partly successfully (*0.5)) / the total number of tasks [Nielsen, 2001] • User satisfaction: each user had to rate their satisfaction with the website after finishing the testing session, as indicated in Section 3.2.
Additional data were also collected: • Number of errors: this refers to the number of errors made by a user when attempting to accomplish a task, such as visiting a wrong page. • Usability problems encountered and their severity rate: this is the most important result as it can help the owner, developer and designer to improve their website. Once the problems were found they were assessed in terms of severity, as indicated in the literature review. • Users' comments and feedback: this was collected at the end of each session; the users were asked to comment and to provide feedback with regard to their perceived usability of the website.
• Efficiency: one measure of Efficiency of Usability Evaluation Methods (UEMs) is "the ratio between the number of usability problems detected and the total time spent on the inspection process" . Others can be deduced by dividing the average severity rating by the average time taken, as shown below [Tan et al., 2009]: Efficiency = [Tan et al., 2009] • Thoroughness: this is perhaps the most attractive measure. It is defined as being an indication of the proportion of real problems found using a Usability Evaluation Method (UEM) Average severity rating Average time spent to the total number of known real problems existing in the target design z. It can be calculated by following formula: Thoroughness= [Sears, 1997] • Validity: this is the extent to which a usability evaluation method accurately identifies usability problems. It can be calculated by following formula: Number of real usability problems found Total number of real usability problems Validity= [Sears, 1997] • Effectiveness: this is defined as the ability of a usability evaluation method to identify usability problems related to the user interface of a specific system . It can be calculated by the following formula: Effectiveness = [Sears, 1997] Number of real usability problems found Number of issues identified as a usability problem

Data Analysis
The previous sections describe and explore the objectives of the study, the methods used, the preparation of the experiment and, finally other usability testing measures. This section is a critical part of the experiment. It starts by exploring the users' demographic data, which includes nationality, gender and Web experience. It then examines the quantitative and qualitative data. Finally, the impact of the tasks and the 'think-aloud' types are assessed vis-à-vis on the three websites. Table 2 shows the mean values of the users' Web experience for all three groups. Approximately 4 years was the average for user experience across the three groups.

Quantitative Analysis
Quantitative data is an important part of usability data analysis. It provides a number of useful results, derived from various aspects that include success rate, error number, user satisfaction and time spent. The following sections explore and discuss the quantitative data collected in these experiments and reveal how each group performed with regard to usability measures. Table 3 shows the success rate for each group when using the three websites. The BBC KS3bitesize groups had the lowest overall success rate. For this website, FR-Group had the highest success rate of the three groups, which was expected because they performed tasks they were interested in and paid more attention to their tasks because they did not have to speak while doing them. They scored a 58% success rate, which means that 58% of the tasks, on average, were completed successfully by the users. Although SC-Group discovered fewer usability problems than GC-group, they scored better than them. SC-Group members were observed performing tasks very successfully in the first stage, when they were asked to explore the website and familiarise themselves with it. They were more focused on accomplishing this task as they were expecting to encounter problems later. The actual tasks were limited to finding an answer and so they knew what they were looking for. Also, the constructive 'think-aloud' procedure helped them to clarify their tasks. This is perhaps the main difference between SC-Group and GC-group.

Success rate
The Skoool groups ranked second in terms of success rate. They scored 62%, which means that 62% of the tasks, on average, were completed successfully by the users. FR-Group again had the highest success rate, followed by SC-Group and GC-group respectively. It can be seen clearly that GC-Group were able to score more partially successful tasks than successful ones, as they attempted different ways and visited different pages to accomplish each task. Also, the concurrent 'think-aloud' procedure may have played a role in producing more failed tasks. This may be because this procedure distracted their attention, lowered their level of concentration and ultimately influenced their task performance. The Academic Earth groups had the highest success rate of the three website groups. These groups scoured 63%, which means that 63% of the tasks, on average, were completed successfully by the users. SC-Group had the highest number of failed tasks of the three groups. This may be because they had doubts and were uncertain of their ability to guess and accomplish a task successfully. Overall, the FR-Group success rate was somewhat higher than those of SC-Group and GC-Group.
Despite these observations none of the three websites scored below 50%, which is claimed by Nielsen to be the average for most websites, arguing that users generally fail to perform a task successfully the first time [Nielsen, 2001]. In terms of the group types, GC-Group achieved below 50% in BBC KS3bitesize, and came close to this score with the other websites. This implies that the website's success rate can be described as acceptable and is in line with this study.

Please see table 3 in the PDF version of the article
The number of errors made Table 4 shows that the BBC KS3bitesize groups made more errors than the other website groups. FR-Group made fewer errors than the other groups, where an average of 1.5 errors were made by each user while he/she performed this type of task using 'think-aloud' protocol on the BBC KS3bitesize website, and 1.3 and 1.2 errors respectively on the Skoool and Academic Earth websites. GC-Group made the most errors. This was probably because this group did not have any guidelines or specific objective when performing the tasks. Also, the concurrent 'thinkaloud' procedure may have had a negative impact, thus contributing to the number of errors made. Difficulties were also encountered because some of the navigation on the Skoool and Academic Earth websites took the users away from the website; also, there were too many windows and help links, and much of the documentation was not very visible. SC-Group came second with 1.7 errors per user, on average, in performing the specific task and the constructive 'think-aloud' procedure on the BBC KS3bitesize website; the average number of errors was 1.5 on both the Skoool and the Academic Earth websites. Thus, it can be seen that different types of task produce different results with regard to the number of errors made by users.

Please see table 4 in the PDF version of the article
Number of usability problems discovered Table 5 shows the number of problems discovered by each group. It shows that GC-Group, in performing guessing tasks with the concurrent procedure, discovered 81% of the total usability problems discovered by all groups on the BBC KS3bitesize website, and 85% and 67% on the Skoool and Academic Earth websites respectively. SC-Group performed specific tasks using Co-Discovery Learning, uncovered only 56% of the total number of discovered usability problems on the BBC KS3bitesize website, and 39% and 50% on the Skoool and Academic Earth websites respectively. The FR-Group found 31% of the total number of usability problems discovered by all groups on the BBC KS3bitesize website, and 31% and 25% on the Skoool and Academic Earth websites respectively. GC-Group performed better than SC-Group in discovering catastrophic, major, minor and cosmetic problems. However, FR-Group was better at discovering minor and cosmetic problems. The majority of the major problems discovered by GC-Group were mostly to do with navigation and structure. This may be because the users were not provided with guidelines telling them what they should do and where they should go; also, they had to speak out loud. On the other hand, SC-Group performed their tasks knowing what they were looking for, i.e. answering a question. Table 6 shows the time spent by each user in performing their tasks, and whether or not they succeeded in carrying them out. GC-Group spent the longest time, longer than SC-Group and FR-Group, the timings being 310, 275 and 244 minutes respectively on the BBC KS3bitesize website. On the Skoool website, GC-Group spent the longest time -340 minutes; SC-Group and FR-Group spent 293 and 237 minutes respectively. On the Academic Earth website, again GC-Group spent the longest time, longer than SC-Group and FR-Group, the timings being 298, 267 and 239 minutes respectively. Again, this is probably due to the type of task and 'think-aloud' procedure performed by the users. For example, GC-Group found themselves in problematic circumstances and having to speaking out loud whilst performing their tasks, which may have affected their concentration and attention. Also, they were trying to understand the situation they were in, and so had to spend time thinking about how to perform each task. FR-Group was free of such hindrances and so were more interested in, and concentrated on, accomplishing their tasks. SC-Group felt confident about how to accomplish their tasks and the constructive interaction procedure was helpful for this group; this is demonstrated in the success rate table (Table  3). The average time spent by each user in all website groups was longer than 3 minutes.  asserted that the time spent by users on a website is less important than other factors such as success rate. Table 7 shows that the Academic Earth group were noticeably less satisfied than the BBC KS3bitesize and the Skoool groups. The FR-Group produced the highest scores, followed by SC-Group and GC-Group in overall evaluations. This indicates that there were certain factors influencing the users which impacted on their satisfaction score for the tested websites, as evidenced by the critical user comments relating to the design features of each website. These factors related to the various activities and functions, such as the games or the 'test and revise' facilities. Also, the users were influenced by the design of each website; a simple and attractive design encouraged and was enthused them. The best example is the BBC KS3bitesize website, which achieved the baseline score for user satisfaction of 4.7, as determined by Nielsen and Loranger (2006) after they had tested 25 websites. Furthermore, it can be seen that FR-Group had the highest satisfaction score of the three website groups. This is probably because the users were given the freedom to perform the required tasks and the retrospective 'think-aloud' procedure was very helpful in achieving their high success rate. GC-Group, using the concurrent procedure had the lowest satisfaction score. This may reflect the fact that they were not given any clues or suggestions to help them complete their tasks, and having to speak out loud may have caused them a certain amount of frustration.

Usability Metrics
It is noticeable in Table 8 that GC-group was more efficient in detecting usability problems and in the total time they spent on the inspection process on the three websites. Also, they were more thorough in discovering the real usability problems on the target websites. Furthermore, they achieved better validity in accurately identifying usability problems on the three websites. Finally, their ability to identify a usability problem that related to the user interface of a specific website was also higher. The SC-Group came second after GC-group, and the FR-Group got the worst result from the three websites.


KooSHO: Japanese Text Input Environment based on Aerial Hand Writing

Hand gesture-based input systems have been in active research, yet most of them focus only on single character recognition. We propose KooSHO: an environment for Japanese input based on aerial hand gestures. The system provides an integrated experience of character input, Kana-Kanji conversion, and search result visualization. To achieve faster input, users only have to input consonant, which is then converted directly to Kanji sequences by direct consonant decoding. The system also shows suggestions to complete the user input. The comparison with voice recognition and a screen keyboard showed that KooSHO can be a more practical solution compared to the existing system.

Introduction
In mobile computing, intuitive and natural text input is crucial for successful user experience, and there have been many methods and systems proposed as the alternatives to traditional keyboard-and-mouse input devices. One of the most widely used input technologies is voice recognition such as Apple Inc.'s Siri. However, it has some drawbacks such as being vulnerable to ambient noise and privacy issues when being overheared. Virtual keyboards 1 require extensive practice and could be errorprone compared to physical keyboards. In order to address these issues, many gesturebased text input interfaces have been proposed, including a magnet-based hand writing device (Han et al., 2007). Because these systems require users to wear or hold special devices, hand gesture recognition systems based on video cameras are proposed, such as Yoon et al. (1999) and Sonoda and Muraoka (2003). However, a large portion of the literature only focuses on single character input. One must consider overall text input experience when users are typing words and phrases. This problem is pronounced for languages which require explicit conversion from Romanized forms to ideographic writing systems such as Japanese.
In this paper, we propose KooSHO: an integrated environment for Japanese text input based on aerial hand gestures. It provides an integrated experience of character input, Kana-Kanji conversion, i.e., conversion from Romanized forms to ideographic (Kanji) ones, and search result visualization. Figure 1 shows the overall procedure using KooSHO. First, (a) a user draws alphabetical shapes in the air, whose hand position is captured by Microsoft Kinect. KooSHO then recognizes characters, and after  Kana-Kanji conversion, the results are shown in a circle centered at the user's shoulder (b). Finally, the user can choose one of the candidates by "touching" it, and (c) the search result using the chosen word as the query is shown in circle again for the user to choose.
KooSHO has several novelties to achieve seamless yet robust text input, including: Non-restrictive character forms -the system does not restrict on the input character forms, unlike Graffiti 2 2 .
Robust continuous recognition and conversion -Aerial handwriting poses special difficulties since the system cannot obtain individual strokes. We solve this problem by employing a discriminative Kana-Kanji conversion model trained on the specific domain.
Faster input by suggestions and consonant input -KooSHO shows suggestions to predict the words the user is about to input, while it allows users to type only consonants, similar to Tanaka-Ishii et al. (2001). We propose direct consonant decoding, which runs Viterbi search directly on the input consonant sequence without converting them back into Kana candidates.
We conducted the evaluations on character recognition and Kana-Kanji conversion accuracy to measure KooSHO's performance. We also ran an overall user experience test, comparing its performance with the voice recognition software Siri and a screen keyboard. Figure 2 describes the overall configuration. A user draws alphabetical shapes in the air, which is captured by Kinect and sent to KooSHO. We 2 http://en.wikipedia.org/wiki/Graffiti_2 Figure 3: Lattice search based on consonants used the skeleton recognition functionalities included in Kinect for Windows SDK v1.5.1. The system consists of the front-end and back-end parts, which are responsible for character recognition and user interface, and Kana-Kanji conversion and suggestion, respectively. We continuously match the drawn trajectory to templates (training examples) using dynamic programming. The trajectory and the templates are both represented by 8 direction features to facilitate the match, and the distance is calculated based on how apart the directions are. This coding system is robust to scaling of characters and a slight variation of writing speed, while not robust to stroke order. This is repeated every frame to produce the distance between the trajectory ending at the current frame and each template. If the distance is below a certain threshold, the character is considered to be the one the user has just drawn.

Character Recognition
If more than one characters are detected and their periods overlap, they are both sent as alternative. The result is represented as a lattice, with alternation and concatenation. To each letter a confidence score (the inverse of the minimum distance from the template) is assigned.

Kana-Kanji Conversion
In this section, we describe the Kana-Kanji conversion model we employed to achieve the consonant-to-Kanji conversion. As we mentioned, the input to the back-end part passed from the front-end part is a lattice of possible consonant sequences. We therefore have to "guess" the possibly omitted vowels somehow and convert the sequences back into intended Kanji sequences. However, it would be an exponentially large number if we expand the input consonant sequence to all possible Kana se-quences. Therefore, instead of attempting to restore all possible Kana sequences, we directly "decode" the input consonant sequence to obtain the Kanji sequence. We call this process direct consonant decoding, shown in Figure 3. It is basically the same as the vanilla Viterbi search often used for Japanese morphological analysis (Kudo et al., 2004), except that it runs on a consonant sequence. The key change to this Viterbi search is to make it possible to look up the dictionary directly by consonant substrings. To do this, we convert dictionary entries to possible consonant sequences referring to Microsoft IME Kana Table 3 when the dictionary structure is loaded onto the memory. For example, for a dictionary entry 福袋/フクブクロ hukubukuro, possible consonant sequences such as "hkbkr," "hukbkr," "hkubkr," "hukubkr," "hkbukr,"... are stored in the index structure.
As for the conversion model, we employed the discriminative Kana-Kanji conversion model by Tokunaga (2011). The basic algorithm is the same except that the Viterbi search also runs on consonant sequences rather than Kana ones. We used surface unigram, surface + class (PoS tags) unigram, surface + reading unigram, class bigram, surface bigram as features. The red lines in Figure 3 illustrate the finally chosen path.
The suggestion candidates, which is to show candidates such as hukubukuro (lucky bag) and hontai (body) for an input "H," are chosen from 2000 most frequent query fragments issued in 2011 at Rakuten Ichiba 4 . We annotate each query with Kana pronunciation, which is converted into possible consonant sequence as in the previous section. At run-time, prefix search is perfomed on this consonant trie to obtain the candidate list. The candidate list is sorted by the frequency, and shown to the user supplementing the Kana-Kanji conversion results.

Experiments
In this section, we compare KooSHO with Siri and a software keyboard system. We used the following three training corpora: 1) BCCWJ-CORE (60,374 sentences and 1,286,899 tokens) 5 , 2) EC corpus, consists of 1,230 product titles and descriptions randomly sampled from Rakuten Ichiba (118,355 tokens). 3) EC query log (2000 most frequent query fragments issued in 2011 at Rakuten Ichiba) As the dictionary, we used UniDic 6 .
Character Recognition Firstly, we evaluate the accuracy of the character recognition model. For each letter from "A" to "Z," two subjects attempted to type the letter for three times, and the accuracy how many times the character was correctly recognized was measured.
We observed recognition accuracy varies from letter to letter. Letters which have similar forms, such as "F" and "T" can be easily misrecognized, leading lower accuracy. For some of the cases where the letter shape completely contains a shape of the other, e.g., "F" and "E," recognition error is inevitable. The overall character recognition accuracy was 0.76.

Kana-Kanji Conversion
Secondly, we evaluate the accuracy of the Kana-Kanji conversion algorithm. We used ACC (averaged Top-1 accuracy), MFS (mean F score), and MRR (mean reciprocal rank) as evaluation measures (Li et al., 2009). We used a test set consisting of 100 words and phrases which are randomly extracted from Rakuten Ichiba, popular products and query logs. The result was ACC = 0.24, MFS = 0.50, and MRR = 0.30, which suggests the right choice comes at the top 24 percent of the time, about half (50%) the characters of the top candidate match the answer, and the average position of the answer is 1 / MRR = 3.3. Notice that this is a very strict evaluation since it does not allow partial input. For example, even if "フィットネスシューズ" fittonesushu-zu (fitness shoes) does not come up at the top, one could obtain the same result by inputting "フィットネ ス" (fitness) and "シューズ" (shoes) separately. Also, we found that some spelling variations such as まつげ and まつ毛 (both meaning eyelashes) lower the evaluation result, even though they are not a problem in practice.
Overall Evaluation Lastly, we evaluate the overall input accuracy, speed, and user experience comparing Siri, a screen keyboard (Tablet PC Input Panel) controlled by Kinect using KinEmote 7 , and KooSHO.
First, we measured the recognition accuracy of Siri based on the 100 test queries. The accuracy turned out to be 85%, and the queries were recognized within three to four seconds. However, about 14% of the queries cannot be recognized even after many attempts. There are especially two types of queries where voice recognition performed poorly -the first one is relatively new, unknown words such as オーガラ ンド (ogaland), which obviously depends on the recognition system's language models and the vocabulary set. The second the is homonyms, i.e., voice recognition is, in principle, unable to discern multiple words with the same pronunciation, such as "包装" (package) and "放送" (broadcast) housou, and "ミョウバン" (alum) and "明晩" (tomorrow evening) myouban. This is where KooSHO-like visual feedback on the conversion results has a clear advantage.
Second, we tried the screen keyboard controlled by Kinect. Using a screen keyboard was extremely difficult, almost impossible, since it requires fine movement of hands in order to place the cursor over the desired keys. Therefore, only the time required to place the cursor on the desired keys in order was measured. The fact that users have to type out all the characters including vowels is making the matter worse. This is also where KooSHO excels.
Finally, we measured the time taken for KooSHO to complete each query. The result varied depending on query, but the ones which contain characters with low recognition accuracy such as "C" (e.g., "チーズ" (cheese)) took longer. The average was 35 seconds.

Conclusion and Future Works
In this paper, we proposed a novel environment for Japanese text input based on aerial hand gestures called KooSHO, which provides an integrated experience of character input, Kana-Kanji conversion, and search result visualization. This is the first to propose a Japanese text input system beyond single characters based on hand gestures. The system has several novelties, including 1) non-restrictive character forms, 2) robust continuous recognition and Kana-Kanji conversion, and 3) faster input by suggestions and consonant input. The comparison with voice recognition and a screen keyboard showed KooSHO can be a more practical solution compared to the screen keyboard.
Since KooSHO is an integrated Japanese input environment, not just a character recognition software, many features implemented in modern input methods, such as fuzzy matching and user personalization, can also be implemented. In particular, how to let the user modify the mistaken input is a great challenge.


On Named Entity Recognition in Targeted Twitter Streams in Polish

This paper reports on some experiments aiming at tuning a rule-based NER system designed for detecting names in Polish online news to the processing of targeted Twitter streams. In particular, one explores whether the performance of the baseline NER system can be improved through the incremental application of knowledge-poor methods for name matching and guessing. We study various settings and combinations of the methods and present evaluation results on five corpora gathered from Twitter, centred around major events and known individuals.

Introduction
Recently, Twitter emerged as an important social medium providing most up-to-date information and comments on current events of any kind. This results in an ever-growing interest of various organizations in tools for real-time monitoring of Twitter streams to collect their businessspecific information therefrom for analysis purposes. Since monitoring the entire Twitter stream appears to be unfeasible due to the high volume of published tweets, one usually monitors targeted Twitter streams, i.e., streams of tweets potentially satisfying specific information needs.
Applications for monitoring Twitter streams usually require named entity recognition (NER) capacity. However, due to the nature of Twitter messages, i.e., being short, noisy, written in an informal style, lacking punctuation and capitalization, containing misspellings, non-standard abbreviations, and non grammatically correct sentences, the application of even basic NLP tools (trained on formal texts) on tweets usually results in poor performances. In the case of well-formed texts such as online news, exploitation of contextual clues is crucial to named entity identification and classification (e.g., 'Mayor of ' in the left context of a capitalized token is a reliable pattern to classify it as city name). Such external evidence is often missing in tweets, and entity names are frequently incomplete, abbreviated or glued with other words. Furthermore, deployment of supervised ML-based techniques for NER from tweets is challenging due to the dynamic nature of Twitter.
In this paper, we report on experiments aiming at tuning a rule-based NER system, initially designed for detecting names in Polish online news, to the processing of targeted Twitter streams. In particular, we explore whether the performance of the baseline NER system can be improved through the utilization of knowledge-poor methods (based on string distance metrics) for name matching and name guessing. In comparison to English, Polish is a free-word order and highly inflective language, with particularly complex declension paradigm of proper names, which makes NER for Polish a more difficult task.
The remaining part of the paper is structured as follows. First, Section 2 provides information on related work. Next, Section 3 describes the baseline NER system and the knowledge-poor enhancements. Subsequently, Section 4 presents the evaluation results. Finally, Section 5 gives a summary and an outlook as regards future research.

Related Work
The problem of NER has gained lot of attention in the last two decades and a vast bulk of research on development of NER from formal texts exists (Nadeau and Sekine, 2007). Although most of the reported work focused on NER for major languages, efforts on NER for Polish have also been reported. (Piskorski, 2005) describes a rule-based NER system for Polish that covers the classical named-entity types, i.e., persons, locations, organizations, as well as numeral and temporal expres-sions. (Marcińczuk and Piasecki, 2007) and (Marcińczuk and Piasecki, 2010) report on a memorybased learning and Hidden Markov Model approach resp. to automatic extraction of information on events in the reports of Polish Stockholders, which involves NER. Also in (Lubaszewski, 2007) and (Lubaszewski, 2009) some generalpurpose information extraction tools for Polish are addressed. Efforts related to creation of a dictionary of Warsaw urban proper names oriented towards NER is reported in Marciniak et al., 2009). (Graliński et al., 2009) present NERT, another rule-based NER system for Polish which covers similar types of NEs as (Piskorski, 2005). Finally, some efforts on CRF-based NER methods for Polish are reported in (Waszczuk et al., 2010) and (Marcińczuk and Janicki, 2012).
While NER from formal texts has been well studied, relatively little work on NER for Twitter was reported. (Locke and Martin, 2009) presented a SVM-based classifier for classifying persons, locations and organizations in Twitter. (Ritter et al., 2011) described an approach to segmentation and classification of a wider range of names in tweets based on CRFs (using POS and shallow parsing features) and Labeled LDA resp. (Liu et al., 2011) proposed NER (segmentation and classification) approach for tweets, which combines KNN and CRFs paradigms. The reported precision/recall figures are significantly lower than the state-of-the-art results for NER from well-formed texts and oscillate around 50-80%. Better results were reported in case of extracting names from targeted tweets (person names from tweets on live sport events) (Choudhury andBreslin, 2011). (Nebhi, 2012) presented a rule-based NER system for detecting persons, organizations and locations which exploits an external global knowledge base on entities to disambiguate NE type. (Liu et al., 2012) proposed a factor graph-based approach to jointly conducting NER and NEN (Named Entity Normalization), which improves F-measure performance of NER and accuracy of NEN when run sequentially. An Expectation-Maximization approach to NE disambiguation problem was reported by (Davis et al., 2012). Finally, (Li et al., 2012) presented an unsupervised system for extracting (no classification) NEs in targeted Twitter streams, which exploits knowledge gathered from the web and exhibits comparable performance to the supervised approaches mentioned earlier.
Most of the above mentioned work on NER in tweets focused on English. To our best knowledge no prior work on NER in tweets in Polish has been reported, which makes our effort a pioneering contribution in this specific field. Our work also contributes to NER from targeted Twitter streams.

Named Entity Extraction from Targeted Tweets in Polish
The objective of this work is to explore various linguistically lightweight strategies to adapt an existing news-oriented rule-based NER system for Polish to the processing of tweets in targeted Twitter streams. Starting from the adaptation of a NER rule-based system to the processing of tweets (Section 3.1), we incrementally refine the approach with, first, the introduction of a string similarity-based name matching step (Section 3.2) and, second, the exploitation of corpus statistics and knowledge-poor method for name guessing (Section 3.3).

NER Grammar for Polish
The starting point of our explorations is an existing NER system for Polish, modeled as a cascade of finite-state grammars using the EXPRESS formalism (Piskorski, 2007). Similarly to rule-based approaches to NER for many other Indo-European languages, the grammars consist of a set of extraction patterns for person, organization and location names. The patterns exploit both internal (e.g., company designators) and external clues (e.g., titles and functions of a person, etc.) for name detection and classification; a simple extraction pattern for person names can be illustrated as follows: This rule first matches a sequence consisting of: a first name (through a gazetteer look-up), an optional initial (gazetteer look-up as well) and, finally, a sequence of characters considered as surname candidate (e.g., capitalized tokens), which was detected by a lower-level grammar 1 and is represented as a structure of type surnamecandidate. The right-hand side of the extraction pattern specifies the output structure of type person with one attribute called NAME, whose value is simply a concatenation of the values of the variables #F, #I and #L assigned to the surface forms of the matched first name, initial and surname candidate respectively.
Overall the grammar contains 15 extraction patterns for person names, 10 for location names, and 10 for organization names. It relies on a huge gazetteer of circa 294K entries, which is an extended version of the gazetteer described in (Savary and Piskorski, 2011) and includes, i.a., 39K inflected forms of both Polish and foreign first names, 86K inflected forms of surnames, 5K of organisation names (only partially inflected), 10K of inflected location names (e.g., city names, country names, rivers, etc.). No morphological analyzer for Polish is used and only a tiny fraction of the extraction patterns relies on morphological information (encoded in the gazetteer). In this original grammar, the patterns are divided into surefire patterns and less reliable patterns (whose precision is expected to be lower). The latter ones are patterns that rely solely on gazetteer information (simple look-up), which might have ambiguous interpretation, e.g., patterns that only match first names in text. When applied on conventional online news, the performance of this original NER grammar oscillates around 85% in terms of F-measure.
In order to process tweets, we slightly modified this grammar, mostly by simplifying it. Since mentions of entities in tweets frequently occur as single tokens (e.g., external evidence as in classical news is often missing), we did not keep the distinction between sure-fire and less-reliable patterns. Furthermore, the original NER grammar 'included' a mechanism (encoded directly in pattern specification) to lemmatize the recognized names as well as to extract various attributes such as titles (e.g., 'Pan' (Mr.)) and position (e.g., 'Prezydent' (president)) for persons. As we are mainly interested in the detection and classification of NEs while processing tweets, these functionalities were not needed and the grammar simply extracts names and their type. This 'reduced' NER grammar constitutes the baseline approach, and will be referred to as BASE in the remaining part of the paper. It is worth mentioning that we tested as well a version of the grammar with lower-cased lexical resources, but due to poor re-sults (mainly due to high ambiguity of lower-case lexical entries) we did not conduct further explorations in this direction.

String distance-based Name Matching
In tweets, names are often abbreviated (e.g., 'Parl. Europ.' and 'PE' are abbreviations of 'Parlament Europejski'), glued to other words (e.g., 'prezydent Komorowski' is sometimes written as 'prezydentKomorowski') and misspelled variants are frequent (e.g., 'Donlad Tusk' is a frequent misspelling of 'Donald Tusk'). The NER grammar 'as is' would fail to recognize the particular names in the aforementioned examples. Therefore, in order to improve the recall of the 'tweet grammar', we perform a second run deploying string distance metrics (in the entire targeted Twitter stream) for matching new mentions of names previously recognized by the NER grammar (see Section 3.1). Furthermore, due to the highly inflective character of Polish, we also expect to capture with string distance metrics non-nominative mentions of names (e.g., 'Rzeczpospolitej -genitive/dative/locative form of 'Rzeczpospolita' -the name of a Polish daily newspaper), which the NER grammar might have failed to recognize.
Inspired by the work reported in (Piskorski et al., 2009) we explored the performance of several string distance metrics. First, we tested the baseline Levenshtein edit distance metric given by the minimum number of character-level operations (insertion, deletion, or substitution) needed to transform one string into another (Levenshtein, 1965). Next, we used an extension thereof, namely Smith-Waterman (SW) metric (Smith and Waterman, 1981), which additionally allows for variable cost adjustment to the cost of a gap and variable cost of substitutions (mapping each pair of symbols from alphabet to some cost). We used a variant of this metric, where the Smith-Waterman score is normalized using the Dice coefficient (the average length of strings compared).
Subsequently, we explored variants of the Jaro metric (Jaro, 1989;Winkler, 1999). It considers the number and the order of the common characters between the two strings being compared. More precisely, given two strings s = a 1 . . . a K and Furthermore, let s = a 1 . . . a K be the characters in s which are common with t (with preserved order of appearance in s) and let t = b 1 . . . b L be defined analogously. A transposition for s and t is defined as any position i such that a i = b i . Let us denote the number of transpositions for s and t as T s ,t . The Jaro similarity is then calculated as: A Winkler variant of Jaro metric boosts this similarity for strings with agreeing initial characters and is calculated as: where δ denotes the common prefix adjustment factor (default value is 0.1) and boost p (s, t) = min(|lcp(s, t)|, p). Here lcp(s, t) denotes the longest common prefix between s and t. Further, p stands for the upper bound of |lcp(s, t)| 2 , i.e., up from a certain length of lcp(s, t) the 'boost value' remains the same.
The q-gram metric (Ukkonen, 1992) is based on the intuition that two strings are similar if they share a large number of character-level qgrams. We used a variant thereof, namely skipgram metric (Keskustalo et al., 2003), which exhibited better performance than any other variant of character-level q-grams based metrics. It is based on the idea that in addition to forming bigrams of adjacent characters, bigrams that skip characters are considered. Gram classes are defined that specify what kind of skip-grams are created, e.g. {0, 1} class means that normal bigrams are formed, and bigrams that skip one character. In particular, we tested {0, 1} and {0, 2} classes. Due to the nature of Twitter we expected skipgrams to be particularly useful in our experiments.
Considering the declension paradigm of Polish we also considered the basic CommonPrefix metric introduced in (Piskorski et al., 2009), which is based on the longest common prefix. It is calculated as: Finally, we evaluated the performance of longest common sub-strings distance metric, which recursively finds and removes the longest 2 Here p is set to 6. common sub-string in the two strings compared. Let lcs(s, t) denote the first longest common substring for s and t and let s −p denote a string obtained by removing from s the first occurrence of p in s. The LCS metric is calculated as: The string distance-based name matching described in this section will be referred to as MATCH-X, with X standing for the name of the string distance metric being used.

Name Clustering
Since contextual clues for recognizing names in formal texts are often missing in tweets, we additionally developed a rudimentary name guesser to boost the recall. Let us also observe that using string distance metrics described in Section 3.2 to match all not yet captured mentions of previously recognized names might not be easy due the fact that the process of creating abbreviations in Twitter is very productive, e.g., 'Rzeczpospolita' appears abbreviated as ' Rzepa', Rzp. or 'RP, which are substantially different from the original name.
The main idea beyond the name guesser is based on the following assumption: given a targeted Twitter stream, if a capitalized word n-gram has a couple of 'similar' word n-grams in the same stream, most of which are not recognized as valid word forms, then such a group of n-grams word are most likely named mentions of the same entity (e.g., person, organization or location, etc.). To be more precise, the name guesser works as follows.
2. Create an initial set of singleton 'name' clusters: 3. Build clusters of simmilar n-grams around the selected uni-and bigrams using the string distance metric m: Assign each word n-gram w in the Twitter stream to at most one cluster C j with j ∈ arg min x∈{1,2,...,k} dist m (s x , w) 5 , and dist m (s j , w) ≤ maxDist, where maxDist is a predefined constant.

Iteratively merge most-simmilar clusters in
5. Discard 'small' clusters: 6. Discard clusters containing high number of n-grams, whose parts are valid word forms, but not proper names: where W ordF orm * (w) = 1 if all the words constituting the word n-gram w are valid word forms, but not proper names, and W ordF orm * (w) = 0 otherwise, e.g., W ordF orm * (Jan Grzyb) = 0 since Grzyb (eng. mushroom) can be interpreted as a valid word form, which is not a proper name, whereas Jan has only proper name interpretation.
7. Use the n-grams in the remaining clusters in C (each of them is considered to contain named mentions of the same entity) to match names in the Twitter stream through simple lexicon look-up.
For computing similarity of n-grams and merging clusters we used the longest common substrings (LCS) metric which performed on average best (in terms of F-measure) in the context of name matching (see Section 3.2 and 4). For checking whether tokens constitute valid word forms we exploited PoliMorf (Woliński et al., 2012), a freely available morphological dictionary of Polish, consisting of circa 6.7 million word forms, including proper names. Proper names are distinguished from other entries in the aforementioned resource.
The name guesser sketched above will be referred to as CLUSTERING. Instead of building the 5 We denote the distance between two strings x and y measured with the string distance metric m as distm(x, y) 6 DIST (Cx, Cy) = Σs∈C x Σt∈C y distm(s,t) |Cx|·|Cy | (average distance between strings in the two clusters) name clusters around n-grams, whose frequency exceeds certain threshold, we also tested building clusters around least frequent n-grams (i.e., whose frequency is ≤ 3), which will be referred to as CLUSTERING-INFRQ. The name guesser runs either independently or on top of the NER grammar described in Section 3.1 in order to detect 'new' names in the unconsumed part of the tweet collection, i.e., names recognized by the grammar are preserved. It is important to emphasize that the clustering-based name guesser only detects names without classifying them.

Dataset
We have gathered tweet collections using Twitter search API 7 focusing on some major events in 2012/2013 and on famous individuals, namely: (a) Boston marathon bombings, (b) general comments on Donald Tusk, the prime minister of Poland, (c) discussion on the public comments of Antoni Macierewicz (a politician of the Law and Justice opposition party in Poland) on the Polish president crash in Smoleńsk (Russia) in 2010, (d) debate on the controversial firing of the journalist Cezary Gmyz from one of the major Polish newspapers Rzeczpospolita and, (e) a collection of random tweets in Polish. Each tweet collection was extracted using simple queries, e.g., "zamach AND (Boston OR Bostonie)" ("attack" AND "'Boston"' either in nominative of locative form) for collecting tweets on the Boston bombings. From each collection a subset of randomly chosen tweets was selected for evaluation purposes. We will refer to the latter as the test corpus, whereas the entire tweet collections will be referred to as the stream corpus.
In the stream corpus, we computed for each tweet: (a) the text-like fraction of its body, i.e., the fraction of the body which contains text, and (b) the lexical validity, i.e., the percentage of tokens in the text-like part of the body of the tweet which are valid word forms in Polish 8 . Figure 1 and 2 show the histograms for text-like fraction and lexical validity of the tweets in each collection in the stream corpus. We can observe that large portion of the tweets contains significant text-like part, which is 7 https://dev.twitter.com 8 For computing lexical validity we used PoliMorf (Woliński et al., 2012), already mentioned in the previous section. also lexically valid. Interestingly, the random collection exhibits lower lexical validity, which is due to more colloquial language used in the tweets in this collection. We built the test corpus by randomly selecting tweets whose text-like fraction of the body was ≥ 80%, additionally checking the language and removing duplicates. These tweets were afterwards manually annotated with person, location and organization names, according to the following guidelines: consideration of unigram entities, non-inclusion of titles, functions and alike, non-inclusion of spurious punctuation marks and exclusion of names starting with '@', since their recognition as names is trivial.
The test corpus statistics are provided in Table 1. We provide in brackets the number of tweets in the corresponding tweet collections in the entire stream corpus. In this test corpus, 86,7% of the annotated names are word unigrams, whereas bigrams constitute 12,7% of the annotated names and 3-and 4-grams account only for a tiny frac-tion (0,6%); this is in line with the characteristics of the Twitter language, which favours quick and simple expressions. For each collection, we computed the name diversity as the ratio between entity occurrences and unique entities, as well as the average number of entities per tweet 9 . Targeted stream corpora show a medium name diversity (except for Boston and Gmyz collections, centred on a very specific location and person name resp.) and a high rate of entity per tweet (around 2.2), in contrast with random corpus which shows a high name diversity (0.79) for a low average number of entity per tweets. Reported to the limited number of characters in tweets (140), the important significant number of entity per tweet in targeted streams accounts, on the one hand, for the usefulness of working on targeted streams and, on the other, for the importance of NER in tweets.

Evaluation
In our experiments we evaluated the performance of (i) the NER grammar (BASE), a combination thereof with (ii) different name matching strategies (MATCH) and (iii) different variants of the name guesser (CLUSTERING, CLUSTERING-INFRQ) and, finally, (iv) the combinations of all techniques. Within the MATCH configuration, we experimented all string distance metrics presented in 3.2 but since Jaro, Jaro-Winkler and Smith-Waterman metrics performed on average worse than the others, we did not consider them in further experiments. We selected the best performing metric, LCS 10 , as the one used by the name guesser (CLUSTERING) in subsequent experiments. As a complement, we measured the performance of the name guesser alone to compare it with BASE. Furthermore, name matching and name guessing algorithms were using the tweet collections in the stream corpus (as quasi 'Twitter stream window') in order to gather knowledge for matching/guessing 'new' names in the test corpus.
We measured the performance of the different configurations in terms of Precision (P), Recall (R) and F-measure (F), according to two different schemes: exact match, where entity types and both boundaries should match perfectly, and fuzzy match, which allows for one name boundary returned by the system to be different from the reference, i.e., either too short or too long on the left or on the right, but not on both. Furthermore, since the clustering-based name guesser described in 3.3 does not classify names, for any settings with this technique we only evaluated name detection performance, i.e., no distinction between name types was made. The overall summary of the results for the entire pool of tweet collections, is presented in Table 3.
In the context of the CLUSTERING algorithm we explored various settings as regards the minimum frequency of an n-gram to be considered as cluster seed (φ parameter -see Section 3.3). More precisely, we tested values in the range of 1 to 30 for all corpora and system settings which included CLUSTERING, and compared the resulting P/R and F figures. An example of a curve with P/R values (exact match) of BASE-CLUSTERING algorithm applied on the 'Boston' corpus with varying values of φ is given in Figure 3. One can observe and hypothesize that the frequency threshold does not impact much the performance. Suchlike curves for other settings were of a similar nature. Therefore we decided to set the φ to 1 in all settings reported in Table 3.

Results analysis
The performance of the NER grammars is surprisingly good, both in case of exact and fuzzy match evaluation. Except for random corpus (which shows rather low performance with 55% precision and 39% recall), precision figures oscillate around 85-95%, whereas recall is somewhat worse (60-75%), as was to be expected. The low recall for 'Gmyz' corpus is due to the non-matching of a frequently occurring person name. Precision and recall figures for each entity type for BASE are given in Table 2. In general, recognition of organization names appears to be more difficult (lower recall), especially in the random corpus.   Extending BASE with MATCH yields some improvements in terms of recall (including random corpus), whereas precision either oscillates around the figures achieved by BASE, or deteriorates. In case of 'Gmyz' corpus, we can observe significant gain in both recall and precision through using the name matching step. With regard to the other corpora, the reason for not obtaining a significant gain could be due to two reasons: (a) the n-grams identified as similar to the names recognized by BASE are already covered by BASE with some patterns (e.g., inflected forms of many entities are stored in the gazetteer), or (b) using string distance metrics in the MATCH step might not be the best method to capture mentions of a recognized entity, as exemplified in Table 4, where the mentions of a newspaper Rzeczpospolita (captured by BASE) may be significantly different, e.g., in terms of the character length.
Regarding the results for CLUSTERING-INFRQ, running it alone, yielded poor results for all corpora, only in case of the'Gmyz' corpus a gain could be observed. CLUSTERING performed better than CLUSTERING-INFRQ for all corpora.
Deploying BASE with CLUSTERING on top of it results in up to 1.5-6% (exact match) and 4-   10% (fuzzy match) gain in F-measure compared to BASE (mainly thanks to gain in recall), except 'Gmyz' corpus, where the gain is higher. The average gain over the four targeted corpora against the best combination of BASE-MATCH in F-measure is 1.3%. We observed comparable improvement for the random corpus. It turned out CLUSTERING often contributes to the recognition of names glued to other words and/or character sequences.
Combining BASE with MATCH-LCS and CLUS-TERING/CLUSTERING-INFRQ yields further improvements against the other settings. In particular, the gain in F-measure of BASE-MATCH-CLUSTERING against BASE, measured over the four targeted corpora, is 10.9% and 16.7% for ex-act and fuzzy match respectively (mainly due to gain in recall).
Considering the nature of Twitter messages the average F-measure score over the four targeted corpora for BASE-MATCH-CLUSTERING, amounting to 77.9% (exact match) and 86.2% (fuzzy match) can be seen as a fairly good result. Although the difference in some of the corresponding scores for exact and fuzzy match appear substantial, it is worth mentioning that CLUSTERING algorithm often guesses name candidates that are either preceded or followed by some characters not belonging to the name itself, which is penalized in exact-match evaluation. This problem could be alleviated through deployment of heuristics to trim such 'unwanted' characters. Another source of false positives extracted by CLUSTER-ING is the fact that this method might, beyond person, organization and location types, recognize any kind of NEs, which, even not very frequent, is penalized since they are not present in our reference corpus.
In general, considering the shortness of names in Twitter, the major type of errors in all settings are either added or missed entities, but more rarely overlapping problems. One of the main source of errors is due to the fact that single-token names, which are frequent in tweets, often exhibit type ambiguity. Once badly recognized, these errors are propagated over the next processing steps.

Conclusions and Outlook
In this paper we have reported on experiments on tuning an existing finite-state based NER grammar for processing formal texts to NER from targeted Twitter streams in Polish through combining it with knowledge-poor techniques for string distance-based name matching and corpus statistics-based name guessing. Surprisingly, the NER grammar alone applied on the four test corpora (including circa 2300 proper names) yielded P, R, and F figures for exact (fuzzy) matching proper names (including: person, organization and locations) of 87.3% (90.5%), 56.3% (58.5) and 67% (69.5%) resp., which can be considered fairly reasonable result, though some variations across tweet collections could be observed (depending on the topic and how people 'tweet' about). The integration of the presented knowledge-poor techniques for name matching/guessing resulted in P, R and F figures for exact (fuzzy) matching names of 84.5% (93.6%), 72.2% (80.0) and 77.9% (86.2%) resp. (setting with best F-measure scores), which constitutes a substantial improvement against the grammar-based approach. We can observe that satisfactory-performing NER from targeted Twitter streams in Polish can be achieved in a relatively straightforward manner.
As future work to enhance our experiments, we envisage to: (a) enlarge the pool of test corpora, (b) carry out a more thorough error analysis, (c) test a wider range of string distance metrics (Cohen et al., 2003), (d) study the applicability of the particular NER grammar rules w.r.t. their usefulness in NER in targeted Twitter streams and (e), compare our approach with an unsupervised MLapproach, e.g. as in (Li et al., 2012).