Inzendingen VVS-scriptieprijs voor Statistiek en Operationele Research

De jury heeft de volgende inzendingen ontvangen.

Deelnemer: Casper Albers
Titel scriptie: Estimating bivariate distributions assuming some form of dependence

Let (X, Y) be an independent random sample of size n from a bivariate population with joint distribution function H. The stochastic variables X and Y are assumed to be (positively) associated in some way. To incorporate this assumption, various mathematical-statistical definitions can be used. We prefer the concept of (positive) quadrant dependence. This thesis contains various methods for estimating the distribution function H(x,y).

Two semiparametric methods are developed and a nonparametric method is discussed. The results are not very promising: though those of the semi-parametric methods display various similarities, they are considerably different. This might suggest that samples of size 50 are too small to arrive at acceptable estimates, unless restrictive assumptions are imposed.

Deelnemer: Sanne de Boer
Titel scriptie: A new non-parametric approach to bivariate regression

In de praktijk is het vaak van belang verbanden tussen variabelen te schatten. Zo zou het voor de directie van een fabriek heel nuttig kunnen zijn het verband te kennen tussen de productie enerzijds en de hoeveelheid ingezette arbeiders en machines anderzijds. De productie is hier de te verklaren variabele, de hoeveelheden arbeiders en machines zijn de verklarende variabelen. Een probleem hierbij is dat de data met betrekking tot deze variabelen niet exact het verband weerspiegelen: het is onmogelijk externe invloeden helemaal te voorkomen.

Soms is de precieze aard van het verband vooraf bekend en hoeven er "alleen" nog wat parameters geschat te worden. Een bekende methode hiertoe is lineaire regressie. Het komt echter ook voor dat het onwenselijk is vooraf te stringente aannames te maken. In dit geval heet het schatten van de functie die de variabelen verbindt "niet-parametrische regressie". In het algemeen wordt van de geschatte functie verlangd dat hij aan twee eisen voldoet. Enerzijds moet hij natuurlijk goed bij de data passen, anderzijds moet het een gladde functie zijn. Dat laatste houdt in dat de functie bijvoorbeeld niet wild heen en weer springt. De mate van verlangde gladheid moet vooraf worden vastgesteld.

Een bekende niet-parametrische regressie methode is het minimaliseren van een straffunctie bestaande uit een gewogen gemiddelde van maatstaven die de kwaliteit van de fit aangeven en de mate van gladheid. Een andere methode is om vooraf een stochastisch model te formuleren voor het verloop van een zeer algemene gladde functie. Deze zogenaamde prior wordt dan gecombineerd met de data in een Bayesiaanse combinatieslag. Het resultaat is een gladde en goed fittende schatting van de functie. Met deze laatste methode heb ik me voor het geval van twee verklarende variabelen ("bivariate regressie") bezig gehouden.

Om moeilijke continue stochastische processen te vermijden heb ik een discretisatie toegepast waardoor de verklarende variabelen op een zeer fijne tweedimensionale grid kwamen te liggen. Op deze grid heb ik recursief een stochastisch proces gedefinieerd voor de prior functie. Dit proces is zo gedefinieerd dat het onwaarschijnlijk is dat de differentiequotiënten van de functie zich wild gedragen, dit was de verlangde graad van gladheid. Dit proces heb ik geformuleerd als een zogenaamd State Space model, dat voor elk datapunt een verdeling geeft van de functiewaarde aldaar. Vervolgens kon met behulp van een Kalman filter de informatie die de data verschaffen hiermee op een samenhangende manier gecombineerd worden. Dit leidt uiteindelijk tot een maximum likelihood schatting van de functie. Het nieuwe aspect van deze aanpak is de discretisatie en de aanpak met het Kalman filter die daardoor mogelijk wordt.

