Computational Algorithms for Censored-Data Problems Using Intersection Graphs

This article presents methods for finding the nonparametric maximum likelihood estimate (NPMLE) of the distribution function of time-to-event data. The basic approach is to use graph theory (in particular intersection graphs) to simplify the problem. Censored data can be represented in terms of their intersection graph. Existing combinatorial algorithms can be used to find the important structures, namely the maximal cliques. When viewed in this framework there is no fundamental difference between right censoring, interval censoring, double censoring, or current status data and hence the algorithms apply to all types of data. These algorithms can be extended to deal with bivariate data and indeed there are no fundamental problems extending the methods to higher dimensional data. Finally this article shows how to obtain the NPMLE using convex optimization methods and methods for mixing distributions. The implementation of these methods is greatly simplified through the graph-theoretic representation of the data.     

Searching for knowledge in a world flooded with facts

The wide availability of computer technology and large electronic storage media has led to an enormous proliferation of databases in almost every area of human endeavour. This naturally creates an intense demand for powerful methods and tools for data analysis. Current methods and tools are primarily oriented toward extracting numerical and statistical data characteristics. While such characteristics are very important and useful, they are often insufficient. A decision maker typically needs an interpretation of these findings, and this has to be done by a data analyst. With the growth in the amount and complexity of the data, making such interpretations is an increasingly difficult problem. As a potential solution, this paper advocates the development of methods for conceptual data analysis. Such methods aim at semi-automating the processes of determining high-level data interpretations, and discovering qualitative patterns in data. It is argued that these methods could be built on the basis of algorithms developed in the area of machine learning. An exemplary system utilizing such algorithms, INLEN, is discussed. The system integrates machine learning and statistical analysis techniques with database and expert system technologies. Selected capabilities of the system are illustrated by examples from implemented modules.     

基于网络结构特征的大规模虚假评论群组识别

目前识别虚假评论的方法主要基于评论内容的文本特征和评论者的行为特征,然而评论文本与评论者行为容易被伪造和模仿,且这两类方法只能对虚假评论逐个识别,本文考虑了虚假评论的网络结构特征,通过分析评论者的网络行为及评论者节点间的网络结构特征定义相邻节点多样性与自相似性,利用累积分布函数估计其概率并合成网络行为得分,以得分高的可疑产品为种子建立2-hop子图,筛选子图中高度相似的虚假评论候选群组,利用GroupStrainer、HDBSCAN等算法对其进行聚类合并,以发现隐藏的虚假评论群组。以亚马逊四类最畅销的产品数据集为样本进行实证分析的结果表明,文中提出的方法能够有效识别隐藏较深的大规模虚假评论群组,综合群组内容的统计特征分析发现,虚假评论群组对目标产品的攻击模式存在产品类别差异,虚假评论群组比真实评论者对目标产品具有更强的集中度,但同时也会利用其它非目标产品对自身进行伪装以弱化其可疑性。     

Lower complexity bounds for interpolation algorithms

We introduce and discuss a new computational model for the Hermite-Lagrange interpolation with nonlinear classes of polynomial interpolants. We distinguish between an interpolation problem and an algorithm that solves it. Our model includes also coalescence phenomena and captures a large variety of known Hermite-Lagrange interpolation problems and algorithms. Like in traditional Hermite-Lagrange interpolation, our model is based on the execution of arithmetic operations (including divisions) in the field where the data (nodes and values) are interpreted and arithmetic operations are counted at unit cost. This leads us to a new view of rational functions and maps defined on arbitrary constructible subsets of complex affine spaces. For this purpose we have to develop new tools in algebraic geometry which themselves are mainly based on Zariski’s Main Theorem and the theory of places (or equivalently: valuations). We finish this paper by exhibiting two examples of Lagrange interpolation problems with nonlinear classes of interpolants, which do not admit efficient interpolation algorithms (one of these interpolation problems requires even an exponential quantity of arithmetic operations in terms of the number of the given nodes in order to represent some of the interpolants).In other words, classic Lagrange interpolation algorithms are asymptotically optimal for the solution of these selected interpolation problems and nothing is gained by allowing interpolation algorithms and classes of interpolants to be nonlinear. We show also that classic Lagrange interpolation algorithms are almost optimal for generic nodes and values. This generic data cannot be substantially compressed by using nonlinear techniques.We finish this paper highlighting the close connection of our complexity results in Hermite-Lagrange interpolation with a modern trend in software engineering: architecture tradeoff analysis methods (ATAM).     

