Provably Fast Training Algorithms for Support Vector Machines

Support Vector Machines are a family of algorithms for the analysis of data based on convex Quadratic Programming. We derive randomized algorithms for training SVMs, based on a variation of Random Sampling Techniques; these have been successfully used for similar problems. We formally prove an upper bound on the expected running time which is quasilinear with respect to the number of data points and polynomial with respect to the other parameters, i.e., the number of attributes and the inverse of a chosen soft margin parameter. [This is the combined journal version of the conference papers (Balcázar, J.L. et al. in Proceedings of 12th International Conference on Algorithmic Learning Theory (ALT’01), pp. 119–134, [2001]; Balcázar, J.L. et al. in Proceedings of First IEEE International Conference on Data Mining (ICDM’01), pp. 43–50, [2001]; and Balcázar, J.L. et al. in Proceedings of SIAM Workshop in Discrete Mathematics and Data Mining, pp. 19–29, [2002]).] The first and the fourth authors started this research while visiting the Centre de Recerca Matemàtica of the Institute of Catalan Studies in Barcelona. The first author was supported by IST Programme of the EU under contract number IST-1999-14186 (ALCOM-FT), Spanish Government TIC2004-07925-C03-02, and CIRIT 2001SGR-00252. The second author conducted this research while she was with Department of Mathematical and Computing Sciences, Tokyo Institue of Technology, and was supported by a Grant-in-Aid (C-13650444) from Japanese Goverment. The fourth author was supported in part by a Grant-in-Aid for Scientific Research on Priority Areas “Discovery Science” 1998–2000 from Japanese Goverment.     

From Dubins’ car to Reeds and Shepp’s mobile robot

In the paper, a control system with intermediate dynamics between Dubins’ car and Reeds and Shepp’s mobile robot is investigated. Time-limited reachable sets and reachable sets at given time are computed. Families of semipermeable curves that are useful for the detection of jumps of the value function of time-optimal control problem are constructed. Research is partly supported by the Russian Foundation for Fundamental Research under Grants 06-01-00414 and 07-01-96085.     

Soft computing based intention reading techniques as a means of human-robot interaction for human centered system

 Friendly interaction between robot and human is vital in the design of a human centered system. Among several interaction technologies, the intention reading of the user plays an important role for the human centered system. We focus on the aspect of intention reading in rehabilitation robots, and implement its capability for the wheelchair-based robotic arm system, called KARES (KAIST Rehabilitation Engineering Service System) II. An effective intention reading scheme is proposed on the basis of several soft computing techniques to handle uncertainty of the user's intention. Two application examples of intention reading in KARES II are discussed: one is visual servoing of the user's face, and the other is emergency stop of the robot by using EMG signals of the user's arm. This work is partially supported by the Ministry of Science and Technology of Korea as a part of Critical Technology 21 Program on “Development of Service Robot Technology”.     

A Protocol for a Private Set-Operation

A new private set-operation problem is proposed. Suppose there are n parties with each owning a secret set. Let one of them, say P, be the leader, S be P＇s secret set, and t （less than n - 1） be a threshold value. For each element w of S, if w appears more than t times in the rest parties＇ sets, then P learns which parties＇ sets include w, otherwise P cannot know whether w appears in any party＇s set. For this problem, a secure protocol is proposed in the semi-honest model based on semantically secure homomorphic encryption scheme, secure sharing scheme, and the polynomial representation of sets. The protocol only needs constant rounds of communication.     

Optimal External Memory Planar Point Enclosure

