Colin De

La Higuera

Jean-Christophe Janodet
email: janodet@univ-st-etienne.fr

Frédéric Tantini
email: frederic.tantini@univ-st-etienne.fr

Learning Balls of Strings: A Horizontal Analysis ⋆

Keywords: Language learning, Query learning, Polynomial identification in the limit, Pac-learning

There are a number of established paradigms to study the learnability of classes of functions or languages: Query learning, Identification in the limit, Probably Approximately Correct learning. Comparison between these paradigms is hard. Moreover, when to the question of converging one adds computational constraints, the picture becomes even less clear. We concentrate here on just one class of languages, that of topological balls of strings (for the edit distance), and visit the different learning paradigms in this context. Between the results, we show that surprisingly it is technically easier to learn from text than from an informant.

Introduction

When aiming to prove that a class of languages is learnable there have been typically three different settings:

-Identification in the limit [START_REF] Gold | Language identification in the limit[END_REF][START_REF] Gold | Complexity of automaton identification from given data[END_REF] sees the learning process as one where information keeps on arriving about a target language. The Learner keeps making new hypothesis. Convergence takes place if there is always a moment where the process is stationary and then the hypothesis is correct. -Pac-learning consists in learning in a setting where a distribution over the strings can be used to sample examples both to build the hypothesis and to test this hypothesis [START_REF] Valiant | A theory of the learnable[END_REF]. Two parameters can be fixed. The first (ǫ) measures the error that is made (which corresponds to the probability that a string is classified wrongly), and the second (δ) measures the probability that the sampling process has gone wrong. -Query learning (sometimes called active learning) is the process of being able to interrogate an Oracle about the language to be learned, in a formalised way [START_REF] Angluin | Queries and concept learning[END_REF].

The three settings are usually difficult to compare; Using computability theory, one reference is [START_REF] Jain | Systems That Learn[END_REF]. The comparison becomes even harder when complexity issues are discussed. Some exceptions are the work by Angluin comparing Paclearning and using equivalence queries [START_REF] Angluin | Negative results for equivalence queries[END_REF], the work by Pitt relating equivalence queries and implicit prediction errors [START_REF] Pitt | Inductive inference, DFA's, and computational complexity[END_REF], comparisons between learning with characteristic samples, simple Pac [START_REF] Li | Learning simple concepts under simple distributions[END_REF] and Mat in [START_REF] Parekh | On the relationship between models for learning in helpful environments[END_REF]. Other analysis of polynomial aspects of learning grammars, automata and languages can be found in [START_REF] Pitt | Inductive inference, DFA's, and computational complexity[END_REF][START_REF] Kearns | Cryptographic limitations on learning boolean formulae and finite automata[END_REF][START_REF] De La Higuera | Characteristic sets for polynomial grammatical inference[END_REF]. An alternative approach to efficiency issues in inductive inference can be found (for pattern languages) in [START_REF] Zeugmann | Can learning in the limit be done efficiently?[END_REF].

