dataesr/scientific-paragraphs-categorization huggingface dataset:
For a given number of clusters, k = 2, 3, 4,. , 20, we run the algorithm 200 times on our data (with different seeds for the algorithm in every run), and obtain the average value of the BD-index (see subsection below for formal definition), which is a measure of how optimal is that K-scheme. This way we can pick which one is the best cluster scheme. In Fig. 19  we show the average value and the Standard Deviation (SD) of the DB-index, as a function of the number of clusters in the partition. This representation will have a minimum around the optimum number of clusters for a given dataset. Conversely, it would be monotonically decreasing if the data set lacks any significant cluster structure. We found that there is an optimum around a scheme with 5 or 6 clusters (black line in Fig. 19 ). However, due to the fact that the SD is considerably smaller for 5 than for 6 (which indicates that the partition schemes found in different realizations of the algorithm for k = 5 are much more similar to each other in terms of their corresponding DB-index, than in the case of k = 6), we pick k = 5 as our optimum clustering partition.
The dispersion S i within cluster C i is calculated as: S i = 1 T i T i =1 X -A i , (2) where A i is the centroid of cluster C i , X -A i denotes the Euclidean distance between the vector X and the centroid A i , and T i is the size of cluster C i (that is, the number of subjects assigned to that cluster). Then for each pair of clusters i and j, we define the matrix R ij = S i + S j M ij , (3) where M ij = A i -A j is the separation between clusters i and j (that is, the distance between their corresponding centroids). Thus, we can define the DB index as DB = 1 N N i=1 D i , (4) where D i = max i =j R ij. S. 4. 9. Normalized Mutual Information Score In order to compare the consistency between two independent runs of the K-means algorithm in terms of the individuals' composition of the clusters obtained, we use the Normalized Mutual Information Score  (37) , as implemented in the Python package SciKit Learn).
The thus derived core functional language intml is formulated by means of a type system inspired by Baillot & Terui's Dual Light Affine Logic. It can be understood as a programming language simplification of Stratified Bounded Affine Logic. We show that it captures the classes flogspace and nflogspace of the functions computable in deterministic logarithmic space and in non-deterministic logarithmic space, respectively. We illustrate the expressiveness of intml by showing how typical graph algorithms, such a test for acyclicity in undirected graphs, can be represented in it.
It is then not visible that strings may be too large to fit into memory. In this paper we show that this higher-order functional programming approach can be used for implementing algorithms with logarithmic space usage. We argue that the higher-order approach captures typical algorithms with logarithmic space in a natural way. Suppose we have a program p of type String → String; a simple example would be λx. cons c (cons d x). Suppose we have a large externally stored string that we want to use as an input for this program. We can construct a value n, w of type String, where n is the length of the string and w is a function that when invoked with argument i has the effect of looking up the i-th character of the externally stored string (perhaps by sending a network request to a database or similar).
We show how to combine computation with a fixed number of pointers with higher-order functions in a functional programming language. We explain how one can extend a simple first-order language for programming with a fixed number of pointers with higher-order functions in such a way that programs are still guaranteed to use no more than a fixed number of pointers. The higher-order extensions will in fact be fully definitional in the sense that any higher-order program will be translated to a first-order program. Since our first-order programs cannot use more than a finite number of pointers, this property will then be true for higher-order programs as well. In this paper we work this out in the form of a minimal functional programming language, intml, for programming with logarithmic space.
Organising Interactive Computation The heart of the definition of intml is the construction of higher-order functions in a first-order language that computes with a fixed number of pointers only. This construction is an instance of the Int-construction  [28] , see Section 5. 7. We begin with a simple first-order language that captures computation with a fixed number of pointers. We then study how this language can implement interactive processes, such as the logarithmic space algorithms that access their input by requesting it piece by piece. This model of interactive computation can interpret higher-order functions, which is what intml makes available directly to the programmer. The point is that the whole construction is such that in the end all computation will happen in the first-order language.
Overview In this paper we develop the functional programming language intml. It is constructed from a simple first-order programming language as a base language. Intml is obtained by adding to this base language a new class of types and terms that allows us to construct message passing circuits whose nodes are implemented in the base language. We call this the interactive language. The new types represent interfaces of wires in message-passing circuits, as outlined above. In intml we use types of the form [A], X ⊗ Y and A • X Y. The terms of the interactive language, which are much like in a standard functional programming language, represent the circuits themselves. By constructing intml in this way we obtain a language that allows the programmer to work both in the base and in the interactive language.
This reflects our experience with writing programs with logarithmic space usage. The interactive language allows the programmer to work with large data. The base language can be used work with small data and to manipulate pointers directly. It seems to be useful to keep such a distinction, as restrictions that need to be imposed on the manipulation of large data in order to remain in logarithmic space are not necessary for small values. We introduce intml in Section 2. The following Sections 3 and 4 contain programming examples and explain how logarithmic space graph algorithms can be represented in intml. In Section 5 we show in detail how higher-order functions in intml are translated to message-passing circuits and thus reduced to first-order programs. In Section 6 we use this reduction to prove soundness and completeness of intml for the functions computable in logarithmic space.
The main issue is the control of exponentials, which are responsible for size increases in message passing. In order to obtain space bounds, the exponentials must therefore be restricted. The difficulty is to do so without the programming language becoming too weak. In this paper we argue that intml with its subexponentials represents a good solution to this problem. Subexponentials make intml an expressive higher-order language. For example, we show that it can type the Kierstead terms, which cannot be typed in similar linear type systems, such as  [14]. Moreover, the proof of flogspacecompleteness in this paper is completely straightforward. In earlier work, such as  [36, 42] , the completeness proofs were more involved. The expressiveness of intml is further illustrated by the programming examples, such as in Section 4.
Subexponentials not only give us control over space usage, they also afford an efficient treatment of controlled duplication. For example, Ghica and Smith  [15]  treat copying in the language by actual duplication of terms. Here we show how to allow copying by sharing without the need to duplicate parts of the program. Finally, the language intml presented in this paper is the first higher-order language with logarithmic space bounds that allows one to use (and define!) higher-order combinators such as for tail recursion and call with current continuation. Compared to  [10] , this paper includes full proofs of all main results presented there. Moreover, the characterisation of logarithmic space from  [10]  has been generalised to nondeterminism. The presence not only of higher-order functions but also the ability to define combinators, such as for call/cc or for block-scoped mutable variables like in Idealised Algol, is the main novelty of the language we present here.
Base Language We begin by fixing the details of the base language. We emphasise that this language was chosen mainly for simplicity and that richer languages can be chosen without affecting the construction of intml. The types of the base language are generated by the grammar A ::= α int 0 1 A + A A × A. They are built from type variables, a type of integers and product and coproduct types. We use lowercase Greek letters α, β, γ to range over type variables. The type int contains the unsigned integers of some fixed bit-width k. We define the interactive language without any assumptions on the choice of k. It shall be possible to evaluate any single program with respect to different choices of k. Indeed, we shall use int as a type of pointers to access large data, which means that we must choose k depending on the size of the data.
Interactive Language The base language is the basis of the definition of intml. To complete the definition, we now introduce the interactive part of the language. This part adds higher-order functions to the base language. The interactive language can be understood as a way of constructing message-passing circuits, as outlined in the Introduction, in which each message-passing node is implemented by a base language term. Nevertheless, the interactive language takes the form of a typed λ-calculus that can be described without reference to circuits and that allows one to write programs following a handier functional paradigm. Interactive types are defined by the grammar X, Y ::= [A] X ⊗ Y A • X Y , in which A ranges over base language types. The type [A] represents computations that return a value of base type A if they terminate.
With the exception of Section 6. 2, all results in this paper remain true verbatim also if one allows arbitrary base terms for v in rule +E c. The intml type system is completed by rule Hack in Fig. 8. Rule Hack is the only rule that requires a detailed understanding of the translation of interactive terms to message passing circuits. This rule allows one to define an interactive term of type X by giving explicitly a base language term f that implements a message passing node with a single outgoing wire of type X and no other wires. Therefore, rule Hack can only be explained properly once the compilation to circuits that are implemented in the base language has been explained in detail. For now, the reader should consider rule Hack like a method for inlining C code in an ML program, whose understanding requires a detailed knowledge of the runtime system.
e. terms not containing any free occurrence of any variable. Note that the case-terms is restricted to case distinction on values by the type system. A term t reduces to s, written t → k s, if there are u, q such that u → k q, t = E[u] and s = E[q]. As in the base language, the parameter k represents the bit-width of integers. In Section 5. 6, we show that the translation of interactive terms to message passing circuits is sound with respect to reduction: t → k s implies that the circuits for t and s have the same message passing behaviour (even if they are not the same). This completes the definition of the interactive language of intml. The reader may wonder if in addition to the various ways of embedding base language terms into interactive terms, it is also possible to embed interactive terms into base terms.
On Large Data and Space Usage Base language programs can be understood as programs that store a constant number of pointers. If the bit-width of integers is k, then any base language program evaluates in space O(k). The same is true for the interactive language. We will show that the interactive part of the language can be compiled to the base language. Even though the interactive language allows higher-order functions, it can nevertheless be evaluated in space O(k). Thus, intml can be seen as a higher-order language for the computation with a finite number of pointers. Let us outline with a simple concrete example how we use higher-order functions in intml to implement sublinear space algorithms. We consider programs that work on long bit vectors, i. e. long sequences of 0s and 1s. The base language type 2 = 1 + 1 can be seen as a type of bits, where inl( * ) stands for 0 and inr( * ) stands for 1.
Bit vectors of length n can be represented as a base type value of type 2 × • • • × 2 (n factors), but this representation would not be space efficient. A value of this type has size O(n), i. e. it will need linear space. A higher-order representation of bit vectors is more space-efficient. If we choose the bit-width of the base language to be log n, then the positions in the bit vector can be represented by values of type int. Bit vectors of length n can then be represented by functions of type A • [int] [2]. (There may be more than n bits, but we can just ignore superfluous elements. ) First, we explain how large bit vectors can be given as input to intml programs. Suppose we have a program of type A • (1 • [int] [2] )  [2]  that represents a predicate on bit vectors. We make no restriction on the subexponential and allow any type A (we cannot use a type variable as the program may require a type of a particular form, such as 1 + B).
Suppose that we have a concrete large vector (e. g. stored in some database) of length n that we would like to pass to the program. The program will translate to a circuit with one outgoing wire with interface (X -, X + ). X = A • ( 1 • [int] [2] ) [2] X -= A × ( 1 × 1 + 2 ) + 1 X + = A × ( 1 × int + 1 ) + 2 To evaluate the program with the bit vector as input, we fix the bit-length of integers to be log n and then use the circuit to evaluate the result of the program. The values of type X -are the messages that we can send to the circuit, the values of type X + are the possible responses. A typical dialogue with this circuit will be as follows: we send inr( * ) : X -('What is the value of the predicate?') to the circuit. A typical answer will be inl( a, inr( * ) ) : X + ('I would like to know a bit of the input vector.
'). The whole bit vector represented by the term of type A • [int]  [2]  can now be reconstructed by repeatedly querying the circuit. Notice that the messages that we send to and receive from the circuits are all base language values of size O(k), where k is the bit-width of integers. The intml type system guarantees that the same is true for the messages exchanged internally in the circuit. The space needed for messages is thus logarithmic in the length of the bit vectors that are represented, which is 2 k. It is this basic observation that leads to logarithmic space bounds. Direct interaction with circuits is needed only to supply the input value and to read off the output value. Intermediate values can be defined using the terms of the interactive language. For example the exclusive or of two bit vectors can be implemented as an interactive program λx.
The term l implements the following strategy: (2) says that a request for the value of loop s t results in the value of t being requested. When an answer from t arrives, we put it in a memory cell (corresponding to α • -in the type) and ask s for its return value (3). Whenever s asks for its argument, we supply the value from the memory cell  (6). If s returns value inr(b), then we are done and give b as output (4). If s returns value inl(a ), then we overwrite the memory cell content with a and restart the step function s by asking for its result  (5). In Section 5 we will make precise the circuit implementation of intml and in Section 5. 6 we show that is correctly implements the operational semantics. With the techniques of Section 5. 6, one can show: Proposition 2. The following reduction is sound (in the sense of Theorem 13) in the interactive language.
Encoding Algol-like Languages The definition of intml was guided by the question of how programming with sublinear space can be supported in functional programming languages. However, the direct definition mechanism in intml is expressive enough to express imperative programming constructs as in Idealised Algol as well. Reynolds has introduced Idealised Algol as a synthesis of functional and imperative programming  [41]. Its core is the simply-typed λ-calculus for functional programming, which is extended with constants for impertative programming constructs. Assume the simply-typed λ-calculus with the following types U, V ::= com exp τ cell τ U × V U → V , where τ ∈ {bool, int}. The idea is that terms of type com are imperative commands that can be exectued and that may have side effects, terms of type exp τ are expressions that when executed return a value of type τ, and that cell τ repesents memory cells with content of type τ that may be updated destructively.
seq asg int y, 1 , seq while lt 1, der int x , seq asg int y, mul der int y, der int x , asg int x, sub der int x, 1 asg x, sub der int y ) : com In this section we outline how constants as in Idealised Algol can be defined in intml. The aim is to implement the constants of Idealised Algol so that the abstract syntax representation of imperative programs has the intended behaviour. Since intml does not allow unrestricted copying of variables in the interactive language, we will not be able to embed all of Idealised Algol, of course. However, there are interesting applications of Idealised Algol even without full copying. Ghica  [14]  uses a restricted variant of Idealised Algol, Basic Syntactic Control of Interference (bSCI), as a language for hardware synthesis. Ghica translates bSCI-programs to hardware circuits in a way that is very similar to our translation of interactive terms to base language terms.
Indeed, if one removes type variables from the base language, base language programs become finite functions, which can be encoded directly in hardware. Thus, intml can also be used as a language for hardware synthesis. In this section we show that its expressiveness is comparable to bSCI. We note that the fine-grained control of copying in intml allows one to go beyond bSCI. For example, the Kierstead terms cannot be typed in bSCI  [14] , but we will show in Section 4. 3 how to express them in intml. We now discuss how one may define an Algol-like language if in Reynolds' definition  [41]  one replaces the simply-typed λ-calculus with the interactive language of intml. We define Algol-like program constants, the choice of which is guided by those in bSCI  [14]. First, we define types for commands, expressions and memory cells by com := [1] , exp α := [α] , cell α := ([α] com) ⊗ [α].
f 2 (λy. y)) : X Struct | f : (1 + α)•T copy f as f 1 , f 2 in f 1 (λx. f 2 (λy. y)) : X I • | • t 1 : (1 + α) • T X In the right-hand branch, Π stands for the following derivation. Ax | f 1 : 1•T f 1 : T Ax | f 2 : 1•T f 2 : T Ax | y : 1•X y : X I • | • λy. y : X X E | f 2 : 1•T f 2 (λy. y) : X Weak | f 2 : 1•T, x : 1•X f 2 (λy. y) : X I | f 2 : 1•T λx. f 2 (λy. y) : X X E | f 1 : 1•T, f 2 : (α × 1)•T f 1 (λx. f 2 (λy. y)) : X Struct | f 1 : 1•T, f 2 : α•T f 1 (λx. f 2 (λy. y)) : X To see that terms t 1 and t 2 can be distinguished in intml, consider the term s = λg. copy g as g 1 , g 2 in let [x 1 ] = g 1 [false] in let [x 2 ] = g 2 [true] in [nor(x 1 , x 2 )]. The base language term x 1 : 2, x 2 : 2 nor(x 1 , x 2 ) : 2 defines the usual logical nor, i. e. ¬(x 1 ∨ x 2 ). We omit its straightforward definition by case distinction on x 1 and x 2.
Compiling Interactive Terms to Base Terms Now we explain in detail how closed interactive terms are compiled down to base language terms, so that whole intml-programs can be evaluated using base language reduction alone. The compilation works by interpreting interactive terms as message passing circuits and then implementing these circuits by base language terms. The construction does not depend on the bit-width of integers. In the following section we fix a bit-width k and consider all reduction with respect to this bit-width. We note that the translation from interactive terms to base terms does not depend on k, i. e. for any choice of k it produces the same base term.
Relation to the Int-Construction At the beginning of this article we have a construction of message passing circuits from the base language. We have derived this construction from the categorical structure obtained by applying the Int construction to a term model of a basic functional language. We have spelled out the details of intml without reference to this categorical structure, as we believe this presentation to be more broadly accessible. Nevertheless, we would like to explain how intml and the compilation from interactive to base terms can be understood as a model construction within the Int construction. In this section we explain in which sense the circuits defined earlier can be understood as morphisms in a category Int(C) obtained by Int construction from a suitable term model C.
Logarithmic Space We describe a precise correspondence between the class of functions representable in intml and the class of functions computable in logarithmic space. We begin by analysing the space requirements of base language reduction. We consider the space usage of a simple direct implementation of term reduction for the base language. The size needed to encode a term will be proportional to the size of its abstract syntax trees, provided that the size of int-constants is counted appropriately. We For the purposes of relating intml to flogspace, it suffices to prove the following lemma on the space requirements of base language reduction. It states that the space needed for base language reduction is linear in bit-width of integers. Next we show that each of the following inequalities holds, given that the terms on both of its sides are defined.
Let Σ be a fixed, finite alphabet. We show that intml captures the flogspace-computable functions Σ * → Σ *. A) ≤ c 1 • |A 1 | + c 2 • |A 2 | + • • • + c n • |A n | + First, we must define how to represent functions from Σ * to Σ * in intml. We choose an encoding that represents functions in a space efficient way, making essential use of the interactive nature of intml-computation. Any finite set can be represented as a variable-free base language type, e. g. by a sum 1 + • • • + 1 with one summand for each element. We shall use finite sets as if they were base language types, with the understanding that such an encoding has been applied implicitly. For the representation of words we will assume that the bit width of integers is chosen to be log n , where n is the length of the input word.
If one further restricts universal quantification to ∀α ≤ p. X, then one can identify the functions computable in logarithmic space. This has led to Stratified Bounded Affine Logic (sbal)  [42]  with formulae of the form α( p), X ⊗ Y, X Y, ! x<p X and ∀α ≤ p. X. The definition of intml can be seen as the result of a simplifying sbal for programming purposes. The formulae of sbal play the same role as the interactive types in intml. In order to make the type system as simple as possible, intml does not have polymorphism, and the resource polynomials have been enriched to become base language types. The removal of polymorphism is motivated by programming language practice. In System F and the abovementioned linear logics, data types such as natural numbers are defined using impredicative encodings  [17].