Bound Analysis Through HDMR for Multivariate Data Modelling - CMMSE

Multivariate data modelling problems consist of a number of nodes with associated function (class) values. The main purpose of these problems is to construct an analytical model to represent the characteristics of the problem under consideration. Because the devices, tools, and/or algorithms used to collect the data may have incapabilities or limited capabilities, the data set is likely to contain unavoidable errors. That is, each component of data is reliable only within an interval which contains the data value. To this end, when an analytical structure is needed for the given data, a band structure should be determined instead of a unique structure. As the multivariance of the given data set increases, divide–and–conquer methods become important in multivariate modelling problems. HDMR based methods allow us to partition the given multivariate data into less variate data sets to reduce the complexity of the given problem. This paper focuses on Interval Factorized HDMR method developed to determine an approximate band structure for a given multivariate data modelling problem having uncertainties on its nodes and function values.     

图像反问题中的数学与深度学习方法

我们生活在数字的时代,数据已经成为了我们生活中不可或缺的一部分,而图像无疑是最重要的数据类型之一.图像反问题,包括图像降噪,去模糊,修复,生物医学成像等,是图像科学中的重要领域.计算机技术的飞速发展使得我们可以用精细的数学和机器学习工具来为图像反问题设计有效的解决方案.本文主要回顾图像反问题中的三大类方法,即以小波（框架）为代表的计算调和分析法、偏微分方程（PDE）方法和深度学习方法.我们将回顾这些方法的建模思想和一些具体数学形式,探讨它们之间的联系与区别,优点与缺点,探讨将这些方法有机融合的可行性与优势.     

Strongly optimal algorithms and optimal information in estimation problems

This paper studies some aspects of information-based complexity theory applied to estimation, identification, and prediction problems. Particular emphasis is given to constructive aspects of optimal algorithms and optimal information, taking into account the characteristics of certain types of problems. Special attention is devoted to the investigation of strongly optimal algorithms and optimal information in the linear case. Two main results are obtained for the class of problems considered. First, central algorithms are proved to be strongly optimal. Second, a simple solution is given to a particular case of optimal information, called optimal sampling design, which is of great interest in system and identification theory.     

Die Nutzung von Programmierwerkzeugen für das Lösen offener Aufgaben im Mathematikunterricht der Sekundarstufe I

Due to the fact that the computer tools available at present in mathematics teaching offer only inferior capabilities for solving (open) problems, their capabilities being restricted to sequential algorithms, and also because the of mathematics—informaties paradigm is inadequately formulated, standardized programming tools are needed in order to handle certain types of problems. The article presents examples of arithmetic problems and their solution using standardized programming tools, so as to illustrate their applications in: developing programs for the derivation of multi-element solution sets (as well as for strengthening the inductive basis required in order to find propositions); modifying available programs in order to be able to deal with diversified or extended open problems; using standardized programs as a ?black-box” software for checking or elaborating strategies for open problem solving.     

Analysis using natural language processing of feedback data from two mathematics support centres

ABSTRACT

This paper explores analysis of feedback data collected from student consultations at two mathematics support centres at universities in Australia and Ireland. Unstructured text data was collected over six years and includes qualitative data on student queries collected during the consultations from mathematics and statistics related subjects. Topic modelling and clustering algorithms are used to uncover key themes in the data across stages. Common areas of difficulty experienced by undergraduate students at both universities are investigated and a comparison between them is shown. The results suggest that, despite institutional differences, there is considerable overlap in the types of mathematical and statistical difficulties experienced by students in their first and second year of university at these institutions. We discuss how the ability to uncover such common mathematical and statistical themes with the aid of text mining techniques can be used to improve the support provided by mathematics support centres in terms of providing an efficient and effective service. The code for analyses at both institutions is provided in a GitHub repository so other academic support centres may use it. Outcomes of this analysis have implications for mainstream mathematics and statistics instructors who wish to gain further insights into their students' learning.     

Multidisciplinary Simulations with the Coupling Library MpCCI