In this paper we study the external memory planar point enclosure problem: Given N axis-parallel rectangles in the plane, construct a data structure on disk (an index) such that all K rectangles containing a query point can be reported I/O-efficiently. This problem has important applications in e.g. spatial and temporal databases, and is dual to the important and well-studied orthogonal range searching problem. Surprisingly, despite the fact that the problem can be solved optimally in internal memory with linear space and O(log N+K) query time, we show that one cannot construct a linear sized external memory point enclosure data structure that can be used to answer a query in O(log  _B N+K/B) I/Os, where B is the disk block size. To obtain this bound, Ω(N/B ^1−ε ) disk blocks are needed for some constant ε>0. With linear space, the best obtainable query bound is O(log ₂ N+K/B) if a linear output term O(K/B) is desired. To show this we prove a general lower bound on the tradeoff between the size of the data structure and its query cost. We also develop a family of structures with matching space and query bounds. An extended abstract of this paper appeared in Proceedings of the 12th European Symposium on Algorithms (ESA’04), Bergen, Norway, September 2004, pp. 40–52. L. Arge’s research was supported in part by the National Science Foundation through RI grant EIA–9972879, CAREER grant CCR–9984099, ITR grant EIA–0112849, and U.S.-Germany Cooperative Research Program grant INT–0129182, as well as by the US Army Research Office through grant W911NF-04-01-0278, by an Ole Roemer Scholarship from the Danish National Science Research Council, a NABIIT grant from the Danish Strategic Research Council and by the Danish National Research Foundation. V. Samoladas’ research was supported in part by a grant co-funded by the European Social Fund and National Resources-EPEAEK II-PYTHAGORAS. K. Yi’s research was supported in part by the National Science Foundation through ITR grant EIA–0112849, U.S.-Germany Cooperative Research Program grant INT–0129182, and Hong Kong Direct Allocation Grant (DAG07/08).     

Analysis of Approximation Algorithms for <Emphasis Type="Italic">k</Emphasis>-Set Cover Using Factor-Revealing Linear Programs

We present new combinatorial approximation algorithms for the k-set cover problem. Previous approaches are based on extending the greedy algorithm by efficiently handling small sets. The new algorithms further extend these approaches by utilizing the natural idea of computing large packings of elements into sets of large size. Our results improve the previously best approximation bounds for the k-set cover problem for all values of k≥6. The analysis technique used could be of independent interest; the upper bound on the approximation factor is obtained by bounding the objective value of a factor-revealing linear program. A preliminary version of the results in this paper appeared in Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT ’07), LNCS 4639, Springer, pp. 52–63, 2007. This work was partially supported by the European Union under IST FET Integrated Project 015964 AEOLUS and by the General Secretariat for Research and Technology of the Greek Ministry of Development under programme PENED 2003.     

Mining changing regions from access-constrained snapshots: a cluster-embedded decision tree approach

Change detection on spatial data is important in many applications, such as environmental monitoring. Given a set of snapshots of spatial objects at various temporal instants, a user may want to derive the changing regions between any two snapshots. Most of the existing methods have to use at least one of the original data sets to detect changing regions. However, in some important applications, due to data access constraints such as privacy concerns and limited data online availability, original data may not be available for change analysis. In this paper, we tackle the problem by proposing a simple yet effective model-based approach. In the model construction phase, data snapshots are summarized using the novel cluster-embedded decision trees as concise models. Once the models are built, the original data snapshots will not be accessed anymore. In the change detection phase, to mine changing regions between any two instants, we compare the two corresponding cluster-embedded decision trees. Our systematic experimental results on both real and synthetic data sets show that our approach can detect changes accurately and effectively. Irene Pekerskaya’s and Jian Pei’s research is supported partly by National Sciences and Engineering Research Council of Canada and National Science Foundation of the US, and a President’s Research Grant and an Endowed Research Fellowship Award at Simon Fraser University. Ke Wang’s research is supported partly by Natural Sciences and Engineering Research Council of Canada. All opinions, findings, conclusions and recommendations in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.     

Network invariants for real-time systems

