Exploring whether students’ use of labelling depends upon the type of activity

This paper explores a labelling feature designed to support higher-level online dialogue. It investigates whether students use labels less often during a structured online dialogue than during an unstructured one, and looks at students’ reactions to labelling and to both types of tasks. Participants are from three successive course offerings of a Master’s-level course (n = 37). All students are allowed but not required to use a labelling feature which enables them to insert phrases such as “Building on your point” directly into their online messages. All students participate in two types of online activities in small groups—first an unstructured online dialogue, then a structured online dialogue. Students tended to use labels significantly less often during the structured dialogue: F(1, 36) = 5.950, p < 0.05. Sixty-two percent of students used the feature more than once during the unstructured dialogue compared to 46% during the structured dialogue. The maximum number of labels that a student used in the unstructured dialogue was 28 versus 16 in the structured dialogue. Students generally found the structured dialogue to be more interesting and relevant, and to have clearer expectations. Student reactions to the labelling feature were mixed: The mean of satisfaction was 18.35, SD = 3.88 (six items on a 5-point Likert scale). Students did not find labelling as useful during the structured dialogue: Perhaps labelling and the activity provided redundant scaffolding. These results imply that features built into the software should be implemented flexibly with thought to the other pedagogical scaffolds in the environment, particularly to the type of activity.     

On two versions of the Loomis–Sikorski Theorem for algebraic structures

We present two versions of the Loomis–Sikorski Theorem, one for monotone σ-complete generalized pseudo effect algebras with strong unit satisfying a kind of the Riesz decomposition property. The second one is for Dedekind σ-complete positive pseudo Vitali spaces with strong unit. For any case we can find an appropriate system of nonnegative bounded functions forming an algebra of the given type with the operations defined by points that maps epimorphically onto the algebra. The paper has been supported by the Center of Excellence SAS—Physics of Information—I/2/2005, the grant VEGA No. 2/6088/26 SAV, the Slovak Research and Development Agency under the contract No. APVV-0071-06, Slovak-Italian Project No. 15:“Algebraic and logical systems of soft computing”, and MURST, project “Analisi Reale”.     

Productive failure in CSCL groups

This study was designed as a confirmatory study of work on productive failure (Kapur, Cognition and Instruction, 26(3), 379–424, 2008). N = 177, 11th-grade science students were randomly assigned to solve either well- or ill-structured problems in a computer-supported collaborative learning (CSCL) environment without the provision of any external support structures or scaffolds. After group problem solving, all students individually solved well-structured problems followed by ill-structured problems. Compared to groups who solved well-structured problems, groups who solved ill-structured problems expectedly struggled with defining, analyzing, and solving the problems. However, despite failing in their collaborative problem-solving efforts, these students outperformed their counterparts from the well-structured condition on the individual near and far transfer measures subsequently, thereby confirming the productive failure hypothesis. Building on the previous study, additional analyses revealed that neither preexisting differences in prior knowledge nor the variation in group outcomes (quality of solutions produced) seemed to have had any significant effect on individual near and far transfer measures, lending support to the idea that it was the nature of the collaborative process that explained productive failure.

Investigations into a left-structural right-substructural sequent calculus

We study a multiple-succedent sequent calculus with both of the structural rules Left Weakening and Left Contraction but neither of their counterparts on the right, for possible application to the treatment of multiplicative disjunction (fission, ‘cotensor’, par) against the background of intuitionistic logic. We find that, as Hirokawa dramatically showed in a 1996 paper with respect to the rules for implication, the rules for this connective render derivable some new structural rules, even though, unlike the rules for implication, these rules are what we call ipsilateral: applying such a rule does not make any (sub)formula change sides—from the left to the right of the sequent separator or vice versa. Some possibilities for a semantic characterization of the resulting logic are also explored. The paper concludes with three open questions.     

Network Design with Weighted Players