Ik heb de resultaten van deze methode vergeleken met verschillende andere methodes. Dit heb ik gedaan door een testfunctie te definiëren, hier stochastische storingen aan toe te voegen en vervolgens de schattingsalgoritmes hierop los te laten. Wanneer de testfuncties niet al te wild verliepen (anders is de geëiste mate van gladheid ook te groot!) bleek mijn methode qua schattingsresultaten goed te voldoen. Bijkomende voordelen zijn er in computationele zin en in dat de State Space formulering allerlei extra mogelijkheden biedt. Zo wordt het mogelijk een alternatieve schatting van de functie te toetsen tegen de maximum likelihood schatting en om het schattingsalgoritme op een simpele manier robuuster te maken tegen outliers. Op grond van deze resultaten beschouw ik de in mijn scriptie ontwikkelde methode als een interessant alternatief voor bivariate regressie.

Deelnemer: Simone van den Bosch
Titel scriptie: Modellering van tijdreeksen met behulp van dynamische lineaire modellen en toepassen van het Kalman filter

Een tijdreeks is een collectie van observaties die opeenvolgend in tijd genomen zijn. De observaties worden gemodelleerd m.b.v. een dynamisch lineair model (DLM). Een DLM beschrijft op ieder tijdstip twee lineaire modellen:

  • het ene model beschrijft de samenhang tussen de observaties en de modelparameters;
  • het andere model beschrijft de verandering van de modelparameters in de tijd.

Het klassieke lineaire regressiemodel is te schrijven als een DLM. Een ander voorbeeld van een DLM is het zogenaamde lineaire groeimodel, waarbij de grafiek van de observaties uitgezet tegen de tijd een rechte lijn is.

M.b.v. het zogenaamde Kalman filter, een Bayesiaanse manier beschreven in de jaren zestig door Kalman krijgt men mooie recursieve formules en is het onder andere mogelijk de verwachtingswaarde en een 95% betrouwbaarheidsinterval van de observatie op het volgende tijdstip te bepalen.

Na de introductie in DLM en het Kalman filter wordt het DLM met meerdere toestanden beschreven. Als illustratie heb ik het lineaire groeimodel gekozen, waarbij op een bepaald tijdstip zich vier mogelijke toestanden kunnen voordoen:

  • stabiele toestand;
  • verandering van niveau;
  • verandering van richtingscoëfficiënt;
  • uitschieter.

Er wordt ervan uitgegaan dat de effecten van alle mogelijke toestanden op tijdstip t - 1 te verwaarlozen zijn op tijdstip t + 1 en door gebruik te maken van benaderingen van kansdichtheidsfuncties en het Kalman filter kan men uitspraken doen over de volgende observatie. Het benaderen van kansdichtheidsfuncties vormt een zeer belangrijk onderdeel. Om de recursie in de formules te behouden wordt een kansdichtheidsfunctie, die een mix is van kansdichtheidsfuncties van normale verdelingen d.m.v. het minimaliseren van de zogenaamde Kullback-Leibler directed divergence benaderd door de kansdichtheidsfunctie van een normale verdeling.

Naast voorspellen speelt controle ook een grote rol in de tijdreeksanalye, het is dan ook mogelijk op ieder tijdstip een kansuitspraak te doen over de toestand op dat moment, één tijdstip of twee tijdstippen terug.

Deelnemer: Gido A.J.F. Brouns
Titel scriptie: Prestatieanalyse van mainframe computersystemen

De theorie van netwerken van wachtrijen kan op een groot aantal verschillende gebieden gebruikt worden ter modellering en analyse van reële systemen. In dit verslag gaat de aandacht specifiek uit naar mainframe computersystemen, maar de hoofdresultaten, gepresenteerd in de vorm van algoritmen, zijn zodanig dat ze ook aangewend kunnen worden in geval van systemen van andere aard. Hierbij kan onder andere gedacht worden aan produktie-, communicatie- of transportsystemen.

Het voornaamste doel was het opzetten van een model waarmee de prestaties van een bestaand of nog te bouwen computersysteem geëvalueerd kunnen worden. Door het gedrag van de zich in het systeem bevindende componenten en opdrachten te meten aan de hand van een aantal vastgelegde prestatiegrootheden, kan een oordeel uitgesproken worden over de prestaties die het systeem levert.