Extreme high demands on designing accurate prototypes for example in the fields of medical research, aircraft construction, shipbuilding and automotive industry require multidisciplinary simulations. A large number of tools for monodisciplinary simulations are available today. Each of these provides high quality simulation results in a specific physical domain. Now there is also a solution to do multidisciplinary computations: Parallel monodisciplinary codes are coupled with the Mesh based parallel Code Coupling Interface MpCCI to solve multidisciplinary problems with a loose coupled approach. The paper presents applications in the framework of fluid‐structure interaction, which demonstrate the advantages of the parallel coupling library for this kind of problems. The computational fluid dynamics code FLOWer developed at the Institute of Design Aerodynamics/DLR and the structural mechanics code SIMPACK developed at the Institute of Aeroelasticity/DLR are coupled to solve an aeroelastic test problem. The applicability of the coupling library in the field of aeroelasticity is strongly dependent on the integrated interpolations between the involved meshes. In the Institute of Aeroelasticity the aeroelastic analysis tool CAESAR was developed which includes aeroelasticity specific interpolation algorithms. These routines are integrated in MpCCI via a special interface. There are two types of interpolation routines included. The first kind of algorithms is based on the method of finite interpolation elements and the second uses radial basis functions.     

Performance Space Analysis for an Industrial Product

As a guide for developing additions to a line of machine tools a model of the "performance space" of competing brands was developed using catalogue specifications of 25 performance related characteristics. A two-stage analytical process, utilizing cluster analysis and non-metric multidimensional scaling, yielded five- and three-dimensional solutions, in which the axes of the spaces were summary measures of performance. Brands which had similar performance characteristics, in the sense that they could perform similar types of operations, were located "close" to each other in these spaces. The techniques illustrated are quite general and can be applied in a variety of situations, even if (interval scaled) "measured" performance data are not available.     

Perspectives on self-scaling variable metric algorithms

Recent attempts to assess the performance of SSVM algorithms for unconstrained minimization problems differ in their evaluations from earlier assessments. Nevertheless, the new experiments confirm earlier observations that, on certain types of problems, the SSVM algorithms are far superior to other variable metric methods. This paper presents a critical review of these recent assessments and discusses some current interpretations advanced to explain the behavior of SSVM methods. The paper examines the new empirical results, in light of the original self-scaling theory, and introduces a new interpretation of these methods based on anL-function model of the objective function. This interpretation sheds new light on the performance characteristics of the SSVM methods, which contributes to the understanding of their behavior and helps in characterizing classes of problems which can benefit from the self-scaling approach.The subject of this paper was presented at the ORSA/TIMS National Meeting in New York, 1978.This work was done while the author was with the Analysis Research Group, Xerox Palo Alto Research Center, Palo Alto, California.     

Hybrid symbolic-numeric algorithms for computational convex analysis

Computational convex analysis focuses on developing efficient tools to compute fundamental transforms arising in convex analysis. Symbolic computation tools have been developed, and have allowed more insight into the calculation of the Fenchel conjugate and related transforms. When such tools are not applicable e.g. when there is no closed form, fast transform algorithms perform numerical computation efficiently. However, computing the composition of several transforms is difficult to achieve with fast transform algorithms, which is the case for the recently introduced proximal average operator. We consider the class of piecewise linear-quadratic functions which, being closed under the most relevant operations in convex analysis, allows the robust and efficient numerical computation of compositions of transforms like the proximal average. The algorithms presented are hybrid symbolic-numeric: they first compute a piecewise linear-quadratic approximation of the function, and then manipulate the approximation symbolically. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An introduction to the analysis of approximation algorithms

Approximation algorithms may be inevitable choice when it comes to the solution of difficult combinatorial problems. The mathematical analysis of approximation algorithms can lead to various types of results. In this introductory paper, these various possibilities are illustrated on an example taken from scheduling theory.     

Local and parallel finite element algorithms based on two-grid discretizations

A number of new local and parallel discretization and adaptive finite element algorithms are proposed and analyzed in this paper for elliptic boundary value problems. These algorithms are motivated by the observation that, for a solution to some elliptic problems, low frequency components can be approximated well by a relatively coarse grid and high frequency components can be computed on a fine grid by some local and parallel procedure. The theoretical tools for analyzing these methods are some local a priori and a posteriori estimates that are also obtained in this paper for finite element solutions on general shape-regular grids. Some numerical experiments are also presented to support the theory.

     

Computerunterstützung offener Aufgabenstellungen im Geometrieunterricht