We extend the approach of model checking parameterized networks of processes by means of network invariants to the setting of real-time systems. We introduce timed transition structures (which are similar in spirit to timed automata) and define a notion of abstraction that is safe with respect to linear temporal properties. We strengthen the notion of abstraction to allow a finite system, then called network invariant, to be an abstraction of networks of real-time systems. In general the problem of checking abstraction of real-time systems is undecidable. Hence, we provide sufficient criteria, which can be checked automatically, to conclude that one system is an abstraction of a concrete one. Our method is based on timed superposition and discretization of timed systems. We exemplify our approach by proving mutual exclusion of a simple protocol inspired by Fischer’s protocol, using the model checker TLV. Part of this work was done during O. Grinchtein’s stay at Weizmann Institute. This author was supported by the European Research Training Network “Games”.     

Molecular Robotics: A New Paradigm for Artifacts

The rapid progress of molecular nanotechnology has opened the door to molecular robotics, which uses molecules as robot components. In order to promote this new paradigm, the Molecular Robotics Research Group was established in the Systems and Information Division of the Society of Instrument and Control Engineers (SICE) in 2010. The group consists of researchers from various fields including chemistry, biophysics, DNA nanotechnology, systems science and robotics, challenging this emerging new field. Last year, the group proposed a research project focusing on molecular robotics, and it was recently awarded a Grant-in-Aid for Scientific Research on Innovative Areas (FY2012-16), one of the large-scale research projects in Japan, by MEXT (Ministry of Education, Culture, Sports, Science and Technology, JAPAN). Here, we wish to clarify the fundamental concept and research direction of molecular robotics. For this purpose, we present a comprehensive view of molecular robotics based on the discussions held in the Molecular Robotics Research Group.     

Modeling, simulation and fuzzy control of an anthropomorphic robot arm by using Dymola

Analysis and fuzzy control of an anthropomorphic robot arm on a special trajectory is the subject of this paper. These types of systems are used in cutting operations on materials, joining materials by welding, material handling in remote and dangerous environments, packing of foods, inspection/testing electronic parts or medical products. This robot arm realizes the handling motion on a special trajectory. In this study, the first three links of Mitsubishi RV-2AJ Industrial Robot, are like an anthropomorphic arm, have been modeled and simulated by using Dymola. Kinematic equations have been obtained and mathematical model of this system has been formed by using Lagrange’s Equations. Fuzzy logic controller for the joint angles for the motion trajectory has been designed and the simulation results have been presented at the end of the study.     

The attentional spotlight

One of the interesting and occasionally controversial aspects of Dennett’s career is his direct involvement in the scientific process. This article describes some of Dennett’s participation on one particular project conducted at MIT, the building of the humanoid robot named Cog. One of the intentions of this project, not to date fully realized, was to test Dennett’s multiple drafts theory of consciousness. I describe Dennett’s involvement and impact on Cog from the perspective of a graduate student. I also describe the problem of coordinating distributed intelligent systems, drawing examples from robot intelligence, human intelligence, and the Cog project itself.     

Mechanism design for policy routing

The Border Gateway Protocol (BGP) for interdomain routing is designed to allow autonomous systems (ASes) to express policy preferences over alternative routes. We model these preferences as arising from an AS’s underlying utility for each route and study the problem of finding a set of routes that maximizes the overall welfare (ie, the sum of all ASes’ utilities for their selected routes). We show that, if the utility functions are unrestricted, this problem is NP-hard even to approximate closely. We then study a natural class of restricted utilities that we call next-hop preferences. We present a strategyproof, polynomial-time computable mechanism for welfare-maximizing routing over this restricted domain. However, we show that, in contrast to earlier work on lowest-cost routing mechanism design, this mechanism appears to be incompatible with BGP and hence difficult to implement in the context of the current Internet. Our contributions include a new complexity measure for Internet algorithms, dynamic stability, which may be useful in other problem domains. Supported in part by ONR grant N00014-01-1-0795 and NSF grantITR-0219018.Supported by ONR grant N00014-01-1-0795 and NSF grant ITR-0219018. Most of this work was done while the author was at Yale University. Supported in part by NSF grants ITR-0121555 and ANI-0207399. This work was supported by the DoD University Research Initiative (URI) program administered by the Office of Naval Research under Grant N00014-01-1-0795. It was presented in preliminary form at the 2004 ACM Symposium on Principles of Distributed Computing [7]. Portions of this work appeared in preliminary form in the second author’s PhD Thesis [16].     

