131 |
Representative Subsets for Preference QueriesChester, Sean 26 August 2013 (has links)
We focus on the two overlapping areas of preference queries and dataset summarization. A (linear) preference query specifies the relative importance of the attributes in a dataset and asks for the tuples that best match those preferences. Dataset summarization is the task of representing an entire dataset by a small, representative subset. Within these areas, we focus on three important sub-problems, significantly advancing the state-of-the-art in each.
We begin with an investigation into a new formulation of preference queries, identifying a neglected and important subclass that we call threshold projection queries. While literature typically constrains the attribute preferences (which are real-valued weights) such that their sum is one, we show that this introduces bias when querying by threshold rather than cardinality. Using projection, rather than inner product as in that literature, removes the bias. We then give algorithms for building and querying indices for this class of query, based, in the general case, on geometric duality and halfspace range searching, and, in an important special case, on stereographic projection.
In the second part of the dissertation, we investigate the monochromatic reverse top-k
(mRTOP) query in two dimensions. A mRTOP query asks for, given a tuple and a dataset,
the linear preference queries on the dataset that will include the given tuple. Towards this goal, we consider the novel scenario of building an index to support mRTOP queries, using geometric duality and plane sweep. We show theoretically and empirically that the index is quick to build, small on disk, and very efficient at answering mRTOP queries. As a corollary to these efforts, we defined the top-k rank contour, which encodes the k-ranked tuple for every possible linear preference query. This is tremendously useful in answering mRTOP queries, but also, we posit, of significant independent interest for its relation to myriad related linear preference query problems. Intuitively, the top-k rank contour is the minimum possible representation of knowledge needed to identify the k-ranked tuple for any query, without apriori knowledge of that query.
We also introduce k-regret minimizing sets, a very succinct approximation of a numeric
dataset. The purpose of the approximation is to represent the entire dataset by just a small subset that nonetheless will contain a tuple within or near to the top-k for any linear preference query. We show that the problem of finding k-regret minimizing sets—and, indeed, the problem in literature that it generalizes—is NP-Hard. Still, for the special case of two dimensions, we provide a fast, exact algorithm based on the top-k rank contour. For arbitrary dimension, we introduce a novel greedy algorithm based on linear programming and randomization that does excellently in our empirical investigation. / Graduate / 0984
|
132 |
On the Value of Prediction and Feedback for Online Decision Making With Switching CostsMing Shi (12621637) 01 June 2022 (has links)
<p>Online decision making with switching costs has received considerable attention in many practical problems that face uncertainty in the inputs and key problem parameters. Because of the switching costs that penalize the change of decisions, making good online decisions under such uncertainty is known to be extremely challenging. This thesis aims at providing new online algorithms with strong performance guarantees to address this challenge.</p>
<p><br></p>
<p>In part 1 and part 2 of this thesis, motivated by Network Functions Virtualization and smart grid, we study competitive online convex optimization with switching costs. Specifically, in part 1, we focus on the setting with an uncertainty set (one type of prediction) and hard infeasibility constraints. We develop new online algorithms that can attain optimized competitive ratios, while ensuring feasibility at all times. Moreover, we design a robustification procedure that helps these algorithms obtain good average-case performance simultaneously. In part 2, we focus on the setting with look-ahead (another type of prediction). We provide the first algorithm that attains a competitive ratio that not only decreases to 1 as the look-ahead window size increases, but also remains upper-bounded for any ratio between the switching-cost coefficient and service-cost coefficient.</p>
<p><br></p>
<p>In part 3 of this thesis, motivated by edge computing with artificial intelligence, we study bandit learning with switching costs where, in addition to bandit feedback, full feedback can be requested at a cost. We show that, when only 1 arm can be chosen at a time, adding costly full-feedback is not helpful in fundamentally reducing the Θ(<em>T</em>2/3) regret over a time-horizon <em>T</em>. In contrast, when 2 (or more) arms can be chosen at a time, we provide a new online learning algorithm that achieves a significantly smaller regret equal to <em>O</em>(√<em>T</em>), without even using full feedback. To the best of our knowledge, this type of sharp transition from choosing 1 arm to choosing 2 (or more) arms has never been reported in the literature.</p>
|
133 |
Trestný čin zkrácení daně, poplatku a podobné povinné platby / Evasion of taxes, fees and other mandatory paymentsTöglová, Markéta January 2021 (has links)
This thesis describes the most commonly committed tax criminal offense i.e., the evasion of taxes, fees, and other mandatory payments pursuant to Section 240 of the Criminal Code. The goal of the thesis is to examine the problematic aspects of this criminal offense and to call attention to the discrepancies in proceedings and judgements, with special attention to substantive and procedural aspect, relevant case law of the domestic courts, and the opinion of professional public. The body of the thesis is divided into five chapters. The first two chapters introduce the substantive basis of the topic, provide a brief overview of the history of tax crimes and, last but not least, underline the importance and relevance of the whole topic using publicly available statistical data. The third chapter is focused on the mutual connection between the criminal offense pursuant to Section 240 of the Criminal Code and two selected criminal offenses. The first being the non-payment of taxes, social security contributions and similar mandatory payments pursuant to Section 241 of the Criminal Code, with a focus on the role of effective regret. Among other things, this outlines the issue following the unprecedented judgment of the Constitutional Court of the Czech Republic concerning the voluntary action of the...
|
134 |
Studies on the Space Exploration and the Sink Location under Incomplete Information towards Applications to Evacuation Planning / 不完全情報下における空間探索及び施設配置に関する理論的研究 -避難計画への応用を目指して-Higashikawa, Yuya 24 September 2014 (has links)
京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第18582号 / 工博第3943号 / 新制||工||1606(附属図書館) / 31482 / 京都大学大学院工学研究科建築学専攻 / (主査)教授 加藤 直樹, 教授 門内 輝行, 教授 神吉 紀世子 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM
|
135 |
Algorithmic Study on Prediction with Expert Advice : Study of 3 novel paradigms with Grouped ExpertsCayuela Rafols, Marc January 2018 (has links)
The main work for this thesis has been a thorough study of the novel Prediction with Partially Monitored Grouped Expert Advice and Side Information paradigm. This is newly proposed in this thesis, and it extends the widely studied Prediction with Expert Advice paradigm. The extension is based on two assumptions and one restriction that modify the original problem. The first assumption, Grouped, presumes that the experts are structured into groups. The second assumption, Side Information, introduces additional information that can be used to timely relate predictions with groups. Finally, the restriction, Partially Monitored, imposes that the groups’ predictions are only known for one group at a time. The study of this paradigm includes the design of a complete prediction algorithm, the proof of a theoretical bound of the worse-case cumulative regret for such algorithm, and an experimental evaluation of the algorithm (proving the existence of cases where this paradigm outperforms Prediction with Expert Advice). Furthermore, since the development of the algorithm is constructive, it allows to easily build two additional prediction algorithms for the Prediction with Grouped Expert Advice and Prediction with Grouped Expert Advice and Side Information paradigms. Therefore, this thesis presents three novel prediction algorithms, with corresponding regret bounds, and a comparative experimental evaluation including the original Prediction with Expert Advice paradigm. / Huvudarbetet för den här avhandlingen har varit en grundlig studie av den nya Prediction with Partially Monitored Grouped Expert Advice and Side Information paradigmet. Detta är nyligen föreslagit i denna avhandling, och det utökar det brett studerade Prediction with Expert Advice paradigmet. Förlängningen baseras på två antaganden och en begränsning som ändrar det ursprungliga problemet. Det första antagandet, Grouped, förutsätter att experterna är inbyggda i grupper. Det andra antagandet, Side Information, introducerar ytterligare information som kan användas för att i tid relatera förutsägelser med grupper. Slutligen innebär begränsningen, Partially Monitored, att gruppens förutsägelser endast är kända för en grupp i taget. Studien av detta paradigm innefattar utformningen av en komplett förutsägelsesalgoritm, beviset på en teoretisk bindning till det sämre fallet kumulativa ånger för en sådan algoritm och en experimentell utvärdering av algoritmen (bevisar förekomsten av fall där detta paradigm överträffar Prediction with Expert Advice). Eftersom algoritmens utveckling är konstruktiv tillåter den dessutom att enkelt bygga två ytterligare prediksionsalgoritmer för Prediction with Grouped Expert Advice och Prediction with Grouped Expert Advice and Side Information paradigmer. Därför presenterar denna avhandling tre nya prediktionsalgoritmer med motsvarande ångergränser och en jämförande experimentell utvärdering inklusive det ursprungliga Prediction with Expert Advice paradigmet.
|
136 |
Advanced signal processing techniques for multi-target trackingDaniyan, Abdullahi January 2018 (has links)
The multi-target tracking problem essentially involves the recursive joint estimation of the state of unknown and time-varying number of targets present in a tracking scene, given a series of observations. This problem becomes more challenging because the sequence of observations is noisy and can become corrupted due to miss-detections and false alarms/clutter. Additionally, the detected observations are indistinguishable from clutter. Furthermore, whether the target(s) of interest are point or extended (in terms of spatial extent) poses even more technical challenges. An approach known as random finite sets provides an elegant and rigorous framework for the handling of the multi-target tracking problem. With a random finite sets formulation, both the multi-target states and multi-target observations are modelled as finite set valued random variables, that is, random variables which are random in both the number of elements and the values of the elements themselves. Furthermore, compared to other approaches, the random finite sets approach possesses a desirable characteristic of being free of explicit data association prior to tracking. In addition, a framework is available for dealing with random finite sets and is known as finite sets statistics. In this thesis, advanced signal processing techniques are employed to provide enhancements to and develop new random finite sets based multi-target tracking algorithms for the tracking of both point and extended targets with the aim to improve tracking performance in cluttered environments. To this end, firstly, a new and efficient Kalman-gain aided sequential Monte Carlo probability hypothesis density (KG-SMC-PHD) filter and a cardinalised particle probability hypothesis density (KG-SMC-CPHD) filter are proposed. These filters employ the Kalman- gain approach during weight update to correct predicted particle states by minimising the mean square error between the estimated measurement and the actual measurement received at a given time in order to arrive at a more accurate posterior. This technique identifies and selects those particles belonging to a particular target from a given PHD for state correction during weight computation. The proposed SMC-CPHD filter provides a better estimate of the number of targets. Besides the improved tracking accuracy, fewer particles are required in the proposed approach. Simulation results confirm the improved tracking performance when evaluated with different measures. Secondly, the KG-SMC-(C)PHD filters are particle filter (PF) based and as with PFs, they require a process known as resampling to avoid the problem of degeneracy. This thesis proposes a new resampling scheme to address a problem with the systematic resampling method which causes a high tendency of resampling very low weight particles especially when a large number of resampled particles are required; which in turn affect state estimation. Thirdly, the KG-SMC-(C)PHD filters proposed in this thesis perform filtering and not tracking , that is, they provide only point estimates of target states but do not provide connected estimates of target trajectories from one time step to the next. A new post processing step using game theory as a solution to this filtering - tracking problem is proposed. This approach was named the GTDA method. This method was employed in the KG-SMC-(C)PHD filter as a post processing technique and was evaluated using both simulated and real data obtained using the NI-USRP software defined radio platform in a passive bi-static radar system. Lastly, a new technique for the joint tracking and labelling of multiple extended targets is proposed. To achieve multiple extended target tracking using this technique, models for the target measurement rate, kinematic component and target extension are defined and jointly propagated in time under the generalised labelled multi-Bernoulli (GLMB) filter framework. The GLMB filter is a random finite sets-based filter. In particular, a Poisson mixture variational Bayesian (PMVB) model is developed to simultaneously estimate the measurement rate of multiple extended targets and extended target extension was modelled using B-splines. The proposed method was evaluated with various performance metrics in order to demonstrate its effectiveness in tracking multiple extended targets.
|
137 |
Stratégies optimistes en apprentissage par renforcementFilippi, Sarah 24 November 2010 (has links) (PDF)
Cette thèse traite de méthodes « model-based » pour résoudre des problèmes d'apprentissage par renforcement. On considère un agent confronté à une suite de décisions et un environnement dont l'état varie selon les décisions prises par l'agent. Ce dernier reçoit tout au long de l'interaction des récompenses qui dépendent à la fois de l'action prise et de l'état de l'environnement. L'agent ne connaît pas le modèle d'interaction et a pour but de maximiser la somme des récompenses reçues à long terme. Nous considérons différents modèles d'interactions : les processus de décisions markoviens, les processus de décisions markoviens partiellement observés et les modèles de bandits. Pour ces différents modèles, nous proposons des algorithmes qui consistent à construire à chaque instant un ensemble de modèles permettant d'expliquer au mieux l'interaction entre l'agent et l'environnement. Les méthodes dites « model-based » que nous élaborons se veulent performantes tant en pratique que d'un point de vue théorique. La performance théorique des algorithmes est calculée en terme de regret qui mesure la différence entre la somme des récompenses reçues par un agent qui connaîtrait à l'avance le modèle d'interaction et celle des récompenses cumulées par l'algorithme. En particulier, ces algorithmes garantissent un bon équilibre entre l'acquisition de nouvelles connaissances sur la réaction de l'environnement (exploration) et le choix d'actions qui semblent mener à de fortes récompenses (exploitation). Nous proposons deux types de méthodes différentes pour contrôler ce compromis entre exploration et exploitation. Le premier algorithme proposé dans cette thèse consiste à suivre successivement une stratégie d'exploration, durant laquelle le modèle d'interaction est estimé, puis une stratégie d'exploitation. La durée de la phase d'exploration est contrôlée de manière adaptative ce qui permet d'obtenir un regret logarithmique dans un processus de décision markovien paramétrique même si l'état de l'environnement n'est que partiellement observé. Ce type de modèle est motivé par une application d'intérêt en radio cognitive qu'est l'accès opportuniste à un réseau de communication par un utilisateur secondaire. Les deux autres algorithmes proposés suivent des stratégies optimistes : l'agent choisit les actions optimales pour le meilleur des modèles possibles parmi l'ensemble des modèles vraisemblables. Nous construisons et analysons un tel algorithme pour un modèle de bandit paramétrique dans un cas de modèles linéaires généralisés permettant ainsi de considérer des applications telles que la gestion de publicité sur internet. Nous proposons également d'utiliser la divergence de Kullback-Leibler pour la construction de l'ensemble des modèles vraisemblables dans des algorithmes optimistes pour des processus de décision markoviens à espaces d'états et d'actions finis. L'utilisation de cette métrique améliore significativement le comportement de des algorithmes optimistes en pratique. De plus, une analyse du regret de chacun des algorithmes permet de garantir des performances théoriques similaires aux meilleurs algorithmes de l'état de l'art.
|
138 |
Choice deferral, status quo bias, and matchingButurak, Gökhan January 2011 (has links)
This thesis consists of three independent papers. They are put in reverse chronological order according to when they were initiated. The first paper, which is a joint work with Özgür Evren, extends the standard rational choice framework with the option to postpone the act of selecting an alternative. In that paper, we propose an axiomatic model of choice over risky prospects that restricts the classical rationality axioms solely to those instances in which the decision maker does not defer. The cardinal approach we follow allows us to identify the preference relation of the decision maker over lotteries, even if the choice data is very scarce due to deferral. Moreover, we also derive the value of deferring choice from a given set of options, which turns out to be an affine utility function over choice sets. At each choice situation, the decision maker compares the utility of each available alternative with that of deferral so as to decide on opting for an alternative immediately. The second paper is a model of status quo bias with choice avoidance. It describes the choice behavior of an otherwise standard decision maker whose choices are affected by the presence of a status quo alternative. The status quo emerges as a temporary choice, which may be reversed upon arrival of new (introspective or objective) information, or upon finding new alternatives. The third paper considers the network formation problem from a matching perspective. In that paper, agents want to link with each other and each has preferences over the subsets of others. We consider various solution concepts regarding the stability of a matching between the agents, establish relations between these concepts under several preference restrictions, and provide sufficient conditions for these solutions to be nonempty. / Diss. Stockholm : Handelshögskolan i Stockholm, 2011
|
139 |
The subprime mortgage crisis : asset securitization and interbank lending / M.P. MulaudziMulaudzi, Mmboniseni Phanuel January 2009 (has links)
Subprime residential mortgage loan securitization and its associated risks have been a major topic of discussion since the onset of the subprime mortgage crisis (SMC) in 2007. In this regard, the thesis addresses the issues of subprime residential mortgage loan (RML) securitization in discrete-, continuous-and discontinuous-time and their connections with the SMC. In this regard, the main issues to be addressed are discussed in Chapters 2, 3 and 4.
In Chapter 2, we investigate the risk allocation choices of an investing bank (IB) that has to decide between risky securitized subprime RMLs and riskless Treasuries. This issue is discussed in a discrete-time framework with IB being considered to be regret- and risk-averse before and during the SMC, respectively. We conclude that if IB takes regret into account it will be exposed to higher risk when the difference between the expected returns on securitized subprime RMLs and Treasuries is small. However, there is low risk exposure when this difference is high. Furthermore, we assess how regret can influence IB's view - as a swap protection buyer - of the rate of return on credit default swaps (CDSs), as measured by the premium based on default swap spreads. We find that before the SMC, regret increases IB's willingness to pay lower premiums for CDSs when its securitized RML portfolio is considered to be safe. On the other hand, both risk- and regret-averse IBs pay the same CDS premium when their securitized RML portfolio is considered to be risky.
Chapter 3 solves a stochastic optimal credit default insurance problem in continuous-time that has the cash outflow rate for satisfying depositor obligations, the investment in securitized loans and credit default insurance as controls. As far as the latter is concerned, we compute the credit default swap premium and accrued premium by considering the credit rating of the securitized mortgage loans.
In Chapter 4, we consider a problem of IB investment in subprime residential mortgage-backed securities (RMBSs) and Treasuries in discontinuous-time. In order to accomplish this, we develop a Levy process-based model of jump diffusion-type for IB's investment in subprime RMBSs and Treasuries. This model incorporates subprime RMBS losses which can be associated with credit risk. Furthermore, we use variance to measure such risk, and assume that the risk is bounded by a certain constraint. We are now able to set-up a mean-variance optimization problem for IB's investment which determines the optimal proportion of funds that needs to be invested in subprime RMBSs and Treasuries subject to credit risk measured by the variance of IE's investment. In the sequel, we also consider a mean swaps-at-risk (SaR) optimization problem for IB's investment which determines the optimal portfolio which consists of subprime RMBSs and Treasuries subject to the protection by CDSs required against the possible losses. In this regard, we define SaR as indicative to IB on how much protection from swap protection seller it must have in order to cover the losses that might occur from credit events. Moreover, SaR is expressed in terms of Value-at-Risk (VaR).
Finally, Chapter 5 provides an analysis of discrete-, continuous- and discontinuous-time models for subprime RML securitization discussed in the aforementioned chapters and their connections with the SMC.
The work presented in this thesis is based on 7 peer-reviewed international journal articles (see [25], [44], [45], [46], [47], [48] and [55]), 4 peer-reviewed chapters in books (see [42], [50j, [51J and [52]) and 2 peer-reviewed conference proceedings papers (see [11] and [12]). Moreover, the article [49] is currently being prepared for submission to an lSI accredited journal. / Thesis (Ph.D. (Applied Mathematics))--North-West University, Potchefstroom Campus, 2010.
|
140 |
The subprime mortgage crisis : asset securitization and interbank lending / M.P. MulaudziMulaudzi, Mmboniseni Phanuel January 2009 (has links)
Subprime residential mortgage loan securitization and its associated risks have been a major topic of discussion since the onset of the subprime mortgage crisis (SMC) in 2007. In this regard, the thesis addresses the issues of subprime residential mortgage loan (RML) securitization in discrete-, continuous-and discontinuous-time and their connections with the SMC. In this regard, the main issues to be addressed are discussed in Chapters 2, 3 and 4.
In Chapter 2, we investigate the risk allocation choices of an investing bank (IB) that has to decide between risky securitized subprime RMLs and riskless Treasuries. This issue is discussed in a discrete-time framework with IB being considered to be regret- and risk-averse before and during the SMC, respectively. We conclude that if IB takes regret into account it will be exposed to higher risk when the difference between the expected returns on securitized subprime RMLs and Treasuries is small. However, there is low risk exposure when this difference is high. Furthermore, we assess how regret can influence IB's view - as a swap protection buyer - of the rate of return on credit default swaps (CDSs), as measured by the premium based on default swap spreads. We find that before the SMC, regret increases IB's willingness to pay lower premiums for CDSs when its securitized RML portfolio is considered to be safe. On the other hand, both risk- and regret-averse IBs pay the same CDS premium when their securitized RML portfolio is considered to be risky.
Chapter 3 solves a stochastic optimal credit default insurance problem in continuous-time that has the cash outflow rate for satisfying depositor obligations, the investment in securitized loans and credit default insurance as controls. As far as the latter is concerned, we compute the credit default swap premium and accrued premium by considering the credit rating of the securitized mortgage loans.
In Chapter 4, we consider a problem of IB investment in subprime residential mortgage-backed securities (RMBSs) and Treasuries in discontinuous-time. In order to accomplish this, we develop a Levy process-based model of jump diffusion-type for IB's investment in subprime RMBSs and Treasuries. This model incorporates subprime RMBS losses which can be associated with credit risk. Furthermore, we use variance to measure such risk, and assume that the risk is bounded by a certain constraint. We are now able to set-up a mean-variance optimization problem for IB's investment which determines the optimal proportion of funds that needs to be invested in subprime RMBSs and Treasuries subject to credit risk measured by the variance of IE's investment. In the sequel, we also consider a mean swaps-at-risk (SaR) optimization problem for IB's investment which determines the optimal portfolio which consists of subprime RMBSs and Treasuries subject to the protection by CDSs required against the possible losses. In this regard, we define SaR as indicative to IB on how much protection from swap protection seller it must have in order to cover the losses that might occur from credit events. Moreover, SaR is expressed in terms of Value-at-Risk (VaR).
Finally, Chapter 5 provides an analysis of discrete-, continuous- and discontinuous-time models for subprime RML securitization discussed in the aforementioned chapters and their connections with the SMC.
The work presented in this thesis is based on 7 peer-reviewed international journal articles (see [25], [44], [45], [46], [47], [48] and [55]), 4 peer-reviewed chapters in books (see [42], [50j, [51J and [52]) and 2 peer-reviewed conference proceedings papers (see [11] and [12]). Moreover, the article [49] is currently being prepared for submission to an lSI accredited journal. / Thesis (Ph.D. (Applied Mathematics))--North-West University, Potchefstroom Campus, 2010.
|
Page generated in 0.0274 seconds