Enerzijds is het hierdoor voor reeds bestaande computersystemen mogelijk zich in het systeem voordoende problemen, bijvoorbeeld overbelaste disks, aan het licht te brengen. Anderzijds biedt deze analyse de mogelijkheid relatief snel en zonder veel kosten na te gaan of een nog aan te schaffen en te configureren systeem aan de door de gebruiker gestelde eisen kan voldoen. Verder kan op deze manier op interactieve wijze gezocht worden naar een optimale configuratie, zonder eerst daadwerkelijk een concreet systeem op te moeten bouwen en te moeten testen.

De ontwikkelde modellen hebben we vertaald naar een aantal algoritmen. De exact- en nauwkeurigheid van deze algoritmen werd getest door de resultaten die voor een aantal karakteristieke praktijkvoorbeelden van computersystemen volgen uit deze algoritmen, te vergelijken met de resultaten die volgen uit simulaties van dezelfde computersystemen. De voorbeelden zijn zodanig gekozen dat ze een groot scala aan praktijksituaties overdekken.

Het onderzoek is deels verricht aan de Technische Universiteit Eindhoven en deels bij Consul Risk Management B.V., een Nederlandse onderneming met als kernactiviteiten software development en software consultancy. Consul brengt onder andere het softwareprodukt Consul/View Solver op de markt. Dit programma voorziet bedrijven die tot de installatie van een of meerdere mainframe computers over willen gaan van een geïntegreerd beslissingsondersteunend systeem, dat een veelheid aan prestatiemeting- en modelleringfaciliteiten biedt. Deze dragen zorg voor een groter inzicht in de werking van specifieke mainframe computersystemen.

De door ons ontwikkelde algoritmen hebben we geïmplementeerd in de broncode van Consul/View Solver. Dit hield in dat we de rekenkern van het programma vervangen hebben door een nieuwe rekenkern, die nauwkeuriger en efficiënter opereert dan de oude rekenkern en die bovendien een groter scala aan systeemmodellen aankan.

Zowel de eerder genoemde exact- en nauwkeurigheidsverificatie van de ontwikkelde algoritmen als een uitvoerige verificatie van de nauwkeurigheid van het vernieuwde Consul/View Solver leverde bevredigende resultaten op. Hierdoor kunnen we concluderen dat de door ons vervaardigde nieuwe rekenkern met een gerust hart opgenomen kan worden in de eerstvolgende versie van Consul/View Solver.

Deelnemer: Oussama Chemlal
Titel scriptie: Application of time series analysis to speech enhancement using the EM algorithm

In this thesis, we consider speech enhancement using the Expectation Maximization (EM) algorithm. This algorithm allows us to estimate parameters of the speech and the noise which are supposed to follow Auto Regressive (AR) processes with unknown parameters. In the E-step of the EM algorithm, we use the Kalman filter-smoother to estimate the likelihood function of the unknown parameters, while in the M-step, we maximize this likelihood function to obtain an estimate of these parameters. Iterating between these two steps increases the likelihood function, and improves the estimated parameters, resulting in a filtered speech signal.

Gannot[1] has used the EM algorithm to reconstruct the clean speech signal from the noisy one. However, the method proposed by Gannot was not complete due to some problems which arise in the two steps. One of the problems is the singularity of the covariance matrices which makes part of the E-step. The other problem arises in M-step where the parameters of the AR process have to be updated. This problems are analysed and solved in this thesis.

The EM algorithm has given good results for speech enhancement when the speech is assumed to be AR(10), and the noise is a simulated AR(q) process. The problem arising in this case is that of the reversibility, which means that the estimated speech signal corresponds sometimes to the original AR(q) process and the estimated AR(q) signal corresponds to the speech signal. This problem can be solved by puting an extra parameter (detector) to indicate if it is the speech or the noise.