Application of self-organizing maps and multilayer neural networks in problems of person identification

The problem of identifying individualizing characteristics of an object using information on bone chemistry extracted from data arrays as a base is considered. It is shown that the use of self-organizing maps allows one to detect the presence of structuredness in learning data arrays and to discriminate significant inputs. Multilayer neural networks are used to reproduce the dependences discovered. Both of the computational tools are considered to be components of the software system of person identification. Igor’ Evgen’evich Shepelev. Born in 1977. Graduated from Rostov State University in 2000 and received his candidate’s degree in 2004. He is currently is with the Research Institute of Neurocybernetics of the South Federal University as a senior research fellow. Scientific interests include artificial neural networks for problems of pattern recognition and robot technology. He is the author of 19 publications.     

Scheduling algorithms for procrastinators

This paper presents scheduling algorithms for procrastinators, where the speed that a procrastinator executes a job increases as the due date approaches. We give optimal off-line scheduling policies for linearly increasing speed functions. We then explain the computational/numerical issues involved in implementing this policy. We next explore the online setting, showing that there exist adversaries that force any online scheduling policy to miss due dates. This impossibility result motivates the problem of minimizing the maximum interval stretch of any job; the interval stretch of a job is the job’s flow time divided by the job’s due date minus release time. We show that several common scheduling strategies, including the “hit-the-highest-nail” strategy beloved by procrastinators, have arbitrarily large maximum interval stretch. Then we give the “thrashing” scheduling policy and show that it is a Θ(1) approximation algorithm for the maximum interval stretch. Research of M.A. Bender was supported in part by NSF Grants CCR-0208670, CCF-0621439/0621425, CCF-0540897/05414009, CCF-0634793/0632838, and CNS-0627645.     

Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information

In semi-online scheduling problems, we always assume that some partial additional information is exactly known in advance. This may not be true in some application. This paper considers semi-online problems on identical machines with inexact partial information. Three problems are considered, where we know in advance that the optimal value, or the largest job size are in given intervals, respectively, while their exact values are unknown. We give both lower bounds of the problems and competitive ratios of algorithms as functions of a so-called disturbance parameter r ∈[1, ∞). We establish for which r the inexact partial information is useful to improve the performance of a semi-online algorithm with respect to its pure online problem. Optimal preemptive semi-online algorithms are then obtained. Research supported by Natural Science Foundation of China (10671177) and Natural Science Foundation of Zhejiang Province (Y605316) and its preliminary version appeared in proceedings of ISAAC’05.     

Speed Scaling of Tasks with Precedence Constraints

We consider the problem of speed scaling to conserve energy in a multiprocessor setting where there are precedence constraints between tasks, and where the performance measure is the makespan. That is, we consider an energy bounded version of the classic problem Pm | prec | C _max. We extend the standard 3-field notation and denote this problem as Sm | prec, energy | C _max. We show that, without loss of generality, one need only consider constant power schedules. We then show how to reduce this problem to the problem Qm | prec | C _max to obtain a poly-log(m)-approximation algorithm. A preliminary version of this paper appears in Proceedings of the 3rd Workshop on Approximation and Online Algorithms (WAOA 2005). Research of K. Pruhs supported in part by NSF grants CCR-0098752, ANI-0123705, CNS-0325353, CCF-0448196, CCF-0514058, and IIS-0534531. Research of R. van Stee supported by Alexander von Humboldt-Stiftung.     

‘Working Well, Together’: Arts-Based Research and the Cultural Future of Small Cities