The conventional and traditional way of mathematics teaching for the most part relies on practising and performance of algorithms and solutions of certain kinds of problems. The exclusive objective of the required activities for solving the convergent problems that are generally used in this connection is to achieve methodological competence. This approach reduces mathematics teaching to the purpose of achieving calculational competence and ignores an essential inherent component, namely the chance to stimulate the creativity and create incentives to generate something completely new. Lack of appropriate tools may be one reason explaining the fact that this creative aspect has been left almost unconsidered in teaching practice so far, because solving “open problems” requires specific tools and means. The following article is intended to demonstrate, with a concrete example from geometry teaching at lower secondary level, the opportunities opened up by the computer when used as a tool for introducing in class the typical problems and mathematical problem solving strategies required for mathematics beyond methods and calculational competence.     

Variational analysis of circular cone programs

This paper conducts variational analysis of circular programs, which form a new class of optimization problems in nonsymmetric conic programming, important for optimization theory and its applications. First, we derive explicit formulas in terms of the initial problem data to calculate various generalized derivatives/co-derivatives of the projection operator associated with the circular cone. Then we apply generalized differentiation and other tools of variational analysis to establish complete characterizations of full and tilt stability of locally optimal solutions to parameterized circular programs.     

生物信息中的概率统计方法

随着生物研究技术的不断改进与突破，特别是人类，水稻，大鼠，小鼠等的基因组测序与后基因组计划的迅猛推进，未来几年蛋白质和核酸的测序数据将以指数方式增加，生物信息学成为当前生物学领域的研究热点，预计在未来的若干年中它还将变得越来越重要．这是因为海量数据的获，导只是为知识的获得提供了条件，如果不能从中找出规律性的事物，数据本身往往并不显示知识．例如人类基因组测序只不过提供了用4种核酸(A，T，C，G)的序列书写成的人类机体的设计书．拿到了书并不意味着知道书中的内容．对一个识字不多的人来说，拿到书只是到达懂得书中内容这一遥远征途的第一小步．事实上，人们对于人类基因组的认识，大概也就是小学水平．另一方面，当前，生物的实验技术不仅达到了很高的精度，而且具有极高的通量．我们正在生物信息学研究的一个有活力的新时代．不少科学家还说它是人类基因组研究的收获时代，它不仅将赋予人们获得各种基础研究的重要成果的可能性，也带来取得巨大的经济效益和社会效益成果的很多机会．这是一个难得的机遇，我国应尽快综合利用它，充分发挥各学科交叉研究的威力，走向国际科学界的最前沿．在这一过程中，数学思想、模型、算法，特别是概率统计的思想与方法起到很关键的作用．     

A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 Special Session on Real Parameter Optimization

In recent years, there has been a growing interest for the experimental analysis in the field of evolutionary algorithms. It is noticeable due to the existence of numerous papers which analyze and propose different types of problems, such as the basis for experimental comparisons of algorithms, proposals of different methodologies in comparison or proposals of use of different statistical techniques in algorithms’ comparison. In this paper, we focus our study on the use of statistical techniques in the analysis of evolutionary algorithms’ behaviour over optimization problems. A study about the required conditions for statistical analysis of the results is presented by using some models of evolutionary algorithms for real-coding optimization. This study is conducted in two ways: single-problem analysis and multiple-problem analysis. The results obtained state that a parametric statistical analysis could not be appropriate specially when we deal with multiple-problem results. In multiple-problem analysis, we propose the use of non-parametric statistical tests given that they are less restrictive than parametric ones and they can be used over small size samples of results. As a case study, we analyze the published results for the algorithms presented in the CEC’2005 Special Session on Real Parameter Optimization by using non-parametric test procedures.     

Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches

Proofs from complexity theory as well as computational experiments indicate that most lot sizing problems are hard to solve. Because these problems are so difficult, various solution techniques have been proposed to solve them. In the past decade, meta-heuristics such as tabu search, genetic algorithms and simulated annealing, have become popular and efficient tools for solving hard combinatorial optimization problems. We review the various meta-heuristics that have been specifically developed to solve lot sizing problems, discussing their main components such as representation, evaluation, neighborhood definition and genetic operators. Further, we briefly review other solution approaches, such as dynamic programming, cutting planes, Dantzig–Wolfe decomposition, Lagrange relaxation and dedicated heuristics. This allows us to compare these techniques. Understanding their respective advantages and disadvantages gives insight into how we can integrate elements from several solution approaches into more powerful hybrid algorithms. Finally, we discuss general guidelines for computational experiments and illustrate these with several examples.