We have tested the EM algorithm constructed from the clean speech and a noise coming from a PC fan, where the noise is assumed to be AR(4). In this case, the estimated signals do not agree with the original signals. The diagnostic model for the noise has shown that the assumption that the noise is an AR(4) may be rejected. To solve this problem, one must formulate a good model for the noise signal, and based on this model, derive another EM algorithm to cancel this noise.

[1] S. Gannot, D. Burstein and E. Weinstein: Iterative and Sequential Kalman Filter-based Speech Enhancement Algorithms.

Deelnemer: Blazenka Cickaric
Titel scriptie: Sampling techniques for auditing the European finances

In order to give an independent opinion on the reliability of the European accounts the European Court of Auditors have to check on the legality and regularity of the transactions underlying the EC accounts. The complexity of the audit of European payments is caused by complex, multilevel administrative organization these payments are flowing through. Not only the operations at the level of the Commission have to be audited, but every subsequent level, as money is transferred to national governments and to other public authorities on its way to the final beneficiaries.

The statistical sampling technique known as Monetary unit sampling is applied to identify individual monetary units that will identify at each level in the population the transactions to be audited. From the sample audit evidence the error fraction in the population has been estimated by the so called "taint estimator" as well as the "Stringer bound" , a widely used nonparametric confidence bound that seems to be conservative (i.e. it overestimates actual risk)

A review of the present methodology for taking and auditing a sample of the European finances was the initial task of the project. Concluding that the methods presently used tend to underestimate the total error volume in the population a model has been proposed for combining the possible multiple errors found within an account at the different levels. The model seems to provide a valid Monetary Unit Sample and therefore valid estimators.

Further, the possibility of applying two-stage sample has been discussed. By auditing some regions more intensively a better control over geographical dispersion of the sample would be gained, which would lead to reducing in auditing costs in comparison to simple random sampling. Discussion includes how intensive the sampling and subsampling should be to obtain an estimator at least as precise as the estimator with simple random sampling.

The paper considers also the possibility of comparing different audit areas (domains) such as budget lines or Member States. By using large sample theory we evaluate the global sample size needed from which we would be able to declare the discovered difference in two domains significantly different from zero.

Deelnemer: Teus Jakobs
Titel scriptie: Neurale netwerken en korte termijn voorspellingen voor het drinkwaterverbruik

Ieder waterleidingbedrijf zal streven naar het afleveren van drinkwater van de hoogst mogelijke kwaliteit. Tevens zal het streven zijn dat men steeds over voldoende drinkwater beschikt om aan de vraag te kunnen voldoen. Omdat de kwaliteit van het water echter gebaat is bij een gelijkmatig productieproces, is een goede korte termijn voorspelling van het drinkwaterverbruik van essentieel belang. Omdat de tot nu toe gemaakte voorspellingsmodellen met de Box-Jenkins methode niet altijd even nauwkeurig waren, wordt gezocht naar een methode met een grotere voorspelkracht. Het vermoeden bestaat dat een Neuraal Netwerk een serieuze optie is om de Box-Jenkins modellen te vervangen.

Doel van dit onderzoek is dan ook om een vergelijking te maken tussen de voorspelkracht van een Neuraal Netwerk en de voorspelkracht van een Box-Jenkins model. In dit verslag zijn een paar, reeds bestaande, Box-Jenkins modellen vergeleken met nieuw gebouwde Neurale Netwerken om een uitspraak te kunnen doen over de voorspelkracht van beide methoden.

In de gebruikte modellen wordt gewerkt met een voorspelperiode van 1 dag. Om een zo eerlijk mogelijke vergelijking te maken, worden voor de twee methoden iedere keer dezelfde hoeveelheid gegevens en dezelfde variabelen gebruikt.