This article offers a research update on a 3-year programme initiated by the Kamloops Art Gallery and the University College of the Cariboo in Kamloops, British Columbia. The programme is supported by a ‘Community–University Research Alliance’ grant from the Social Sciences and Humanities Research Council of Canada, and the collaboration focuses on the cultural future of small cities – on how cultural and arts organisations work together (or fail to work together) in a small city setting. If not by definition, then certainly by default, ‘culture’ is associated with big city life: big cities are equated commonly with ‘big culture’; small cities with something less. The Cultural Future of Small Cities research group seeks to provide a more nuanced view of what constitutes culture in a small Canadian city. In particular, the researchers are exploring notions of social capital and community asset building: in this context, ‘visual and verbal representation’, ‘home’, ‘community’ and the need to define a local ‘sense of place’ have emerged as important themes. As the Small Cities programme begins its second year, a unique but key aspect has become the artist-as-researcher. Correspondence and offprint requests to: L. Dubinsky, Kamloops Art Gallery, 101–465 Victoria Street, Kamloops, BC V2C 2A9 Canada. Tel.: 250-828-3543; Email: ldubinsky@museums.ca     

Merged processes: a new condensed representation of Petri net behaviour

Model checking based on Petri net unfoldings is an approach widely applied to cope with the state space explosion problem. In this paper, we propose a new condensed representation of a Petri net’s behaviour called merged processes, which copes well not only with concurrency, but also with other sources of state space explosion, viz sequences of choices and non-safeness. Moreover, this representation is sufficiently similar to the traditional unfoldings, so that a large body of results developed for the latter can be re-used. Experimental results indicate that the proposed representation of a Petri net’s behaviour alleviates the state space explosion problem to a significant degree and is suitable for model checking.V. Khomenko is a Royal Academy of Engineering/Epsrc Research Fellow supported by the RAEng/Epsrc grant EP/C53400X/1 (Davac).M. Koutny is supported by the EC IST grant 511599 (Rodin).W. Vogler is supported by the DFG-project STG-Dekomposition VO 615/7-1     

A proof-theoretic foundation of abortive continuations

We give an analysis of various classical axioms and characterize a notion of minimal classical logic that enforces Peirce’s law without enforcing Ex Falso Quodlibet. We show that a “natural” implementation of this logic is Parigot’s classical natural deduction. We then move on to the computational side and emphasize that Parigot’s λ μ corresponds to minimal classical logic. A continuation constant must be added to λ μ to get full classical logic. The extended calculus is isomorphic to a syntactical restriction of Felleisen’s theory of control that offers a more expressive reduction semantics. This isomorphic calculus is in correspondence with a refined version of Prawitz’s natural deduction. This article is an extended version of the conference article “Minimal Classical Logic and Control Operators” (Ariola and Herbelin, Lecture Notes in Computer Science, vol. 2719, pp. 871–885, 2003). A longer version is available as a technical report (Ariola et al., Technical Report TR608, Indiana University, 2005). Z.M. Ariola supported by National Science Foundation grant number CCR-0204389. A. Sabry supported by National Science Foundation grant number CCR-0204389, by a Visiting Researcher position at Microsoft Research, Cambridge, U.K., and by a Visiting Professor position at the University of Genova, Italy.     

Scrub Nurse Robot for Laparoscopic Surgery

During laparoscopic surgeries, changing forceps is a relatively simple procedure that requires a nurse or another surgeon; however, most hospitals lack a scrub nurse in the operating room. Therefore, we have developed an assisting robot for laparoscopic surgery that is able to pass or receive forceps under the voice control of the surgeon. This robot system consists of a magazine that holds all forceps to be used in one operation and a robot arm that passes or receives forceps between the magazine and surgeon. These two components are located side by side and have a linear actuator for height adjustment. A bar code is attached to the forceps to identify the forceps. This system utilizes speech recognition software and can select the forceps requested by the surgeon. After the robot hand grasps the forceps from the magazine, the arm and the wrist turn to hand the forceps to the surgeon. When the surgeon lays the used forceps on the return holder, the robot returns the forceps to the magazine in a similar motion as when passing the forceps to the surgeon. This robot can, thus, compensate for the shortage of scrub nurses required for surgery.