If the customary approach is to introduce a learning paradigm and survey a variety of classes of languages for this paradigm, we choose here to visit just one class, that of balls of strings for the edit or levenshtein distance [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions, and reversals[END_REF]. These were shown to be learnable from noise [START_REF] Tantini | Identification in the limit of systematic-noisy languages[END_REF] and from correction queries [START_REF] Becerra-Bonache | Learning balls of strings with correction queries[END_REF].

The results we obtain here are generally negative: Polynomial identification in the limit from an informant is impossible, for most definitions, and it is the same when learning from membership and equivalence queries. Pac-learning is also impossible in polynomial time, at least if we accept that RP = N P.

On the other hand, the errors are usually due to the counterexamples, and if we learn from text (instead of from an informant or when we count only mind changes) we get several positive results: Only a polynomial number of mind changes or of prediction errors are made. This constitutes a small surprise as one would think the more information one gets for learning, the richer the classes one can learn would be.

In Section 2 we introduce the definitions corresponding to balls of strings and complexity classes. In Sections 3, 4 and 5, we focus on so-called good balls only and present the results concerning Pac-learning, query learning and polynomial identification in the limit, respectively. We list our learning results on general balls in Section 6 before concluding in Section 7.

Definitions

Languages and Grammars

An alphabet Σ is a finite nonempty set of symbols called letters. We suppose in the sequel that |Σ| ≥ 2. A string w = a 1 . . . a n is any finite sequence of letters. We write λ for the empty string and |w| for the length of w. Let Σ ⋆ denote the set of all strings over Σ. A language is any subset L ⊆ Σ ⋆ . Let IN be the set of non negative integers. For all k ∈ IN, let Σ ≤k = {w ∈ Σ ⋆ : |w| ≤ k} and Σ >k = {w ∈ Σ ⋆ : |w| > k}. The symmetrical difference A ⊕ B between 2 languages A and B is the set of all strings that belong to exactly one of them.

Grammatical inference aims at learning the languages of a fixed class L (semantics) represented by the grammars of a given class G (syntax). L and G are related by a semantical naming function

L : G → L that is total (∀G ∈ G, L(G) ∈ L) and surjective (∀L ∈ L, ∃G ∈ G s.t. L(G) = L).
For any string w ∈ Σ ⋆ and language L ∈ L, we shall write L |= w if def w ∈ L. Concerning the grammars, they may be understood as any piece of information allowing a given parser to recognize strings. For any string w ∈ Σ ⋆ and representation G ∈ G, we shall write G ⊢ w if the parser answers Yes given G and w. Basically, we require that the semantical function matches the parser: G ⊢ w ⇐⇒ L(G) |= w.

Finally, we will mainly consider learning paradigms subject to efficiency constraints. In order to define them, we will use G to denote the size of the grammar G (e.g., the number of states in the case of Dfa). Moreover, given a set S of strings, we will use S to denote the sum of the lengths of the strings in S. Finally, we will use the single bar notation | • | for the cardinality of sets.

Balls of Strings

The edit distance d(w, w ′ ) is the minimum number of primitive edit operations needed to transform w into w ′ [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions, and reversals[END_REF]. The primitive operation is either (1) a deletion: w = uav and w ′ = uv , or (2) an insertion: w = uv and w ′ = uav, or (3) a substitution: w = uav and w ′ = ubv, where u, v ∈ Σ ⋆ , a, b ∈ Σ and a = b. E.g., d(abaa, aab) = 2 since abaa -→ aaa -→ aab and the rewriting of abaa into aab cannot be achieved with less than 2 steps. Notice that d(w, w ′ ) can be computed in O (|w| • |w ′ |) time by dynamic programming [START_REF] Wagner | The string-to-string correction problem[END_REF].

It is well-known that the edit distance is a metric [START_REF] Crochemore | Algorithmique du Texte. Vuibert[END_REF], so it conveys to Σ ⋆ the structure of a metric space. Therefore, it is natural to introduce the balls of strings. The ball of centre o ∈ Σ ⋆ and radius r ∈ IN, denoted B r (o), is the set of all strings whose distance is at most r from o: B r (o) = {w ∈ Σ ⋆ : d(o, w) ≤ r}. E.g., if Σ = {a, b}, then B 1 (ba) = {a, b, aa, ba, bb, aba, baa, bab, bba} and B r (λ) = Σ ≤r for all r ∈ IN. We denote by BALL(Σ) the family of all the balls:

BALL(Σ) = {B r (o) : o ∈ Σ ⋆ , r ∈ N}.
We represent a ball B r (o) by the pair (o, r) itself. Indeed, its size is |o| + log r. Moreover, deciding whether w ∈ B r (o) or not is immediate: One only has to (1) compute d(o, w) and ( 2) check whether this distance is at most r, which is achievable in time O (|o| • |w| + log r). Finally, as |Σ| ≥ 2, we can show that (o, r) is a unique thus canonical representation of B r (o) [START_REF] Becerra-Bonache | Learning balls of strings with correction queries[END_REF].

A good ball is a ball whose radius is at most the length of the centre. The advantage of using good balls is that there is a natural relation between the size of the centre and the size of the border strings. We denote by GB(Σ) the class of all the good balls.

Complexity Classes

See [START_REF] Garey | Computers and Intractability[END_REF] for a comprehensive survey. Here, we only wish to recall that RP ('Randomised Polynomial Time' ) is the complexity class of decision problems for which a probabilistic Turing machine exists and (1) it always runs in time polynomial in the input size, [START_REF] Gold | Complexity of automaton identification from given data[END_REF] if the correct answer is No, it always returns No and (3) if the correct answer is Yes, then it returns Yes with probability > 1 2 (otherwise, it returns No).

The algorithm is randomised since it is allowed to flip a random coin while it is running. It should be noted that because the error (in the negative case) is less that 0.5, by repeating the run of the algorithm as many times as necessary, the actual error can be brought to be as small as one wants. Notice that the algorithm only makes one sided errors. The strong belief and assumption is that RP = N P.

Main Pac Results

The Pac (Probably Approximatively Correct) paradigm has been widely used in machine learning to provide a theoretical setting for convergence issues. The setting was introduced by [START_REF] Valiant | A theory of the learnable[END_REF], and the analysis for the case of learning from strings representations of unbounded size have always been tricky [START_REF] Warmuth | Towards representation independence in pac-learning[END_REF][START_REF] Kearns | Cryptographic limitations on learning boolean formulae and finite automata[END_REF][START_REF] Kearns | An Introduction to Computational Learning Theory[END_REF]. Typical techniques proving non Pac-learnability often depend on complexity hypothesis [START_REF] Pitt | Computational limitations on learning from examples[END_REF].

Balls of Strings are not Pac-Learnable

Definition 1 (ǫ-good hypothesis). Let G be the target grammar and H be a hypothesis grammar. Let D be a distribution over Σ ⋆ . We say, for ǫ > 0, that H is an ǫ-good hypothesis with respect to

G if def P r D (x ∈ L(G) ⊕ L(H)) < ǫ.
In the usual definition of Pac-learning we are going to sample examples to learn from. In the case of strings, there always is the risk (albeit small) to sample a string too long to account for in polynomial time. In order to avoid this problem, we will sample from a distribution restricted to strings shorter than a specific value given by the following lemma: Lemma 1. Let D be a distribution over Σ ⋆ . Then given any ǫ > 0 and any δ > 0, with probability at least 1-δ we have: If we draw a sample X of size at least 1 ǫ ln 1 δ strings following D and write µ X = max{|y| : y ∈ X}, then P r D (|x| > µ X ) < ǫ.

Proof. Denote by µ ǫ the smallest integer n such that P r(Σ >n ) < ǫ. A sufficient condition for P r D (|x| > µ X ) < ǫ is that we take a sample large enough to be nearly sure (i.e. with probability at least 1δ) to have one string longer than µ ǫ . On the contrary, the probability of having all (n) strings in X of length at most µ ǫ is bounded by (1ǫ) n . In order for this quantity to be less than δ, it is sufficient to take n ≥ 1 ǫ ln 1 δ .

⊓ ⊔

A learning algorithm is now asked to learn a grammar given a confidence parameter δ and an error parameter ǫ. The algorithm must also be given an upper bound on the size of the target grammar and on the length of the examples it is going to get (perhaps using an extra sample built thanks to Lemma 1 above). The algorithm can query an Oracle: It may ask for an example randomly drawn according to the distribution D. The query will be denoted Ex(). When the Oracle is only queried for a positive example we will write Pos-Ex(). Finally, if we pass a value m bounding the length of the admissible strings, we will write Ex(m). Combining ideas we can use Pos-Ex(m). The Oracle will return a string drawn from D(L(G)) (for Pos-Ex()), D(Σ ≤m ) (for Ex(m)) or D(L(G) ∩ Σ ≤m ) (for Pos-Ex(m)), where we denote by D(L) the restriction of distribution D to the strings in L: P r D(L) (x) = P rD(x) P rD(L) if x ∈ L, 0 if not. P r D(L) (x) is undefined if L is the empty set.

Definition 2 (Polynomial Pac-learnable). Let G be a class of grammars. G is Pac-learnable if def there exists an algorithm Alg with the following property: For every grammar G in G of size at most n, for every distribution D over Σ ⋆ , for every ǫ > 0 and δ > 0, if Alg is given access to Ex(m), m and n, ǫ and δ then with probability at least 1-δ, Alg outputs an ǫ-good hypothesis with respect to G. If Alg runs in time polynomial in 1 ǫ , 1 δ , m and n, we say that G is polynomiallly Pac-learnable.

Notice that in order to deal with the unbounded length of the examples we can use an ǫ ′ = ǫ 2 and a fraction of δ to compute m and accept to make an error of at most ǫ ′ over all the strings of length more than m, and then use Ex(m) instead of Ex().

We will denote by Poly Informant -Pac the collection of all classes polynomially Pac-learnable.

We prove that provided RP = N P, good balls are not efficiently Paclearnable. The proof follows the classical lines for such results: We first prove that the associated consistency problem is N P-hard, through reductions from a well known N P-complete problem (Longest Common Subsequence). Then it follows that if a polynomial Pac-learning algorithm for balls existed, this algorithm would provide us with a proof that this N P-complete problem would also be in RP. Name: Longest Common Subsequence ( Lcs) Instance: n strings x 1 . . . x n , an integer k Question: Does there exist a string w which is a subsequence of each x i and is of length k? Name: Longest Common Subsequence of Strings of a Given Length( Lcssgl) Instance: n strings x 1 . . . x n all of length 2k Question: Does there exist a string w which is a subsequence of each x i and is of length k? Name: Consistent ball ( Cb) Instance: Two sets X + and X -of strings over some alphabet Σ Question: Does there exist a good ball containing X + and which does not intersect X -? Proof (of lemmata). The first problem is solved in [START_REF] Maier | The complexity of some problems on subsequences and supersequences[END_REF] (see also [START_REF] Garey | Computers and Intractability[END_REF]). The second one can be found in [START_REF] De La Higuera | Topology of strings: Median string is NPcomplete[END_REF] (Problem Lcs0 (page 42)). For the last one, we use a reduction of problem Lcssgl: We take the strings of length 2k, and put these with string λ into set X + . Set X -is constructed by taking each string of length 2k in X + , inserting every possible symbol once only (hence constructing at most n(2k + 1)|Σ| strings of size 2k + 1). It follows that a ball that contains X + but no element of X -has necessarily a centre of length k and a radius of k (since we focus on good balls). The centre is then a subsequence of all the strings of length 2k that were given. Conversely, if a ball is constructed using as centre a subsequence of length k, this ball is of radius k, contains also λ, and because of the radius, contains no element of X -. Finally the problem is in N P, since given a centre u it is easy to check if max x∈X+ d(u, x) < min x∈X-d(u, x).

⊓ ⊔

Proof (of Theo. 1). The proof relies on the widely accepted assumption that N P = RP, and follows the model introduced by Pitt and Valiant [START_REF] Pitt | Computational limitations on learning from examples[END_REF]. Suppose that GB(Σ) is polynomially Pac-learnable with Alg and take an instance X + , X -of Problem Cb. We write run Alg(ǫ,δ,m,n). Let B r (o) be the returned ball and test whether (X + ⊆ B r (o) and X -∩ B r (o) = ∅) or not. If there is no consistent ball, then B r (o) is necessarily inconsistent with the data, so the test above is false. If there is a consistent ball, then B r (o) is ǫ-good, with ǫ < 1 h . So, with probability at least 1-δ > 1 2 , there is no error at all and the test will be true. Finally, this procedure runs in polynomial time in 1 ǫ , 1 δ , m and n. Hence, if good balls were Pac-learnable, then there would be a randomized algorithm for the Cb problem, proved N P-complete by Lemma 2.

h = |X + | + |X -| and define over Σ ⋆ the distribution P r(x) = 1 h if x ∈ X + ∪ X -, 0 if not. Let ǫ = 1 h+1 , δ = 1 2 , m = n = max{|w| : w ∈ X + } and
⊓ ⊔

About Pac-learning Balls from Positive Examples Only

In certain cases it may even be possible to Pac-learn from positive examples only.

In this setting, during the learning phase, the examples are sampled following Pos-Ex() whereas during the testing phase the sampling is done following Ex(), but in both cases the distribution is identical. Again, we can sample using Pos-Ex(m), where m is obtained by using Lemma 1 and little additional cost. Let us denote the collection of such classes polynomially Pac-learnable from Text by Poly Text -Pac. Nevertheless, we get:

Theorem 2. GB(Σ) ∈Poly Text -Pac .
Proof. Consider sample of strings X + = {a, b}. Given any ball B 1 containing X + , there is another ball B 2 also containing a and b such that

B 1 -B 2 = ∅; Let w 1 be a string in B 1 -B 2 .
Then we can construct a distribution D 1 where P r D1 (a) = P r D1 (b) = P r D1 (w 1 ) = 1 3 . But if from X + the Learner constructs B 1 instead of B 2 , the error is of 1 3 and cannot diminish as would be needed. ⊓ ⊔

Queries

Learning from queries involves the Learner (he) being able to interrogate the Oracle (she) using queries from a given set. The goal of the Learner is to identify the representation of an unknown language. The Oracle knows the target language and answers properly to the queries (i.e., she does not lie). We call Quer the class of queries. For example, if the Learner is only allowed to make membership queries, we will have Quer = {Mq}. Definition 3. A class G is polynomially identifiable in the limit with queries from Quer if def there exists an algorithm Alg able to identify every G ∈ G such that, at any call of a query from Quer, the total number of queries and of time used up to that point by Alg is polynomial both in G and in the size of the information presented up to that point by the Oracle.

We will denote by Poly Queries -Quer the collection of all classes polynomially identifiable in the limit with queries from Quer.

For instance, the class of all Dfa is in Poly Queries -{Mq, Eq} [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF]. In the case of good balls, we get the following result:

Theorem 3. GB(Σ) ∈Poly Quer -{Mq, Eq}. Proof. Let n ∈ IN and B ≤n = {B r (o) : o ∈ Σ ⋆ , r ≤ |o| ≤ n}. Following [6],
we describe an Adversary who maintains a set S of all possible balls. At the beginning, S = B ≤n . Her answer to the equivalence query L = B r (o) is a counterexample o. Her answer to the membership query o is No. At each step, the Adversary eliminates many balls of S but only one of centre o and radius 0. As there are Ω(|Σ| n ) such balls in B ≤n , identifying them requires Ω(|Σ| n ) queries.

⊓ ⊔

Notice however that if the Learner is given one string from a good ball, then he can learn using a polynomial number of Mq only. Also, we have shown in [START_REF] Becerra-Bonache | Learning balls of strings with correction queries[END_REF] that special queries, called correction queries (Cq), allowed to identify GB(Σ). Given a language L, a correction of a string w is either Yes if w ∈ L, or a string w ′ ∈ L at minimum edit distance from w, if w / ∈ L.

Theorem ( [START_REF] Becerra-Bonache | Learning balls of strings with correction queries[END_REF]). GB(Σ) ∈Poly Quer -{Cq}.

Polynomial Identification of Balls

In Gold's standard identification in the limit paradigm, a Learner receives an infinite sequence of information (presentation) that should help him to find the representation G ∈ G of an unkown target language L. The set of admissible presentations is denoted by Pres, each presentation being a function N → X where X is any set. Given f ∈ Pres, we will denote by f m the m + 1 first elements of f, and by f(n) its n th element. Below, we will concentrate on two sorts of presentations:

-Pres=Text: All the strings in L are presented: f(N) = L(G) -Pres=Informant: The presentation is of labelled pairs (w, l) where (w ∈ L =⇒ l = +) and (w

∈ L =⇒ l = -): f(N) = L(G) × {+} ∪ L(G) × {-}.
Definition 4. We say that G is identifiable in the limit from Pres if def there exists a learning algorithm Alg such that for all G ∈ G and for any presentation f of L(G) (belonging to Pres), there exists a rank n such that for all m ≥ n,

L(Alg(f m )) = L(G).
This definition yields a lot of learnability results. However, the absence of efficiency constraints may lead to unusable algorithms. Therefore several authors have tried to define polynomial identification in the limit, by introducing different efficiency criteria and combining them.

Polynomial Identification Criteria

Firstly, it is reasonable to think that polynomiality must concern the amount of time an algorithm has to learn: Definition 5 (Polynomial Update Time). An algorithm Alg is said to have polynomial update time if def there is a polynomial p() such that, for every presentation f and every integer n, constructing Alg(f n ) requires O(p( f n )) time.

However, it is known that polynomial update time is not sufficient [START_REF] Pitt | Inductive inference, DFA's, and computational complexity[END_REF]. Indeed, a Learner could receive an exponential number of examples without doing anything but wait, and then use the huge amount of time he saved in order to solve any N P-hard problem. . . Secondly, polynomiality should also concern the minimum amount of data that any algorithm should receive in order to learn: Definition 6 (Polynomial Characteristic Sample). A grammar class G admits polynomial characteristic samples if def there exist an algorithm Alg and a polynomial p() such that ∀G ∈ G ∃Cs ⊆ X ∀f ∈ Pres ∀n ∈ N : Cs ≤ p( G ) ∧ Cs ⊆ f n =⇒ L(Alg(f n )) = L(G). Such a set Cs is called a characteristic sample of G for Alg. If such an algorithm Alg exists, we say that Alg identifies G in the limit in Poly-CS time for Pres.

We will denote by Poly Presentation -Cs the collection of all classes identifiable in the limit in Poly-CS time from Presentation (either Text or Informant).

Notice that if a grammar class only admits characteristic samples whose size are exponential, then no algorithm will be able to converge before receiving an unreasonable amount of data. So the existence of polynomial characteristic sample is necessary but not sufficient again. Notice that several authors (e.g., [START_REF] De La Higuera | Characteristic sets for polynomial grammatical inference[END_REF]) have used stronger notions of polynomial characteristic samples to define polynomial identification in the limit.

Thirdly, polynomiality can concern the behaviour of the algorithm itself through the hypotheses he outputs all along his learning, e.g., the number of implicit prediction errors [START_REF] Pitt | Inductive inference, DFA's, and computational complexity[END_REF]: Definition 7 (Implicit Prediction Errors). Given a learning algorithm Alg and a presentation f, we say that Alg makes an implicit prediction error at time n if def Alg(f n-1 ) ⊢ f(n). We say that Alg is consistent if def it changes its mind each time a prediction error is detected with the new presented element.

Definition 8 (Polynomial Implicit Prediction Errors Criterion

). An algorithm Alg identifies a class G in the limit in Ipe polynomial time if def (1) Alg identifies G in the limit, (2) Alg has polynomial update time and (3) Alg makes a polynomial number of implicit prediction errors: Let #Ipe(f) = |{k ∈ N : Alg(f k ) ⊢ f(k + 1)}|; There exists a polynomial p() such that, for each grammar G and each presentation f of L(G), #Ipe(f) ≤ p( G ).

Note that the first condition is not implied by the two others.

We will denote by Poly Presentation -Ipe the collection of all classes polynomially identifiable in the limit in Ipe polynomial time from Presentation (either Text or Informant).

Fourthly, one can bound the number of mind changes instead of Ipe [START_REF] Angluin | Inductive inference: theory and methods[END_REF].

Definition 9 (Mind Changes). Given a learning algorithm Alg and a presentation f, we say that Alg changes its mind at time n if def Alg(f n ) = Alg(f n-1 ). We say that Alg is conservative if def it never changes its mind when the current hypothesis is consistent with the new presented element.

Theorem 1 .Lemma 2 .

 12 GB(Σ) ∈ Poly Informant -Pac . The following problems are N P-complete:

Definition 10 (

 10 Polynomial Mind Changes Criterion). An algorithm Alg identifies a class G in the limit in Mc polynomial time if def (1) Alg identifies G in the limit, (2) Alg has polynomial update time and (3)Alg makes a polynomial number of mind changes: Let #Mc(f) = |{k ∈ N : Alg(f k ) = Alg(f k+1 )}|; There exists a polynomial p() such that, for each grammar G and each presentation f of L(G), #Mc(f) ≤ p( G ). We will denote by Poly Presentation -Mc the collection of all classes polynomially identifiable in the limit in Mc polynomial time from Presentation (either Text or Informant).

Finally, ifTheorem 4 .

 4 an algorithm Alg is consistent then #Ipe(f) ≤ #Mc(f) for every presentation f. Likewise, if Alg is conservative then #Mc(f) ≤ #Ipe(f). So we deduce the following theorem: If Alg identifies the class G in the limit in Mc polynomial time and is consistent, then Alg identifies G in the limit in Ipe polynomial time. Conversely, if Alg identifies G in the limit in Ipe polynomial time and is conservative, then Alg identifies G in the limit in Mc polynomial time.

⋆ This work was supported in part by the IST Programme of the European Community, under the Pascal Network of Excellence, IST-2002-506778. This publication only reflects the authors' views.

In this section, we show the following results: We say that u is a subsequence of v, denoted u v, if def u = a 1 . . . a n and there exist u 0 , . . . , u n ∈ Σ ⋆ such that v = u 0 a 1 u 1 . . . a n u n . Subsequences and edit distance are strongly related since, d(w, w ′ ) ≥ |w| -|w ′ | . Moreover, d(w, w ′ ) = |w| -|w ′ | iff (w w ′ or w ′ w). We denote by lcs(u, v) the set of longest common subsequences of u and v.

In order to prove Theo. 5, we will need to build the minimum consistent ball containing a set S = {x 1 , . . . x n } of strings (learning sample). This will be efficiently achievable if S admits a so-called certificate. We denote by S max = {w ∈ S : ∀u ∈ S, |w| ≥ |u|} the set of strings in S of maximum length and by S min = {w ∈ S : ∀u ∈ S, |w| ≤ |u|}, the set of strings in S of minimum length.

Definition 11 (Certificate).

A certificate for S is a tuple (u, v, w, o, r) such that [START_REF] Gold | Language identification in the limit[END_REF] 6) S ⊆ B r (o). There may exist 0, 1 or several certificates for S; We will say that S admits a certificate if def there is at least one. As soon as such u, v, w appears in f i , then for all j ≥ i (u, v, w, o, r) will be a certificate for f j . Note that other certificates may exist, but due to Lemma 3, Algo. 1 will return the same representation (o, r) forever.

⊓ ⊔ Lemma 6. Algo. 1 makes a polynomial number of Mc.

Proof. Assume that B r (o) is the target ball and f is a presentation. Let us run Algo. 1 on f and observe the output trace T = (x 1 , s 1 )(x 2 , s 2 )(x 3 , s 3 ) . . . Each (x i , s i ) is either the representation of a valid ball (o, r) coming from a certificate, or else, of a junk ball (c, |c|). Let (o i , r i ) be an output generated by a certificate and j the smallest rank such that j > i and (o j , r j ) is also valid.

Then, as f i ⊆ B rj (o j ), by Lemma 3, either r i < r j or (o j = o i and r j = r i ). The latter is impossible, so r i < r j . Therefore, each time Alg changes its mind in favor of a new valid ball, its radius is increased by at least 1 w.r.t. the previous valid balls. So the number of different valid balls it will output will be at most r (it is bounded by the radius of the target ball). Moreover, the number of Mc of Alg in favor of a valid ball is ≤ r.

On the other hand, let (c i , |c i |) and (c j , |c j |) be 2 junk balls. We have: (1) if i < j then |c i | ≤ |c j | (since c i (resp. c j ) is a string of maximum length in f i (resp. f j )), and ( 2 Proof. We give the proof here for the case where the learning algorithm is deterministic. If the algorithm is allowed to be randomized, a slightly more tedious proof can be derived from this one. Suppose we have a Learner Alg and a polynomial p()

Let n be a sufficiently large integer, and consider the subclass of targets B k (λ) with k ≤ n. For each target, we construct a presentation f k by running Alg in an interactive learning session. At each step i, Alg produces hypothesis H i , and we have to compute a new string f k (i + 1). For this purpose, we use Algo. 2.

Algorithm 2: Compute f k (i)

) else return λ else if Hi-1 = Bj(λ) where j = max{|u| : u ∈ f k i-1 } then return a j+1 else return λ end end Each presentation f k is a correct text presentation of its target B k (λ), i.e., f k (N) = B k (λ). Let us denote by m(k) = min{i ∈ N : f k (i) = a k }. For each k, f k and f k+1 coincide on the same m(k) initial values. Then f n can be rewritten as: λ, . . . , λ, a, . . . , a, . . . , a n ,. . . with: ∀j : 0 < j ≤ n, ∀i ∈ {m(j -1), .., m(j) -1}, f n (i) = f j (m(j-1)) = f j (i) = a j-1 , and Alg makes a mind change just before receiving new example a i . This proves that #Mc(f n ) > p(log n). Therefore, given any learning algorithm Alg and any polynomial p(), there is a n

Proof. We prove that there is a Learner that just checks the data until it is sure that there is only one possible consistent ball and therefore makes just one mind change. Let B r (o) be the target ball, and X + , X -be a sample such that there is a string u for which (1)a k u, b k u ∈ X + , (2) all supersequences of a k u or of b k u of length |u|+1+k are in X -and (3) if u = λ, for each subsequence v of u of length |u|-1, there is a supersequence of v of length |u|+k in X -. Note that (1) given a ball B r (o), this sample always exists; (2) Checking if there is such a string u for a sample X is in O( X ); (3) All edit operations in a minimal path transforming o into a k u and b k u are insertions: If not, by changing any non-insertion operation by an insertion, we can build a string w such that d(o, w) = d(o, a k u) ∧ w ∈ X -; Therefore o u; (4) Since for each subsequence w of u there is a supersequence of length |u| + k in X -, no proper subsequence of u is the centre. We conclude that u = o and k = r. And of course the required conditions will be true at some point of the presentation. ⊓ ⊔ An alternative to making a difference between BALL(Σ) and GB(Σ) is to consider an intermediary collection of classes: For any polynomial p(), p()-good balls are those balls B r (o) for which r ≤ p(|o|), and we denote by p() -GB(Σ) the corresponding class. It seems that if most results for good balls transfer to p()-good balls in a natural way, this is not systematically the case.


Hazem Awni

Al Rekhawi

Samy S Abu Naser
email: abunaser@alazhar.edu.ps

An Intelligent Tutoring System for Learning Android Applications UI Development

Keywords: Intelligent Tutoring System, Android, Java, Problem Generation, Droid-Tutor

The paper describes the design of a web based intelligent tutoring system for teaching Android Applications Development to students to overcome the difficulties they face. The basic idea of this system is a systematic introduction into the concept of Android Application Development. The system presents the topic of Android Application Development and administers automatically generated problems for the students to solve. The system is automatically adapted at run time to the student's individual growth. The system provides obvious support for adaptive demonstration constructs. An initial assessment study was done to examine the effect of using the intelligent tutoring system on the performance of students enrolled in Smartphone Applications Development in the University College of Applied Sciences, Gaza. The results showed a positive impact on the evaluators.

INTRODUCTION

Intelligent Tutoring Systems (ITSs) can be traced back to the early 1970s, when Carbonell tried to combine methods of Artificial Intelligence (AI) with Computer Aided Instruction (CAI) [START_REF] Carbonell | AI in CAI: An artificial-intelligence approach to computerassisted instruction[END_REF]. Therefore, the first generation of ITSs is more or less a sort of "intelligent" CAI. Their focal task is specified by Lelouche: "The basic principle of "intelligent" CAI is that it should identify the taught material" [START_REF] Lelouche | Intelligent tutoring systems from birth to now[END_REF]. Knowledge about the trained material is implanted in the ITS in form of expert systems, that is, the expert module [START_REF] Amalathas | Developing an intelligent tutoring system for palm oil in ASPIRE[END_REF][START_REF] Fournier-Viger | Building Intelligent Tutoring Systems for Ill-Defined Domains[END_REF]. The integration of insights of cognitive science in ITSs, has led to what nowadays is termed an Intelligent Tutoring System [START_REF] Abu Naser | ITSB: An Intelligent Tutoring System Authoring Tool[END_REF]. In addition to the knowledge about the trained material, these systems have understanding about pedagogical approaches and understanding about the student, realized as pedagogical module and student module, respectively.

The traditional ITS architecture was designated by Clancey, comprises of the components: student module, expert module, pedagogical module, and user interface [START_REF] Clancey | Methodology for Building an Intelligent Tutoring System[END_REF]. The identification of the components varies. Occasionally, depending on the teaching domain, a module for automatic generation of exercises is likewise part of the ITS. While the ITS"s ingredients appear to be part of common agreement in the ITS community, the role and the functionality of each of the components varies a lot [START_REF] Al Rekhawi | Rickets Expert System Diagnoses and Treatment[END_REF][START_REF] Amalathas | Developing an intelligent tutoring system for palm oil in ASPIRE[END_REF]. The reason for this can partly be seen in the different application domains. One can easily imagine that training in mathematics places different demands on ITSs than clinical medicine training. Another reason might be the realization of different learning theories in ITS. Case-based learning, described in the former section, places special demands on an ITS that are rather different in problemoriented education. These sensible features often unavoidably lead to mixed and unrivaled systems. But even in the same application domain and established on the same education style, ITSs are often not analogous and based on a whole different clarification of the same architecture. Furthermore, regarding only the ITS architecture on a more nonconcrete level, it turn out to be tough to find motives for heterogeneous understandings at all. A mixture of content and delivery functions, which is seemingly not based on visions of research but on traditions of ITS development, can be found in ITS understandings.

In other ITSs, the expert knowledge base is a modest database deprived of own functionality [START_REF] Tang | Qualitative reasoning and articulate software[END_REF]. The same condition can be found in the dissimilar ways the pedagogical knowledge module is realized and embedded in the ITS. Thus, there are ITSs that involve a set of interacting and more or less distinct subsystems, and there are ITSs containing of passive components plus a component that encapsulates the execution. Execution in this context contains the interaction with the student, the evaluation of the student"s behavior and success, and the provision of contents and navigation. Thus, two standpoints on the same architecture can be established, replicating different clarification of the same modules: ITS architecture contains either distinct independent subsystems or reflexive components with unified implementation system. Both viewpoints have their benefits and drawbacks. However, the main system"s thinking concerning the understanding of the components should be made clear to offer comparability of ITSs and reusability of ITS components. The benefit of this approach is that the central navigating component might be reused in different ITSs, as it is clearly detached from the databases and the user interface. Figure 1 illustrate the recommended ITS architecture with the tutoring process module is outlined.  Building an intelligent tutoring system for problems for which the responses might not be usually quantitative.  Creating limitless number of problems automatically, thereby providing as much practice with problemsolving as the student wants.  Having a system that adapt at run time to the student"s individual growth.  Using students' previous knowledge of Java in the development of android applications.  Teaching students how to deal with problems and solve them.  Evaluating student level through MCQ, correct and error on several levels of difficulty.  Providing a complete teaching material for the student in android applications development containing a lot of exercises and practical examples.  Providing videos that explain some lessons in Android applications development, making learning easier for students.  Designing of Android applications according to the standards of mobile applications design.  Building interactive android applications and publishing it on Google Play Store.

DROID-TUTOR DESIGN

There are many Intelligent Tutoring Systems (ITS) that were designed and developed for many fields such as: a comparative study between Animated Intelligent Tutoring Systems (AITS) and Video-based Intelligent Tutoring Systems (VITS) [START_REF] Abu Naser | A comparative study between animated intelligent tutoring systems AITS and videobased intelligent tutoring systems VITS[END_REF], cloud computing [START_REF] Abu Hasanein | An intelligent tutoring system for cloud computing[END_REF], Computer Networks [START_REF] Almurshidi | Stomach disease intelligent tutoring system[END_REF], ADO-Tutor: Intelligent Tutoring System for leaning ADO. NET [START_REF] El Haddad | ADO-Tutor: Intelligent Tutoring System for leaning ADO[END_REF],CPP-Tutor for C++ Programming Language [START_REF] Khella | Expert System for Chest Pain in Infants and Children[END_REF], effectiveness of E-learning [START_REF] Khella | Expert System for Chest Pain in Infants and Children[END_REF][START_REF] Abu Naser | JEE-Tutor: An Intelligent Tutoring System for Java Expression Evaluation[END_REF], effectiveness of the CPP-Tutor [START_REF] Naser | Evaluating the effectiveness of the CPP-Tutor an intelligent tutoring system for students learning to program in C++[END_REF], E-learning system [START_REF]Android Development by Vogella Website[END_REF], Health problems related to addiction of video game playing [START_REF] Al-Bayed | An intelligent tutoring system for health problems related to addiction of video game playing[END_REF], Java Expression Evaluation [START_REF] Abu Naser | JEE-Tutor: An Intelligent Tutoring System for Java Expression Evaluation[END_REF] , Linear Programming [START_REF] Abu Naser | A Qualitative Study of LP-ITS: Linear Programming Intelligent Tutoring System[END_REF], learning Computer Theory [START_REF] Al-Nakhal | Adaptive Intelligent Tutoring System for learning Computer Theory[END_REF], Learning Java Objects [START_REF] Amalathas | Developing an intelligent tutoring system for palm oil in ASPIRE[END_REF], Mathematics Intelligent Tutoring System [START_REF] Abueloun | Mathematics intelligent tutoring system[END_REF], Oracle Intelligent Tutoring System (OITS) [START_REF] Aldahdooh | Development and Evaluation of the Oracle Intelligent Tutoring System (OITS)[END_REF], parameter passing in Java programming [START_REF] Abu Naser | An Agent Based Intelligent Tutoring System For Parameter Passing In Java Programming[END_REF], Photoshop (CS6) Intelligent Tutoring System [START_REF] Hamed | An intelligent tutoring system for teaching the 7 characteristics for living things[END_REF], predicting learners performance using NT and ITS [START_REF] Abu Naser | Predicting learners performance using artificial neural networks in linear programming intelligent tutoring system[END_REF], stomach disease Intelligent Tutoring System [START_REF] Almurshidi | Stomach disease intelligent tutoring system[END_REF], teaching advanced topics in information security [START_REF] Naser | Evaluating the effectiveness of the CPP-Tutor an intelligent tutoring system for students learning to program in C++[END_REF], teaching AI searching algorithms [START_REF] Abu Naser | Developing visualization tool for teaching AI searching algorithms[END_REF], teaching database [START_REF] Abu Naser | Intelligent tutoring system for teaching database to sophomore students in Gaza and its effect on their performance[END_REF], teaching DES information security algorithm [START_REF] Hilles | Knowledge-based Intelligent Tutoring System for Teaching Mongo Database[END_REF], teaching grammar English tenses [START_REF] Alhabbash | An Intelligent Tutoring System for Teaching Grammar English Tenses[END_REF], teaching Mongo Database [START_REF] Mahdi | An intelligent tutoring system for teaching advanced topics in information security[END_REF], teaching the 7 Characteristics for Living Things [START_REF] Hamed | An intelligent tutoring system for teaching the 7 characteristics for living things[END_REF], right letter pronunciation in reciting the Holy Quran [START_REF] Akkila | Teaching the right letter pronunciation in reciting the holy Quran using intelligent tutoring system[END_REF] , and Diabetes Intelligent Tutoring System [START_REF] Almurshidi | Design and Development of Diabetes Intelligent Tutoring System[END_REF], CSS-Tutor: An intelligent tutoring system for CSS and HTML [START_REF] Alawar | CSS-Tutor: An intelligent tutoring system for CSS and HTML[END_REF], Design and Development of an Intelligent Tutoring System for C# [START_REF] Al-Bastami | Design and Development of an Intelligent Tutoring System for C# Language[END_REF].

DROID-TUTOR IS UNIQUE WITH RESPECT TO THE PREVIOUS WORK IN THE FOLLOWING MANNER:

 The system was built to look like the most familiar interactive interfaces like OS desktops, including (icons, drag and drop features, tabs menus, and pop-up windows) which are all integrated in one single window.  The intelligent tutoring system was built for problems for which the answers might not be always quantitative [START_REF] Al Rekhawi | Rickets Expert System Diagnoses and Treatment[END_REF][START_REF] Abu Naser | ITSB: An Intelligent Tutoring System Authoring Tool[END_REF].  WebToTeach is related to Droid-Tutor [START_REF] Arnow | WebToTeach: An interactive focused programming exercise system[END_REF], but it administers instructor pre-prepared problems, and does not generate the problems automatically. Droid-Tutor can generate unlimited number of problems automatically, thereby providing as much practice with problem-solving as the student needs.

Kashy have shown that the use of problem generation systems has increased student performance by 10% in Physics, largely due to limitless time spent on the task [START_REF] Kashy | Using networked tools to enhance student success rates in large classes[END_REF].

DROID-TUTOR IS DESIGNED TO HELP STUDENTS LEARN ANDROID APPLICATIONS DEVELOPMENT BY:

1. Gradually teaching the Android Applications Development material to the students. The system is supported with a student controlled voice narrator, which acts as a facility during learning. 2. Repeatedly solving automatically generated problems and obtaining the proper feedback. 3. Droid Tutor is designed with amazing android text lessons and video training materials. 4. The possibility of measuring the level of the student through exercises and questions. 5. The possibility of advising the student how to handle errors and solve them quickly.

The Droid-Tutor is designed to be used as a supplement to the traditional method of teaching (Android Development textbook and Instructor), either during a laboratory session, after class training, or for homework assignments. Droid-Tutor has the following modules: Pedagogical Module, Problems Generation Module, and Expert Module, Student Module, and Tutoring process module.

Droid-Tutor Pedagogical Module Design

It has been noticed that students are having difficulties in understanding the concepts of Android Applications Development. To overcome these difficulties, an Intelligent Tutoring System for teaching Android Applications Development called Droid-Tutor have been developed to students enrolled in Android Applications Development Course in the Mobile Applications Development Department at University College of Applied Sciences in Gaza. Droid-Tutor gradually introduces students to the concept of Android Applications Development and automatically generates problems for the students to solve. The key sections that draws the main structure of the tutoring material [18,[START_REF]Android Applications Development Training Material[END_REF][START_REF]Android Hive website that is contains a lot of android examples[END_REF]

Problems Generation Module of Droid-Tutor

A number of problems have been lately recognized as a potential shortcoming of encoding a limited set of problems into a tutor [START_REF] Martin | Tailoring feedback by correcting student answers[END_REF]. A technique used in literature to dynamically generate problems is by BNF-like grammar [START_REF] Koffman | A module for generative CAI and concept selection[END_REF]. In this technique, problems are generated by arbitrarily instantiating templates written in the grammar. Each template can be prudently planned with specific pedagogical aims in mind.

Problem Generation Module is accountable for generating the template of code, theses templates cover the core topics of Android Applications Development which are (android user interface, applications components, Activity Lifecycle, Layout Manager, Android views, Android Dialogs, Fragments and Advanced Android Material Design). The module depends on randomly structuring of the pieces of codes which forms the templates that consist of (layout manager, values resource, themes and styles, Custom Data Adapter, return types, arguments data types, classes, methods, and arguments names). These structures are imported from pre-defined lists of keywords. The template is generated with a previously intended problem each time it is requested, followed by a related question and possible solutions. The questions have different styles including either asking the student to correct an Android code, write an Android code, multiple choice, or true/false.

Expert Module of Droid-Tutor

Expert Module was implemented to gather the necessary information for generating the feedback [START_REF] Anderson | Cognitive tutors: Lessons learned[END_REF]. The expert module is capable of solving the generated problems by parsing the template. Since the expert module can execute any code, it can generate the correct answer for a problem on its own, and determine whether the user"s answer is correct/incorrect. In addition to whether the user"s answer is correct/incorrect, the module can provide the student with the correct answer when it is requested. Furthermore, the module provides the student the proper feedback in response to the student's answer.

Student Module of Droid-Tutor

A new student must create his own account to have a profile. The profile has information about the student such as his name, dates of login, score of each session, and learning progress during each session. The student's score can be viewed at any time during the session that describes the student performance in solving problems in the following subjects: casting, classes and inheritance.

Tutoring process Module of Droid-Tutor

Tutoring process module works as a coordinator that controls the functionality of the whole system.

Droid-Tutor User Interface Design

The Droid Tutor is uniquely designed and easy for the student and here is a screenshot and explanation for each interface, you can see figures from Figure 2 to Figure 14.

EVALUATION OF THE DROID-TUTOR

An initial evaluation of the Droid-tutor was carried out by the lecturers and their students who enrolled in android applications development course during the first semester of 2017/2018 in Mobile Applications Development Department at University College of Applied Sciences in Gaza. A questioner consisting of the items in table 1 was filled out by each evaluator (Lecturers and Students). A group of 4 lecturers and 25 students participated in the evaluation of the system. Table 1 shows the overall rating of the lecturers and students who evaluated the system. Form the summary of Table 1, the evaluation of the Droid-Tutor showed a positive impact on the evaluators (Lecturers and students). Furthermore, they recommend that similar systems for other courses to be implemented.

CONCLUSIONS AND FUTURE WORKS

The design of an Intelligent Tutoring System called Droid-Tutor was described in this paper. Droid-Tutor was designed for teaching Android Applications Development to students to overcome their difficulties. Droid Tutor

Figure 1 .

 1 Figure 1. ITS architecture with tutoring process module. The design of the Intelligent Tutoring System for Learning Android Applications Development (Droid-Tutor) adopted the ITS architecture with automatically generated problems module. The benefits of the Droid-Tutor are: Building an intelligent tutoring system for problems for which the responses might not be usually quantitative.  Creating limitless number of problems automatically, thereby providing as much practice with problemsolving as the student wants.  Having a system that adapt at run time to the student"s individual growth.  Using students' previous knowledge of Java in the development of android applications.  Teaching students how to deal with problems and solve them.  Evaluating student level through MCQ, correct and error on several levels of difficulty.  Providing a complete teaching material for the student in android applications development containing a lot of exercises and practical examples.  Providing videos that explain some lessons in Android applications development, making learning easier for students.  Designing of Android applications according to the standards of mobile applications design.  Building interactive android applications and publishing it on Google Play Store.

Figure 2 .

 2 Figure 2. The Login User Interface.

Figure 3 .

 3 Figure 3. The Main User Interface.

Figure 4 .

 4 Figure 4. Student Data Interface.

Figure 5 .

 5 Figure 5. Controls Fonts and Colors User Interface.

Figure 6 .

 6 Figure 6. Learning Material Android Applications Development Screenshot 1.

Figure 7 .

 7 Figure 7. Learning Material Android Applications Development Screenshot 2.

Figure 8 .

 8 Figure 8. Learning Material Android Applications Development Screenshot 3.

Figure 9 .

 9 Figure 9. Learning Material Android Applications Development Screenshot 4.

Figure 10 .

 10 Figure 10. Examples of Lessons User Interface.

Figure 11 .

 11 Figure 11. Exercises and Questions User Interface.

Figure 12 .

 12 Figure 12. Different Types of Questions -Multiple Choice.

Figure 13 .

 13 Figure 13. Different Types of Questions -True or False.

Figure 14 .

 14 Figure 14. Result of Final Evaluation.

Table 1 :

 1 Shows the rating of the of the Droid-Tutor by lecturers and students

	Item #	Item	Rating % Lecturers Students
	1	The Quality of the Droid-Tour Design	94%	96%
	2	The importance of the topic covered (Android Applications Development)	96%	98%
	3	Would you benefit from using the Droid-Tutor?	92%	98%
	4	Do you recommend using Droid-Tutor for android applications development course as a supportive tool?	100%	100%
	5	Would you like to see similar tutoring system in other courses?	100%	100%

www.ijeais.org

 [START_REF] Kashy | CAPA-An integrated computer-assisted personalized assignment system[END_REF]presents the topic of Android Applications Development to the student and administers automatically generated problems for him to solve. Droid-Tutor is dynamically adapted at run time to the student"s individual progress. An initial evaluation of Droid-Tutor was carried out by the lecturers and students taken the Android Applications Development course in the University College of Applied Sciences in Gaza. The outcome of the evaluation was positive and suggested that other intelligent tutoring systems be designed for other courses. We recommend a comprehensive evaluation of the system to be carried out next time the course is offered.