Na de vergelijking van de (statistische) resultaten van de twee methoden op de modellen, kan geconcludeerd worden dan een Neuraal Netwerk, zelfs bij zo weinig gegevens als die voor deze modellen bekend waren, inderdaad een grotere voorspelkracht heeft dan een Box-Jenkins model met dezelfde gegevens en variabelen. Dit verschil in voorspelkracht komt tot uiting in de gemiddelde absolute fout die wordt gemaakt. Deze fout ligt bij een Neuraal Netwerk gemiddeld 0.4% lager dan de gemiddelde absolute fout van een Box-Jenkins model. Ook in de voorspelling van de piekdagen is het Neurale Netwerk sterker, waar het de twee methodes op de daldagen vrijwel gelijk zijn.

Daarom kan ook worden aangeraden, wanneer de keus moet worden gemaakt welke methode te gebruiken voor een korte termijn voorspelling van het drinkwaterverbruik, een Neuraal Netwerk te verkiezen boven een Box-Jenkins model.

Deelnemer: Laurens van de Laar
Titel scriptie: A real-life pickup and delivery problem with multiple depots: from model to solution strategy

In this thesis a real-life container transportation problem is tackled, where trains and trucks are available to transport containers between freight centres. The problem is to find a minimum cost planning that meets the various demands that characterize a real-life problem. The cost is mainly decided by the number of kilometres that are driven by truck. Gathering information from a team of CQM-consultants that have been working on the same assignment, we have drawn up the functional specifications of the problem. Consequently we have built a mathematical model of the pick up and delivery problem with multiple depots, which is fit for the container transportation problem.

Based on the mathematical model we have started the search for a solution strategy from scratch. We have presented some interesting results on ways to solve parts of the problem. Since the transportation of containers is not equally distributed over the freight centres, empty containers must be driven to restore the balance. Using a network flow algorithm we have solved this problem effectively. Another aspect of the problem is that at the same time the routes that trucks drive to pick up and deliver containers and the departure times and arrival times at freight centres have to be computed. Using linear programming techniques we demonstrate how the departure times and arrival times are determined efficiently when all other decision variables are known. Based on characteristics of the problem and knowledge of solutions to related problems we have decomposed the problem into six subproblems. We have chosen to develop a solution to one subproblem, with concise demystification of the other components.

The subproblem that we solve is called the trip-length reduction problem. This is the problem to find trips with a capacity of two containers, such that all containers are picked up and delivered, minimal to the number of kilometres that are driven. The size and the complexity of the problem have made us decide to apply a local search solution strategy. A lot of effort is put into defining operators that create a new solution from an old one, in order to find improvement. To begin with the matching operator is defined that allows us to combine trips that are not yet loaded up to their capacity, such that more favourable trips are created. A discussion on the possibility to tranship containers from one trip to the other has resulted in the idea to also define the compound matching operator, that is, though rather complex, well-applicable in many cases.

Furthermore we introduce a clever cost function to guide the search and we apply neighbourhood reduction techniques to reduce the computation time of the algorithm. From the search for ways to escape from local optima we have developed a very interesting variation of the variable depth method, the so-called filtered variable depth method. This method uses knowledge of precedence conditions on transitions to determine from a sequence of transitions the best subset of transitions that can be performed. The problem to find such a subset, the transition filtering problem, is solved, again using a network flow algorithm.

At short notice further improvement on the solution strategy that we have developed will involve solving the other steps of the decomposition and validating the results. Because many problem-specific characteristics have lead to this solution strategy, it is not applicable to a wide range of problems. We do think however that solutions to several parts of the problem may very well be applied to other problems.

Deelnemer: Belinda Smeenk
Titel scriptie: De optimale sensormix

Het verkrijgen van inlichtingen is een essentieel onderdeel van de hedendaagse oorlogsvoering. Een belangrijk deel van de inlichtingen wordt gebaseerd op waarnemingen met behulp van sensoren, zoals radars en infrarood apparatuur. Mede door technologische ontwikkelingen is er een grote hoeveelheid aan sensoren beschikbaar, waardoor het vinden van de meest efficiënte inzet van sensoren steeds moeilijker wordt. Bij de sensorinzet is het niet alleen belangrijk welke sensoren het best ingezet kunnen worden, maar daarnaast ook in welke volgorde dit dient te gebeuren.

