-
A Mixed Tree-Cotree Gauge for the Reduced Basis Approximation of Maxwell's Eigenvalue Problem
Authors:
Anna Ziegler,
Sebastian Schöps
Abstract:
Model order reduction methods are a powerful tool to drastically reduce the computational effort of problems which need to be evaluated repeatedly, i.e., when computing the same system for various parameter values. When applying a reduced basis approximation algorithm to the Maxwell eigenvalue problem, we encounter spurious solutions in the reduced system which hence need to be removed during the…
▽ More
Model order reduction methods are a powerful tool to drastically reduce the computational effort of problems which need to be evaluated repeatedly, i.e., when computing the same system for various parameter values. When applying a reduced basis approximation algorithm to the Maxwell eigenvalue problem, we encounter spurious solutions in the reduced system which hence need to be removed during the basis construction. In this paper, we discuss two tree-cotree gauge-based methods for the removal of the spurious eigenmodes.
△ Less
Submitted 17 June, 2024;
originally announced June 2024.
-
Table tennis ball spin estimation with an event camera
Authors:
Thomas Gossard,
Julian Krismer,
Andreas Ziegler,
Jonas Tebbe,
Andreas Zell
Abstract:
Spin plays a pivotal role in ball-based sports. Estimating spin becomes a key skill due to its impact on the ball's trajectory and bouncing behavior. Spin cannot be observed directly, making it inherently challenging to estimate. In table tennis, the combination of high velocity and spin renders traditional low frame rate cameras inadequate for quickly and accurately observing the ball's logo to e…
▽ More
Spin plays a pivotal role in ball-based sports. Estimating spin becomes a key skill due to its impact on the ball's trajectory and bouncing behavior. Spin cannot be observed directly, making it inherently challenging to estimate. In table tennis, the combination of high velocity and spin renders traditional low frame rate cameras inadequate for quickly and accurately observing the ball's logo to estimate the spin due to the motion blur. Event cameras do not suffer as much from motion blur, thanks to their high temporal resolution. Moreover, the sparse nature of the event stream solves communication bandwidth limitations many frame cameras face. To the best of our knowledge, we present the first method for table tennis spin estimation using an event camera. We use ordinal time surfaces to track the ball and then isolate the events generated by the logo on the ball. Optical flow is then estimated from the extracted events to infer the ball's spin. We achieved a spin magnitude mean error of $10.7 \pm 17.3$ rps and a spin axis mean error of $32.9 \pm 38.2°$ in real time for a flying ball.
△ Less
Submitted 15 April, 2024;
originally announced April 2024.
-
Spiking Neural Networks for Fast-Moving Object Detection on Neuromorphic Hardware Devices Using an Event-Based Camera
Authors:
Andreas Ziegler,
Karl Vetter,
Thomas Gossard,
Jonas Tebbe,
Andreas Zell
Abstract:
Table tennis is a fast-paced and exhilarating sport that demands agility, precision, and fast reflexes. In recent years, robotic table tennis has become a popular research challenge for robot perception algorithms. Fast and accurate ball detection is crucial for enabling a robotic arm to rally the ball back successfully. Previous approaches have employed conventional frame-based cameras with Convo…
▽ More
Table tennis is a fast-paced and exhilarating sport that demands agility, precision, and fast reflexes. In recent years, robotic table tennis has become a popular research challenge for robot perception algorithms. Fast and accurate ball detection is crucial for enabling a robotic arm to rally the ball back successfully. Previous approaches have employed conventional frame-based cameras with Convolutional Neural Networks (CNNs) or traditional computer vision methods. In this paper, we propose a novel solution that combines an event-based camera with Spiking Neural Networks (SNNs) for ball detection. We use multiple state-of-the-art SNN frameworks and develop a SNN architecture for each of them, complying with their corresponding constraints. Additionally, we implement the SNN solution across multiple neuromorphic edge devices, conducting comparisons of their accuracies and run-times. This furnishes robotics researchers with a benchmark illustrating the capabilities achievable with each SNN framework and a corresponding neuromorphic edge device. Next to this comparison of SNN solutions for robots, we also show that an SNN on a neuromorphic edge device is able to run in real-time in a closed loop robotic system, a table tennis robot in our use case.
△ Less
Submitted 15 March, 2024;
originally announced March 2024.
-
Shape uncertainty quantification of Maxwell eigenvalues and -modes with application to TESLA cavities
Authors:
Jürgen Dölz,
David Ebert,
Sebastian Schöps,
Anna Ziegler
Abstract:
We consider Maxwell eigenvalue problems on uncertain shapes with perfectly conducting TESLA cavities being the driving example. Due to the shape uncertainty the resulting eigenvalues and eigenmodes are also uncertain and it is well known that the eigenvalues may exhibit crossings or bifurcations under perturbation. We discuss how the shape uncertainties can be modelled using the domain mapping app…
▽ More
We consider Maxwell eigenvalue problems on uncertain shapes with perfectly conducting TESLA cavities being the driving example. Due to the shape uncertainty the resulting eigenvalues and eigenmodes are also uncertain and it is well known that the eigenvalues may exhibit crossings or bifurcations under perturbation. We discuss how the shape uncertainties can be modelled using the domain mapping approach and how the deformation mapping can be expressed as coefficients in Maxwell's equations. Using derivatives of these coefficients and derivatives of the eigenpairs, we follow a perturbation approach to compute approximations of mean and covariance of the eigenpairs. For small perturbations these approximations are faster and more accurate than sampling or surrogate model strategies. For the implementation we use an approach based on isogeometric analysis, which allows for straightforward modelling of the domain deformations and computation of the required derivatives. Numerical experiments for a three-dimensional 9-cell TESLA cavity are presented.
△ Less
Submitted 11 June, 2024; v1 submitted 22 January, 2024;
originally announced January 2024.
-
A multi-modal table tennis robot system
Authors:
Andreas Ziegler,
Thomas Gossard,
Karl Vetter,
Jonas Tebbe,
Andreas Zell
Abstract:
In recent years, robotic table tennis has become a popular research challenge for perception and robot control. Here, we present an improved table tennis robot system with high accuracy vision detection and fast robot reaction. Based on previous work, our system contains a KUKA robot arm with 6 DOF, with four frame-based cameras and two additional event-based cameras. We developed a novel calibrat…
▽ More
In recent years, robotic table tennis has become a popular research challenge for perception and robot control. Here, we present an improved table tennis robot system with high accuracy vision detection and fast robot reaction. Based on previous work, our system contains a KUKA robot arm with 6 DOF, with four frame-based cameras and two additional event-based cameras. We developed a novel calibration approach to calibrate this multimodal perception system. For table tennis, spin estimation is crucial. Therefore, we introduced a novel, and more accurate spin estimation approach. Finally, we show how combining the output of an event-based camera and a Spiking Neural Network (SNN) can be used for accurate ball detection.
△ Less
Submitted 25 November, 2023; v1 submitted 29 October, 2023;
originally announced October 2023.
-
Gradient-Based Eigenvalue Optimization for Electromagnetic Cavities with Built-in Mode Matching
Authors:
Anna Ziegler,
Robert Hahn,
Victoria Isensee,
Anh Duc Nguyen,
Sebastian Schöps
Abstract:
Shape optimization with respect to eigenvalues of a cavity plays an important role in the design of new resonators or in the optimization of existing ones. In our paper, we propose a gradient-based optimization scheme, which we enhance with closed-form shape derivatives of the system matrices. Based on these, we can compute accurate derivatives of eigenvalues, eigenmodes and the cost function with…
▽ More
Shape optimization with respect to eigenvalues of a cavity plays an important role in the design of new resonators or in the optimization of existing ones. In our paper, we propose a gradient-based optimization scheme, which we enhance with closed-form shape derivatives of the system matrices. Based on these, we can compute accurate derivatives of eigenvalues, eigenmodes and the cost function with respect to the geometry, which significantly reduces the computational effort of the optimizer. We demonstrate our work by applying it to the 9-cell TESLA cavity, for which we tune the design parameters of the computational model to match the design criteria for devices in realistic use cases. Since eigenvalues may cross during the shape optimization of a cavity, we propose a new algorithm based on an eigenvalue matching procedure, to ensure the optimization of the desired mode in order to also enable successful matching along large shape variations.
△ Less
Submitted 24 October, 2023;
originally announced October 2023.
-
eWand: A calibration framework for wide baseline frame-based and event-based camera systems
Authors:
Thomas Gossard,
Andreas Ziegler,
Levin Kolmar,
Jonas Tebbe,
Andreas Zell
Abstract:
Accurate calibration is crucial for using multiple cameras to triangulate the position of objects precisely. However, it is also a time-consuming process that needs to be repeated for every displacement of the cameras. The standard approach is to use a printed pattern with known geometry to estimate the intrinsic and extrinsic parameters of the cameras. The same idea can be applied to event-based…
▽ More
Accurate calibration is crucial for using multiple cameras to triangulate the position of objects precisely. However, it is also a time-consuming process that needs to be repeated for every displacement of the cameras. The standard approach is to use a printed pattern with known geometry to estimate the intrinsic and extrinsic parameters of the cameras. The same idea can be applied to event-based cameras, though it requires extra work. By using frame reconstruction from events, a printed pattern can be detected. A blinking pattern can also be displayed on a screen. Then, the pattern can be directly detected from the events. Such calibration methods can provide accurate intrinsic calibration for both frame- and event-based cameras. However, using 2D patterns has several limitations for multi-camera extrinsic calibration, with cameras possessing highly different points of view and a wide baseline. The 2D pattern can only be detected from one direction and needs to be of significant size to compensate for its distance to the camera. This makes the extrinsic calibration time-consuming and cumbersome. To overcome these limitations, we propose eWand, a new method that uses blinking LEDs inside opaque spheres instead of a printed or displayed pattern. Our method provides a faster, easier-to-use extrinsic calibration approach that maintains high accuracy for both event- and frame-based cameras.
△ Less
Submitted 3 April, 2024; v1 submitted 22 September, 2023;
originally announced September 2023.
-
Reduced Basis Approximation for Maxwell's Eigenvalue Problem and Parameter-Dependent Domains
Authors:
Max Kappesser,
Anna Ziegler,
Sebastian Schöps
Abstract:
In many high-frequency simulation workflows, eigenvalue tracking along a parameter variation is necessary. This can become computationally prohibitive when repeated time-consuming eigenvalue problems must be solved. Therefore, we employ a reduced basis approximation to bring down the computational costs. It is based on the greedy strategy from Horger et al. 2017 which considers multiple eigenvalue…
▽ More
In many high-frequency simulation workflows, eigenvalue tracking along a parameter variation is necessary. This can become computationally prohibitive when repeated time-consuming eigenvalue problems must be solved. Therefore, we employ a reduced basis approximation to bring down the computational costs. It is based on the greedy strategy from Horger et al. 2017 which considers multiple eigenvalues for elliptic eigenvalue problems. We extend this algorithm to deal with parameter-dependent domains and the Maxwell eigenvalue problem. In this setting, the reduced basis may contain spurious eigenmodes, which require special treatment. We demonstrate our algorithm in an eigenvalue tracking application for an eigenmode classification.
△ Less
Submitted 4 August, 2023;
originally announced August 2023.
-
SpinDOE: A ball spin estimation method for table tennis robot
Authors:
Thomas Gossard,
Jonas Tebbe,
Andreas Ziegler,
Andreas Zell
Abstract:
Spin plays a considerable role in table tennis, making a shot's trajectory harder to read and predict. However, the spin is challenging to measure because of the ball's high velocity and the magnitude of the spin values. Existing methods either require extremely high framerate cameras or are unreliable because they use the ball's logo, which may not always be visible. Because of this, many table t…
▽ More
Spin plays a considerable role in table tennis, making a shot's trajectory harder to read and predict. However, the spin is challenging to measure because of the ball's high velocity and the magnitude of the spin values. Existing methods either require extremely high framerate cameras or are unreliable because they use the ball's logo, which may not always be visible. Because of this, many table tennis-playing robots ignore the spin, which severely limits their capabilities. This paper proposes an easily implementable and reliable spin estimation method. We developed a dotted-ball orientation estimation (DOE) method, that can then be used to estimate the spin. The dots are first localized on the image using a CNN and then identified using geometric hashing. The spin is finally regressed from the estimated orientations. Using our algorithm, the ball's orientation can be estimated with a mean error of 2.4° and the spin estimation has an relative error lower than 1%. Spins up to 175 rps are measurable with a camera of 350 fps in real time. Using our method, we generated a dataset of table tennis ball trajectories with position and spin, available on our project page.
△ Less
Submitted 7 March, 2023;
originally announced March 2023.
-
Bayesian Quantification with Black-Box Estimators
Authors:
Albert Ziegler,
Paweł Czyż
Abstract:
Understanding how different classes are distributed in an unlabeled data set is an important challenge for the calibration of probabilistic classifiers and uncertainty quantification. Approaches like adjusted classify and count, black-box shift estimators, and invariant ratio estimators use an auxiliary (and potentially biased) black-box classifier trained on a different (shifted) data set to esti…
▽ More
Understanding how different classes are distributed in an unlabeled data set is an important challenge for the calibration of probabilistic classifiers and uncertainty quantification. Approaches like adjusted classify and count, black-box shift estimators, and invariant ratio estimators use an auxiliary (and potentially biased) black-box classifier trained on a different (shifted) data set to estimate the class distribution and yield asymptotic guarantees under weak assumptions. We demonstrate that all these algorithms are closely related to the inference in a particular Bayesian model, approximating the assumed ground-truth generative process. Then, we discuss an efficient Markov Chain Monte Carlo sampling scheme for the introduced model and show an asymptotic consistency guarantee in the large-data limit. We compare the introduced model against the established point estimators in a variety of scenarios, and show it is competitive, and in some cases superior, with the state of the art.
△ Less
Submitted 17 February, 2023;
originally announced February 2023.
-
On the computation of analytic sensitivities of eigenpairs in isogeometric analysis
Authors:
Anna Ziegler,
Melina Merkel,
Peter Gangl,
Sebastian Schöps
Abstract:
The eigenmodes of resonating structures, e.g., electromagnetic cavities, are sensitive to deformations of their shape. In order to compute the sensitivities of the eigenpair with respect to a scalar parameter, we state the Laplacian and Maxwellian eigenvalue problems and discretize the models using isogeometric analysis. Since we require the derivatives of the system matrices, we differentiate the…
▽ More
The eigenmodes of resonating structures, e.g., electromagnetic cavities, are sensitive to deformations of their shape. In order to compute the sensitivities of the eigenpair with respect to a scalar parameter, we state the Laplacian and Maxwellian eigenvalue problems and discretize the models using isogeometric analysis. Since we require the derivatives of the system matrices, we differentiate the system matrices for each setting considering the appropriate function spaces for geometry and solution. This approach allows for a straightforward computation of arbitrary higher order sensitivities in a closed-form. In our work, we demonstrate the application in a setting of small geometric deformations, e.g., for the investigation of manufacturing uncertainties of electromagnetic cavities, as well as in an eigenvalue tracking along a shape morphing.
△ Less
Submitted 20 December, 2022;
originally announced December 2022.
-
Extracting Meaningful Attention on Source Code: An Empirical Study of Developer and Neural Model Code Exploration
Authors:
Matteo Paltenghi,
Rahul Pandita,
Austin Z. Henley,
Albert Ziegler
Abstract:
The high effectiveness of neural models of code, such as OpenAI Codex and AlphaCode, suggests coding capabilities of models that are at least comparable to those of humans. However, previous work has only used these models for their raw completion, ignoring how the model reasoning, in the form of attention weights, can be used for other downstream tasks. Disregarding the attention weights means di…
▽ More
The high effectiveness of neural models of code, such as OpenAI Codex and AlphaCode, suggests coding capabilities of models that are at least comparable to those of humans. However, previous work has only used these models for their raw completion, ignoring how the model reasoning, in the form of attention weights, can be used for other downstream tasks. Disregarding the attention weights means discarding a considerable portion of what those models compute when queried. To profit more from the knowledge embedded in these large pre-trained models, this work compares multiple approaches to post-process these valuable attention weights for supporting code exploration. Specifically, we compare to which extent the transformed attention signal of CodeGen, a large and publicly available pretrained neural model, agrees with how developers look at and explore code when each answering the same sense-making questions about code. At the core of our experimental evaluation, we collect, manually annotate, and open-source a novel eye-tracking dataset comprising 25 developers answering sense-making questions on code over 92 sessions. We empirically evaluate five attention-agnostic heuristics and ten attention-based post processing approaches of the attention signal against our ground truth of developers exploring code, including the novel concept of follow-up attention which exhibits the highest agreement. Beyond the dataset contribution and the empirical study, we also introduce a novel practical application of the attention signal of pre-trained models with completely analytical solutions, going beyond how neural models' attention mechanisms have traditionally been used.
△ Less
Submitted 11 October, 2022;
originally announced October 2022.
-
Real-time event simulation with frame-based cameras
Authors:
Andreas Ziegler,
Daniel Teigland,
Jonas Tebbe,
Thomas Gossard,
Andreas Zell
Abstract:
Event cameras are becoming increasingly popular in robotics and computer vision due to their beneficial properties, e.g., high temporal resolution, high bandwidth, almost no motion blur, and low power consumption. However, these cameras remain expensive and scarce in the market, making them inaccessible to the majority. Using event simulators minimizes the need for real event cameras to develop no…
▽ More
Event cameras are becoming increasingly popular in robotics and computer vision due to their beneficial properties, e.g., high temporal resolution, high bandwidth, almost no motion blur, and low power consumption. However, these cameras remain expensive and scarce in the market, making them inaccessible to the majority. Using event simulators minimizes the need for real event cameras to develop novel algorithms. However, due to the computational complexity of the simulation, the event streams of existing simulators cannot be generated in real-time but rather have to be pre-calculated from existing video sequences or pre-rendered and then simulated from a virtual 3D scene. Although these offline generated event streams can be used as training data for learning tasks, all response time dependent applications cannot benefit from these simulators yet, as they still require an actual event camera. This work proposes simulation methods that improve the performance of event simulation by two orders of magnitude (making them real-time capable) while remaining competitive in the quality assessment.
△ Less
Submitted 23 March, 2023; v1 submitted 10 September, 2022;
originally announced September 2022.
-
Productivity Assessment of Neural Code Completion
Authors:
Albert Ziegler,
Eirini Kalliamvakou,
Shawn Simister,
Ganesh Sittampalam,
Alice Li,
Andrew Rice,
Devon Rifkin,
Edward Aftandilian
Abstract:
Neural code synthesis has reached a point where snippet generation is accurate enough to be considered for integration into human software development workflows. Commercial products aim to increase programmers' productivity, without being able to measure it directly. In this case study, we asked users of GitHub Copilot about its impact on their productivity, and sought to find a reflection of thei…
▽ More
Neural code synthesis has reached a point where snippet generation is accurate enough to be considered for integration into human software development workflows. Commercial products aim to increase programmers' productivity, without being able to measure it directly. In this case study, we asked users of GitHub Copilot about its impact on their productivity, and sought to find a reflection of their perception in directly measurable user data. We find that the rate with which shown suggestions are accepted, rather than more specific metrics regarding the persistence of completions in the code over time, drives developers' perception of productivity.
△ Less
Submitted 13 May, 2022;
originally announced May 2022.
-
Self-Supervised Learning of Object Parts for Semantic Segmentation
Authors:
Adrian Ziegler,
Yuki M. Asano
Abstract:
Progress in self-supervised learning has brought strong general image representation learning methods. Yet so far, it has mostly focused on image-level learning. In turn, tasks such as unsupervised image segmentation have not benefited from this trend as they require spatially-diverse representations. However, learning dense representations is challenging, as in the unsupervised context it is not…
▽ More
Progress in self-supervised learning has brought strong general image representation learning methods. Yet so far, it has mostly focused on image-level learning. In turn, tasks such as unsupervised image segmentation have not benefited from this trend as they require spatially-diverse representations. However, learning dense representations is challenging, as in the unsupervised context it is not clear how to guide the model to learn representations that correspond to various potential object categories. In this paper, we argue that self-supervised learning of object parts is a solution to this issue. Object parts are generalizable: they are a priori independent of an object definition, but can be grouped to form objects a posteriori. To this end, we leverage the recently proposed Vision Transformer's capability of attending to objects and combine it with a spatially dense clustering task for fine-tuning the spatial tokens. Our method surpasses the state-of-the-art on three semantic segmentation benchmarks by 17%-3%, showing that our representations are versatile under various object definitions. Finally, we extend this to fully unsupervised segmentation - which refrains completely from using label information even at test-time - and demonstrate that a simple method for automatically merging discovered object parts based on community detection yields substantial gains.
△ Less
Submitted 20 June, 2022; v1 submitted 27 April, 2022;
originally announced April 2022.
-
Mode Recognition by Shape Morphing for Maxwell's Eigenvalue Problem
Authors:
Anna Ziegler,
Niklas Georg,
Wolfgang Ackermann,
Sebastian Schöps
Abstract:
In electrical engineering, for example during the design of superconducting radio-frequency cavities, eigenmodes must be identified based on their field patterns. This allows to understand the working principle, optimize the performance of a device and distinguish desired from parasitic modes. For cavities with simple shapes, the eigenmodes are easily classified according to the number of nodes an…
▽ More
In electrical engineering, for example during the design of superconducting radio-frequency cavities, eigenmodes must be identified based on their field patterns. This allows to understand the working principle, optimize the performance of a device and distinguish desired from parasitic modes. For cavities with simple shapes, the eigenmodes are easily classified according to the number of nodes and antinodes in each direction as is obvious from analytical formulae. For cavities with complicated shapes, the eigenmodes are determined numerically. Thereby, the classification is cumbersome, if not impossible. In this paper, we propose a new recognition method by morphing the cavity geometry to a pillbox and tracking its eigenmodes during the deformation.
△ Less
Submitted 1 March, 2022;
originally announced March 2022.
-
Exploration Without Global Consistency Using Local Volume Consolidation
Authors:
Titus Cieslewski,
Andreas Ziegler,
Davide Scaramuzza
Abstract:
In exploration, the goal is to build a map of an unknown environment. Most state-of-the-art approaches use map representations that require drift-free state estimates to function properly. Real-world state estimators, however, exhibit drift. In this paper, we present a 2D map representation for exploration that is robust to drift. Rather than a global map, it uses local metric volumes connected by…
▽ More
In exploration, the goal is to build a map of an unknown environment. Most state-of-the-art approaches use map representations that require drift-free state estimates to function properly. Real-world state estimators, however, exhibit drift. In this paper, we present a 2D map representation for exploration that is robust to drift. Rather than a global map, it uses local metric volumes connected by relative pose estimates. This pose-graph does not need to be globally consistent. Overlaps between the volumes are resolved locally, rather than on the faulty estimate of space. We demonstrate our representation with a frontier-based exploration approach, evaluate it under different conditions and compare it with a commonly-used grid-based representation. We show that, at the cost of longer exploration time, using the proposed representation allows full coverage of space even for very large drift in the state estimate, contrary to the grid-based representation. The system is validated in a real world experiment and we discuss its extension to 3D.
△ Less
Submitted 3 September, 2019;
originally announced September 2019.
-
Unsupervised Recalibration
Authors:
Albert Ziegler,
Paweł Czyż
Abstract:
Unsupervised recalibration (URC) is a general way to improve the accuracy of an already trained probabilistic classification or regression model upon encountering new data while deployed in the field. URC does not require any ground truth associated with the new field data. URC merely observes the model's predictions and recognizes when the training set is not representative of field data, and the…
▽ More
Unsupervised recalibration (URC) is a general way to improve the accuracy of an already trained probabilistic classification or regression model upon encountering new data while deployed in the field. URC does not require any ground truth associated with the new field data. URC merely observes the model's predictions and recognizes when the training set is not representative of field data, and then corrects to remove any introduced bias.
URC can be particularly useful when applied separately to different subpopulations observed in the field that were not considered as features when training the machine learning model. This makes it possible to exploit subpopulation information without retraining the model or even having ground truth for some or all subpopulations available.
Additionally, if these subpopulations are the object of study, URC serves to determine the correct ground truth distributions for them, where naive aggregation methods, like averaging the model's predictions, systematically underestimate their differences.
△ Less
Submitted 17 October, 2020; v1 submitted 24 August, 2019;
originally announced August 2019.
-
The standard coder: a machine learning approach to measuring the effort required to produce source code change
Authors:
Ian Wright,
Albert Ziegler
Abstract:
We apply machine learning to version control data to measure the quantity of effort required to produce source code changes. We construct a model of a `standard coder' trained from examples of code changes produced by actual software developers together with the labor time they supplied. The effort of a code change is then defined as the labor hours supplied by the standard coder to produce that c…
▽ More
We apply machine learning to version control data to measure the quantity of effort required to produce source code changes. We construct a model of a `standard coder' trained from examples of code changes produced by actual software developers together with the labor time they supplied. The effort of a code change is then defined as the labor hours supplied by the standard coder to produce that change. We therefore reduce heterogeneous, structured code changes to a scalar measure of effort derived from large quantities of empirical data on the coding behavior of software developers. The standard coder replaces traditional metrics, such as lines-of-code or function point analysis, and yields new insights into what code changes require more or less effort.
△ Less
Submitted 6 March, 2019;
originally announced March 2019.
-
On Finding Maximum Cardinality Subset of Vectors with a Constraint on Normalized Squared Length of Vectors Sum
Authors:
Anton V. Eremeev,
Alexander V. Kelmanov,
Artem V. Pyatkin,
Igor A. Ziegler
Abstract:
In this paper, we consider the problem of finding a maximum cardinality subset of vectors, given a constraint on the normalized squared length of vectors sum. This problem is closely related to Problem 1 from (Eremeev, Kel'manov, Pyatkin, 2016). The main difference consists in swapping the constraint with the optimization criterion.
We prove that the problem is NP-hard even in terms of finding a…
▽ More
In this paper, we consider the problem of finding a maximum cardinality subset of vectors, given a constraint on the normalized squared length of vectors sum. This problem is closely related to Problem 1 from (Eremeev, Kel'manov, Pyatkin, 2016). The main difference consists in swapping the constraint with the optimization criterion.
We prove that the problem is NP-hard even in terms of finding a feasible solution. An exact algorithm for solving this problem is proposed. The algorithm has a pseudo-polynomial time complexity in the special case of the problem, where the dimension of the space is bounded from above by a constant and the input data are integer. A computational experiment is carried out, where the proposed algorithm is compared to COINBONMIN solver, applied to a mixed integer quadratic programming formulation of the problem. The results of the experiment indicate superiority of the proposed algorithm when the dimension of Euclidean space is low, while the COINBONMIN has an advantage for larger dimensions.
△ Less
Submitted 19 July, 2017;
originally announced July 2017.
-
Unbiased split variable selection for random survival forests using maximally selected rank statistics
Authors:
Marvin N. Wright,
Theresa Dankowski,
Andreas Ziegler
Abstract:
The most popular approach for analyzing survival data is the Cox regression model. The Cox model may, however, be misspecified, and its proportionality assumption may not always be fulfilled. An alternative approach for survival prediction is random forests for survival outcomes. The standard split criterion for random survival forests is the log-rank test statistics, which favors splitting variab…
▽ More
The most popular approach for analyzing survival data is the Cox regression model. The Cox model may, however, be misspecified, and its proportionality assumption may not always be fulfilled. An alternative approach for survival prediction is random forests for survival outcomes. The standard split criterion for random survival forests is the log-rank test statistics, which favors splitting variables with many possible split points. Conditional inference forests avoid this split variable selection bias. However, linear rank statistics are utilized by default in conditional inference forests to select the optimal splitting variable, which cannot detect non-linear effects in the independent variables. An alternative is to use maximally selected rank statistics for the split point selection. As in conditional inference forests, splitting variables are compared on the p-value scale. However, instead of the conditional Monte-Carlo approach used in conditional inference forests, p-value approximations are employed. We describe several p-value approximations and the implementation of the proposed random forest approach. A simulation study demonstrates that unbiased split variable selection is possible. However, there is a trade-off between unbiased split variable selection and runtime. In benchmark studies of prediction performance on simulated and real datasets the new method performs better than random survival forests if informative dichotomous variables are combined with uninformative variables with more categories and better than conditional inference forests if non-linear covariate effects are included. In a runtime comparison the method proves to be computationally faster than both alternatives, if a simple p-value approximation is used.
△ Less
Submitted 16 May, 2018; v1 submitted 11 May, 2016;
originally announced May 2016.