We consider a model of game-theoretic network design initially studied by Anshelevich et al. (Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pp. 295–304, 2004), where selfish players select paths in a network to minimize their cost, which is prescribed by Shapley cost shares. If all players are identical, the cost share incurred by a player for an edge in its path is the fixed cost of the edge divided by the number of players using it. In this special case, Anshelevich et al. (Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pp. 295–304, 2004) proved that pure-strategy Nash equilibria always exist and that the price of stability—the ratio between the cost of the best Nash equilibrium and that of an optimal solution—is Θ(log k), where k is the number of players. Little was known about the existence of equilibria or the price of stability in the general weighted version of the game. Here, each player i has a weight w _i ≥1, and its cost share of an edge in its path equals w _i times the edge cost, divided by the total weight of the players using the edge. This paper presents the first general results on weighted Shapley network design games. First, we give a simple example with no pure-strategy Nash equilibrium. This motivates considering the price of stability with respect to α-approximate Nash equilibria—outcomes from which no player can decrease its cost by more than an α multiplicative factor. Our first positive result is that O(log w _max)-approximate Nash equilibria exist in all weighted Shapley network design games, where w _max is the maximum player weight. More generally, we establish the following trade-off between the two objectives of good stability and low cost: for every α=Ω(log w _max), the price of stability with respect to O(α)-approximate Nash equilibria is O((log W)/α), where W is the sum of the players’ weights. In particular, there is always an O(log W)-approximate Nash equilibrium with cost within a constant factor of optimal. Finally, we show that this trade-off curve is nearly optimal: we construct a family of networks without o(log w _max/ log log w _max)-approximate Nash equilibria, and show that for all α=Ω(log w _max/log log w _max), achieving a price of stability of O(log W/α) requires relaxing equilibrium constraints by an Ω(α) factor. Research of H.-L. Chen supported in part by NSF Award 0323766. Research of T. Roughgarden supported in part by ONR grant N00014-04-1-0725, DARPA grant W911NF-04-9-0001, and an NSF CAREER Award.     

Degree-Optimal Routing for P2P Systems

We define a family of Distributed Hash Table systems whose aim is to combine the routing efficiency of randomized networks—e.g. optimal average path length O(log ² n/δlog δ) with δ degree—with the programmability and startup efficiency of a uniform overlay—that is, a deterministic system in which the overlay network is transitive and greedy routing is optimal. It is known that Ω(log n) is a lower bound on the average path length for uniform overlays with O(log n) degree (Xu et al., IEEE J. Sel. Areas Commun. 22(1), 151–163, 2004). Our work is inspired by neighbor-of-neighbor (NoN) routing, a recently introduced variation of greedy routing that allows us to achieve optimal average path length in randomized networks. The advantage of our proposal is that of allowing the NoN technique to be implemented without adding any overhead to the corresponding deterministic network. We propose a family of networks parameterized with a positive integer c which measures the amount of randomness that is used. By varying the value c, the system goes from the deterministic case (c=1) to an “almost uniform” system. Increasing c to relatively low values allows for routing with asymptotically optimal average path length while retaining most of the advantages of a uniform system, such as easy programmability and quick bootstrap of the nodes entering the system. We also provide a matching lower bound for the average path length of the routing schemes for any c. This work was partially supported by the Italian FIRB project “WEB-MINDS” (Wide-scalE, Broadband MIddleware for Network Distributed Services), .     

Incidence structures and Stone–Priestley duality

We observe that if R: = (I,ρ, J) is an incidence structure, viewed as a matrix, then the topological closure of the set of columns is the Stone space of the Boolean algebra generated by the rows. As a consequence, we obtain that the topological closure of the collection of principal initial segments of a poset P is the Stone space of the Boolean algebra Tailalg (P) generated by the collection of principal final segments of P, the so-called tail-algebra of P. Similar results concerning Priestley spaces and distributive lattices are given. A generalization to incidence structures valued by abstract algebras is considered.      

On BCK algebras: Part II: New algebras. The ordinal sum (product) of two bounded BCK algebras

Since all the algebras connected to logic have, more or less explicitly, an associated order relation, it follows, by duality principle, that they have two presentations, dual to each other. We classify these dual presentations in “left” and “right” ones and we consider that, when dealing with several algebras in the same research, it is useful to present them unitarily, either as “left” algebras or as “right” algebras. In some circumstances, this choice is essential, for instance if we want to build the ordinal sum (product) between a BL algebra and an MV algebra. We have chosen the “left” presentation and several algebras of logic have been redefined as particular cases of BCK algebras. We introduce several new properties of algebras of logic, besides those usually existing in the literature, which generate a more refined classification, depending on the properties satisfied. In this work (Parts I–V) we make an exhaustive study of these algebras—with two bounds and with one bound—and we present classes of finite examples, in bounded case. In Part II, we continue to present new properties, and consequently new algebras; among them, bounded α γ algebra is a common generalization of MTL algebra and divisible bounded residuated lattice (bounded commutative Rl-monoid). We introduce and study the ordinal sum (product) of two bounded BCK algebras. Dedicated to Grigore C. Moisil (1906–1973).     

Covering Many or Few Points with Unit Disks

Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems. In the first problem we want to place m unit disks, for a given constant m≥1, such that the total weight of the points from P inside the union of the disks is maximized. We present algorithms that compute, for any fixed ε>0, a (1−ε)-approximation to the optimal solution in O(nlog n) time. In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that computes, for any fixed ε>0, in O(nlog ² n) expected time a disk that is, with high probability, a (1+ε)-approximation to the optimal solution. A preliminary version of this work has appeared in Approximation and Online Algorithms—WAOA 2006, LNCS, vol. 4368.     

Future trends in data mining

Over recent years data mining has been establishing itself as one of the major disciplines in computer science with growing industrial impact. Undoubtedly, research in data mining will continue and even increase over coming decades. In this article, we sketch our vision of the future of data mining. Starting from the classic definition of “data mining”, we elaborate on topics that — in our opinion — will set trends in data mining.     

Quantifiable data mining using ratio rules

Association Rule Mining algorithms operate on a data matrix (e.g., customers products) to derive association rules [AIS93b, SA96]. We propose a new paradigm, namely, Ratio Rules, which are quantifiable in that we can measure the “goodness” of a set of discovered rules. We also propose the “guessing error” as a measure of the “goodness”, that is, the root-mean-square error of the reconstructed values of the cells of the given matrix, when we pretend that they are unknown. Another contribution is a novel method to guess missing/hidden values from the Ratio Rules that our method derives. For example, if somebody bought $10 of milk and $3 of bread, our rules can “guess” the amount spent on butter. Thus, unlike association rules, Ratio Rules can perform a variety of important tasks such as forecasting, answering “what-if” scenarios, detecting outliers, and visualizing the data. Moreover, we show that we can compute Ratio Rules in a single pass over the data set with small memory requirements (a few small matrices), in contrast to association rule mining methods which require multiple passes and/or large memory. Experiments on several real data sets (e.g., basketball and baseball statistics, biological data) demonstrate that the proposed method: (a) leads to rules that make sense; (b) can find large itemsets in binary matrices, even in the presence of noise; and (c) consistently achieves a “guessing error” of up to 5 times less than using straightforward column averages. Received: March 15, 1999 / Accepted: November 1, 1999     

Mining fuzzy specific rare itemsets for education data

Association rule mining is an important data analysis method for the discovery of associations within data. There have been many studies focused on finding fuzzy association rules from transaction databases. Unfortunately, in the real world, one may have available relatively infrequent data, as well as frequent data. From infrequent data, we can find a set of rare itemsets that will be useful for teachers to find out which students need extra help in learning. While the previous association rules discovery techniques are able to discover some rules based on frequency, this is insufficient to determine the importance of a rule composed of frequency-based data items. To remedy this problem, we develop a new algorithm based on the Apriori approach to mine fuzzy specific rare itemsets from quantitative data. Finally, fuzzy association rules can be generated from these fuzzy specific rare itemsets. The patterns are useful to discover learning problems. Experimental results show that the proposed approach is able to discover interesting and valuable patterns from the survey data.     

Student use of Facebook for organizing collaborative classroom activities

Social network sites such as Facebook are often conceived of as purely social spaces; however, as these sites have evolved, so have the ways in which students are using them. In this study, we examine how undergraduate students use the social network site Facebook to engage in classroom-related collaborative activities (e.g., arranging study groups, learning about course processes) to show how Facebook may be used as an informal tool that students use to organize their classroom experiences, and explore the factors that predict type of use. Data from two surveys (N = 302, N = 214) are used to analyze how Facebook use, social and psychological factors, self-efficacy, and types of instructor-student communication on Facebook are related to positive and negative collaboration among students. We found that predictors of Facebook use for class organizing behaviors include self-efficacy and perceived motivation to communicate with others using the site. When placed in the context of social and psychological factors, Facebook intensity did not predict either positive or negative collaboration, suggesting that how students used the site, rather than how often they used the tool or how important they felt it was, affected their propensity to collaborate.     

Limited context semantic translation from a single knowledge-base for a natural language and structuring metarules

The article introduces an experimental system which produces multilingual semantic translations from relatively short texts from a given context. The system was conceived as an investigation instrument whose characteristics are the following: —the elaboration of a single analyzer and generator able to receive, in the form of data, specific information concerning national language, within the limits of a given area of application; —the use of exclusively semantic internal representation, whose formation is derived from “frames” (an object is defined as a list of “attribute-value” couples, permitting recursion); —a single knowledge-base is used for each natural language as initial data (the grammar transmitted was of a semantic-syntacticatn type); —the structure of grammar used in computer language processing being rarely as well adapted to analysis as to generation, the system itself is provided with the possibility of transforming and reorganizing the information for more efficient use at one stage of processing (thus, theatns are used directly in analysis, whereas for the purposes of generation they are “explored” and their information reorganized); —to produce a text, the use of general structuring principles (independent of language) are experimented with. These principles are given in the form of metarules. The application of these metarules to the restructured grammar of a natural language produces specific structuration rules, peculiar to this language. Although the system was conceived for any conceptual area or language, the present knowledge-base of the system (the experimental support) is based on a collection of elementary exercises in three-dimensional geometry written in Rumanian and in French. She does research in the CNRS group C.F. Picard headed by Professor Pitrat, University of Paris 6.     

Mining interesting imperfectly sporadic rules

Detecting association rules with low support but high confidence is a difficult data mining problem. To find such rules using approaches like the Apriori algorithm, minimum support must be set very low, which results in a large number of redundant rules. We are interested in sporadic rules; i.e. those that fall below a maximum support level but above the level of support expected from random coincidence. There are two types of sporadic rules: perfectly sporadic and imperfectly sporadic. Here we are more concerned about finding imperfectly sporadic rules, where the support of the antecedent as a whole falls below maximum support, but where items may have quite high support individually. In this paper, we introduce an algorithm called Mining Interesting Imperfectly Sporadic Rules (MIISR) to find imperfectly sporadic rules efficiently, e.g. fever, headache, stiff neck → meningitis. Our proposed method uses item constraints and coincidence pruning to discover these rules in reasonable time. This paper is an expanded version of Koh et al. [Advances in knowledge discovery and data mining: 10th Pacific-Asia Conference (PAKDD 2006), Singapore. Lecture Notes in Computer Science 3918, Springer, Berlin, pp 473–482]. Yun Sing Koh is currently a Ph.D. student at the Department of Computer Science, University of Otago, New Zealand. Her main research interest is in association rule mining with particular interest in generating hard-to-find association rules and interestingness measures. She holds a B.Sc. (Honours) degree in computer science and a Master’s degree in software engineering, both from the University of Malaya, Malaysia. Nathan Rountree has been a faculty member of the Department of Computer Science at the University of Otago, Dunedin, since 1999. His research interests are in the fields of data mining, artificial neural networks, and computer science education. He is also a consulting software engineer for Profiler Corporation, a Dunedin-based company specialising in data mining and knowledge discovery. Richard A. O’Keefe holds a B.Sc. (Honours) degree in mathematics and physics, majoring in statistics, and an M.Sc. degree in physics (underwater acoustics), both obtained from the University of Auckland, New Zealand. He received his Ph.D. degree in artificial intelligence from the University of Edinburgh. He is the author of “The Craft of Prolog’’ (MIT Press). Dr. O’Keefe is now a lecturer at the University of Otago, New Zealand. His computing interests include declarative programming languages, especially Prolog and Erlang; statistical applications, including data mining and information retrieval; and applications of logic. He is also a member of the editorial board of theory and practice of logic programming.     

Minimum Cost Source Location Problems with Flow Requirements

In this paper, we consider source location problems and their generalizations with three connectivity requirements (arc-connectivity requirements λ and two kinds of vertex-connectivity requirements κ and ), where the source location problems are to find a minimum-cost set S⊆V in a given graph G=(V,A) with a capacity function u:A→ℝ₊ such that for each vertex v∈V, the connectivity from S to v (resp., from v to S) is at least a given demand d ⁻(v) (resp., d ⁺(v)). We show that the source location problem with edge-connectivity requirements in undirected networks is strongly NP-hard, which solves an open problem posed by Arata et al. (J. Algorithms 42: 54–68, 2002). Moreover, we show that the source location problems with three connectivity requirements are inapproximable within a ratio of cln D for some constant c, unless every problem in NP has an O(N ^{log log N} )-time deterministic algorithm. Here D denotes the sum of given demands. We also devise (1+ln D)-approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions. By the inapproximable results above, this implies that all the source location problems are Θ(ln ∑ _v∈V (d ⁺(v)+d ⁻(v)))-approximable. An extended abstract of this paper appeared in Sakashita et al. (Proceedings of LATIN 2006, Chile, LNCS, vol. 3887, pp. 769–780, March 2006).     

Congruences and ideals in pseudoeffect algebras

This paper is devoted to congruences and ideals in pseudoeffect algebras. Let I be a normal ideal in a pseudoeffect algebra E. We show that: (1) the relation ~ _I induced by I is a congruence if and only if for every a∈E, I∩ [0,a] is upper directed; (2) the relation ~ _I induced by I is a strong congruence if and only if I is a normal weak Riesz ideal in a pseudoeffect algebra E. Moreover, we introduce a stronger concept of congruence—namely Riesz strong congruence—and we prove that, if I is a normal weak Riesz ideal in a pseudoeffect algebra E, then ~ _I is a Riesz strong congruence and, conversely, if ~ is a Riesz strong congruence, then I = [0]_~ is a normal weak Riesz ideal, and ~ _I = ~. This work was supported by the National Natural Science Foundation of China (Grant No. 10271069).