De beschikbare kennis op een bepaald moment wordt weergegeven in de vorm van een vector. De inzet van een sensor moet leiden tot meer kennis en is gemodelleerd als een vermenigvuldiging met een overgangsmatrix. Vooraf aan dit onderzoek was het mogelijk handmatig inzetvolgordes te definiëren en met elkaar te vergelijken.

Een optimalisatieslag waarmee snel de optimale inzetvolgorde bepaald kan worden, was niet voorhanden. In dit onderzoek is gezocht naar snelle optimale methoden en heuristieken voor dit optimaliseringsprobleem.

Het onderzoek is opgedeeld in vier fasen waarbij in iedere fase het probleem verder uitgebreid wordt. De eerste fase behandeld het probleem met N achter elkaar in te zetten sensoren, waarbij over één kenmerk van de vijandelijke eenheden zoveel mogelijk informatie verkregen dient te worden. In de tweede fase wordt dit uitgebreid naar drie kenmerken. Vervolgens wordt in de derde fase een tijdsrestrictie toegevoegd. In de laatste fase wordt een optimaal schema gezocht waarbij sensoren aan verschillende opdrachten toegewezen kunnen worden, zodanig dat het totaalresultaat aan informatie zo groot mogelijk is.

Deelnemer: Alwin Stegeman
Titel scriptie: Modeling traffic in high-speed networks by ON/OFF models

Anyone who has experience with computer networks knows that system crashes occur quite often. In order to increase the performance of the network, efforts have been put into the understanding of the traffic or workload (i.e. bytes per time unit) in computer networks. Empirical studies of the workload in computer networks have shown that the workload process exhibits long memory (long-range dependence) and that the cumulative workload process is self-similar. To understand why this is the case, theoretical models have been developed, describing the traffic in computer networks.

One class of these models are so-called ON/OFF models. In an ON/OFF model a computer network is represented by a number of so-called ON/OFF sources. An ON/OFF source can be compared with a fileserver: it sends data through the network if it is ON and remains silent if it is OFF. The lengths of the ON- and OFF-periods are stochastic.

The ON/OFF model is used to give an explanation for the empirically observed long memory and self-similarity. This is done by obtaining convergence results for the cumulative workload process. This approach is not totally convincing, however, since by choosing different limit regimes, different limiting processes can be obtained. Some limiting processes do not exhibit long memory. Therefore, the ON/OFF model does not give an unambiguous explanation for the empirically observed phenomena.

Deelnemer: Marten Klok
Titel scriptie:
Comparison of CDMA-approximation techniques

Wideband Code Division Multiple Access (W-CDMA) has been selected as the European candidate for the third generation radio interface of the Universal Mobile Telecommunication System (UMTS). The main difference between GSM (Global System for Mobile communications) and CDMA is the way multiple (binary) signals are transmitted. In a GSM-system all signal-bits are transmitted after each other, that is first the i-th bit of all users are transmitted after each other, then the (i+1)-th bit and so on. In a CDMA-system bits of different users are divided by an almost orthogonal code, which is a (pseudo-)random sequence of independent (+1,-1) Bernoulli(1/2) variables. In this thesis only CDMA-systems are investigated.

Major cause of transmission impairments is multiple access interference, caused by the non-orthogonality of the interfering codes. This leads in rare occasions to bit-errors, i.e. the estimated bit differs from the original bit. It is very important to know, or at least approximate this bit-error-rate.

This thesis starts with a precise description and evaluation of the used model. Then four existing approximation techniques and a novel technique are compared for different scenarios. Included are a system with additive white Gaussian noise, imperfect powercontrol and fading channel. Where possible, conclusions are given of the accuracy of the different approximations.

 

05-04-2000

  Info: