11 |
Intractability Results for some Computational ProblemsPonnuswami, Ashok Kumar 08 July 2008 (has links)
In this thesis, we show results for some well-studied problems from learning theory and combinatorial optimization.
Learning Parities under the Uniform Distribution: We study the learnability of parities in the agnostic learning framework of Haussler and Kearns et al. We show that under the uniform distribution, agnostically learning parities reduces to learning parities with random classification noise, commonly referred to as the noisy parity problem. Together with the parity learning algorithm of Blum et al, this gives the first nontrivial algorithm for agnostic learning of parities. We use similar techniques to reduce learning of two other fundamental concept classes under the uniform distribution to learning of noisy parities. Namely, we show that learning of DNF expressions reduces to learning noisy parities of just logarithmic number of variables and learning of k-juntas reduces to learning noisy parities of k variables.
Agnostic Learning of Halfspaces: We give an essentially optimal hardness result for agnostic learning of halfspaces over rationals. We show that for any constant ε finding a halfspace that agrees with an unknown function on 1/2+ε fraction of examples is NP-hard even when there exists a halfspace that agrees with the unknown function on 1-ε fraction of examples. This significantly improves on a number of previous hardness results for this problem. We extend the result to ε = 2[superscript-Ω(sqrt{log n})] assuming NP is not contained in DTIME(2[superscript(log n)O(1)]). Majorities of Halfspaces: We show that majorities of halfspaces are hard to PAC-learn using any representation, based on the cryptographic assumption underlying the Ajtai-Dwork cryptosystem. This also implies a hardness result for learning halfspaces with a high rate of adversarial noise even if the learning algorithm can output any efficiently computable hypothesis. Max-Clique, Chromatic Number and Min-3Lin-Deletion: We prove an improved hardness of approximation result for two problems, namely, the problem of finding the size of the largest clique in a graph (also referred to as the Max-Clique problem) and the problem of finding the chromatic number of a graph. We show that for any constant γ > 0, there is no polynomial time algorithm that approximates these problems within factor n/2[superscript(log n)3/4+γ] in an n vertex graph, assuming NP is not contained in BPTIME(2[superscript(log n)O(1)]). This improves the hardness factor of n/2[superscript (log n)1-γ'] for some small (unspecified) constant γ' > 0 shown by Khot. Our main idea is to show an improved hardness result for the Min-3Lin-Deletion problem.
An instance of Min-3Lin-Deletion is a system of linear equations modulo 2, where each equation is over three variables. The objective is to find the minimum number of equations that need to be deleted so that the remaining system of equations has a satisfying assignment. We show a hardness factor of 2[superscript sqrt{log n}] for this problem, improving upon the hardness factor of (log n)[superscriptβ] shown by Hastad, for some small (unspecified) constant β > 0. The hardness results for Max-Clique and chromatic number are then obtained using the reduction from Min-3Lin-Deletion as given by Khot.
Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching: A monotone Boolean circuit is said to be multilinear if for any AND gate in the circuit, the minimal representation of the two input functions to the gate do not have any variable in common. We show that monotone multilinear Boolean circuits for computing bipartite perfect matching require exponential size. In fact we prove a stronger result by characterizing the structure of the smallest monotone multilinear Boolean circuits for the problem.
|
12 |
A Blind Constellation Agnostic VAE Channel Equalizer and Non Data-Assisted SynchronizationReinholdsen, Fredrik January 2021 (has links)
High performance and high bandwidth wireless digital communication underlies much of modern society. Due to its high value to society, new and improved digital communication technologies, allowing even higher speeds, better coverage, and lower latency are constantly being developed. The field of Machine Learning has exploded in recent years, showing incredible promise and performance at many tasks in a wide variety of fields. Channel Equalization and synchronization are critical parts of any wireless communication system, to ensure coherence between the transmitter and receiver, and to compensate for the often severe channel conditions. This study mainly explores the use of a Variational Autoencoder (VAE) architecture, presented in a previous study, for blind channel equalization without access to pilot symbols or ground-truth data. This thesis also presents a new, non data-assisted method of carrier frequency synchronization based around the k-means clustering algorithm. The main addition of this thesis however is a constellation agnostic implementation of the reference VAE architecture, for equalization of all rectangular QAM constellations. The approach significantly outperforms the traditional blind adaptive Constant Modulus algorithm (CMA) on all tested constellations and signal to noise ratios (SNRs), nearly equaling the performance of a non-blind Least Mean Squares (LMS) based Decision Feedback Equalizer (DFE).
|
13 |
Game-Agnostic Asset Loading Order Using Static Code AnalysisÅsbrink, Anton, Andersson, Jacob January 2022 (has links)
Background. User retention is important in the online sphere, especially within gaming. Utilising browser gaming websites to host games helps smaller studios and solo developers reach out to a larger audience. However, displaying games on the website does not guarantee the user will try the game out and if the load time is long, the player could potentially move on. Using game agnostic, static code analysis, a potential load order can be created, prioritising assets required to start the game to be downloaded first, resulting in shorter wait times for the player to start playing. Objectives. The thesis aim is to develop a game agnostic parser, able to a list all the assets within a given Godot engine based game and sort them according to importance. The order of importance is the assets required for the game to be playable is placed first, followed by each sequential set of assets for each sequential scene. Methods. Static code analysis is in this project done by parsing through all the files and code of a given game. By then using numerous regular expressions one can extract relevant data such as references to assets and scene changes. The assets are then associated with different scenes that are ordered and distinguished by scene changes. Results. The results vary from making no difference to potentially taking 31% of the original loading time. With graphs being generated for every game showing the scenes and their ordering through the parsing process giving information into the process of the game as well as the reasons for the potential speedup or the lack of it. Conclusions. The project shows promising results for games that can be successfully parsed and have the scene structure to gain from it. Further work and development is required for a more comprehensive solution with suggested methods. With these results being largely theoretical a more practical study would be needed to apply the results to a realistic setting. / Bakgrund. Bibehållande av användare är viktigt i den moderna internet sfären, merså inom spelande. Det är fördelaktigt för mindre spel och studios att ha sina spel på webbsidor som ger tillgång till en större användarbas. Det är dock ingen garanti att behålla en användare om ett spel tar för lång tid att ladda. Därav genom spelagnostisk, statisk kodanalys, kan en generera en laddnings ordning för spel resurser där de resurser som krävs för att starta spelet laddas ner först, vilket kan tillåta spelet att starta tidigare. Syfte. Målet är att kunna tolka spel kod för att lista resurserna för ett givet spelgjort i Godot motorn och sortera resurserna i ordningen de förekommer. Där de viktigaste resurserna är de som förekommer i de första scenerna som krävs för att starta spelet och sedan de följande scenen. Metod. Statisk kodanalys är att kolla på koden som den är utan att köras och görsi detta projekt genom att tolka all kod och dess filer. Detta genomförs med hjälp av regular expressions som tar den önskade datan som resurs referenser och indikationer om ändringar i scener. Resultat. Resultatet varierar att inte vara någon skillnad till basfallet till att ta 31% av den ursprungliga laddningstiden. Det visas av grafer skapad för varje spel som visar ordningen av scenerna och dess innehåll, vilket används för att utvärdera vad som gör vissa spel snabbare och varför vissa inte kan optimeras. Slutsatser. Projektet visar lovande resultat för de spel som kan bli optimerat utav programmet. Men för att få en generaliserad lösning krävs mer utveckling för att kunna täcka en större variation av spel. Dock då denna studie endast är teoretisk så behöver en praktiskt implementation göras för att applicera dessa resultat i en realistisk miljö.
|
14 |
Explainable AI methods for credit card fraud detection : Evaluation of LIME and SHAP through a User StudyJi, Yingchao January 2021 (has links)
In the past few years, Artificial Intelligence (AI) has evolved into a powerful tool applied in multi-disciplinary fields to resolve sophisticated problems. As AI becomes more powerful and ubiquitous, oftentimes the AI methods also become opaque, which might lead to trust issues for the users of the AI systems as well as fail to meet the legal requirements of AI transparency. In this report, the possibility of making a credit-card fraud detection support system explainable to users is investigated through a quantitative survey. A publicly available credit card dataset was used. Deep Learning and Random Forest were the two Machine Learning (ML) methodsimplemented and applied on the credit card fraud dataset, and the performance of their results was evaluated in terms of their accuracy, recall, sufficiency, and F1 score. After that, two explainable AI (XAI) methods - SHAP (Shapley Additive Explanations) and LIME (Local Interpretable Model-Agnostic Explanations) were implemented and applied to the results obtained from these two ML methods. Finally, the XAI results were evaluated through a quantitative survey. The results from the survey revealed that the XAI explanations can slightly increase the users' impression of the system's ability to reason and LIME had a slight advantage over SHAP in terms of explainability. Further investigation of visualizing data pre-processing and the training process is suggested to offer deep explanations for users.
|
15 |
The Faith Development of Clinical PsychologistsBlackburn, Tiana January 2017 (has links)
No description available.
|
16 |
Explainable AI techniques for sepsis diagnosis : Evaluating LIME and SHAP through a user studyNorrie, Christian January 2021 (has links)
Articial intelligence has had a large impact on many industries and transformed some domains quite radically. There is tremendous potential in applying AI to the eld of medical diagnostics. A major issue with applying these techniques to some domains is an inability for AI models to provide an explanation or justication for their predictions. This creates a problem wherein a user may not trust an AI prediction, or there are legal requirements for justifying decisions that are not met. This thesis overviews how two explainable AI techniques (Shapley Additive Explanations and Local Interpretable Model-Agnostic Explanations) can establish a degree of trust for the user in the medical diagnostics eld. These techniques are evaluated through a user study. User study results suggest that supplementing classications or predictions with a post-hoc visualization increases interpretability by a small margin. Further investigation and research utilizing a user study surveyor interview is suggested to increase interpretability and explainability of machine learning results.
|
17 |
Implementing Machine Learning in the Credit Process of a Learning Organization While Maintaining Transparency Using LIMEMalmberg, Jacob, Nystad Öhman, Marcus, Hotti, Alexandra January 2018 (has links)
To determine whether a credit limit for a corporate client should be changed, a financial institution writes a PM containingtext and financial data that then is assessed by a credit committee which decides whether to increase the limit or not. To make thisprocess more efficient, machine learning algorithms was used to classify the credit PMs instead of a committee. Since most machinelearning algorithms are black boxes, the LIME framework was used to find the most important features driving the classification. Theresults of this study show that credit memos can be classified with high accuracy and that LIME can be used to indicate which parts ofthe memo had the biggest impact. This implicates that the credit process could be improved by utilizing machine learning, whilemaintaining transparency. However, machine learning may disrupt learning processes within the organization. / För att bedöma om en kreditlimit för ett företag ska förändras eller inte skriver ett finansiellt institut ett PM innehållande text och finansiella data. Detta PM granskas sedan av en kreditkommitté som beslutar om limiten ska förändras eller inte. För att effektivisera denna process användes i denna rapport maskininlärning istället för en kreditkommitté för att besluta om limiten ska förändras. Eftersom de flesta maskininlärningsalgoritmer är svarta lådor så användes LIME-ramverket för att hitta de viktigaste drivarna bakom klassificeringen. Denna studies resultat visar att kredit-PM kan klassificeras med hög noggrannhet och att LIME kan visa vilken del av ett PM som hade störst påverkan vid klassificeringen. Implikationerna av detta är att kreditprocessen kan förbättras av maskininlärning, utan att förlora transparens. Maskininlärning kan emellertid störa lärandeprocesser i organisationen, varför införandet av dessa algoritmer bör vägas mot hur betydelsefullt det är att bevara och utveckla kunskap inom organisationen.
|
18 |
Performance Analysis of a Godot Game-Agnostic Streaming ToolAxelsson, Sam, Eriksson, Filip January 2023 (has links)
Background. Streaming games is traditionally done with video and audio both for watching on websites like Twitch and YouTube or playing via cloud gaming services. Streaming with video and audio requires good internet speeds to be of satisfactory quality therefore compression algorithms are used. Compression algorithms decrease bandwidth usage but it also lowers the quality of the stream. An alternative would be to stream game states and user inputs to recreate the game state for the viewer, this would lower the bandwidth usage while not compromising the quality. Objectives. This thesis aims to explore and compare a generalized streaming tool for the Godot engine. Where game states and user inputs are sent between two game instances to synchronize the host game with the client game. The tool will then be compared to a video and audio streaming setup in terms of image quality, bandwidth, and processing power. Methods. A combination of state replication and client simulation has been implemented for a streaming tool for games. Bandwidth, image quality, and processing power metrics are gathered for seven games for streaming with state replication and client simulation. The performance metrics have also been gathered when streaming video and audio data. To validate the streaming tool, the seven games were visually compared between images from the host and client of the streaming tool. Results. Compared to streaming video and audio data there was shown to be an overhead for streaming game states and user inputs. This overhead causes multiple games to have significant performance issues in terms of processing power for the CPU. In terms of image quality and bandwidth, the generalized streaming tool performed better. Conclusions. The results showed that there is a possibility for a generalized streaming tool for the Godot engine to be successfully implemented. The implementation of the Godot streaming tool didn't work perfectly for each tested game, but most games use less bandwidth and there's no quality loss regarding the image quality. However, the streaming tool requires better hardware than traditional video and audio streaming. / Bakgrund. Att strema spel är oftast gjord med ljud och bild på webbsidor som Twitch eller Youtube, det används också i cloud gaming. Att skicka ljud och bild via nätet kräver bra bandbredd, även när man minskar bandbredden genom existerande komprimerings algoritmer som påverkar kvalitén. Genom att skicka knapp-tryckningar och lägen av spelet, så kan spelläget återskapas hos tittaren och där med minska användning av bandbredden och kvalitén skulle inte bli påverkad. Syfte. Det här examensarbetet utforskar ett spel-agnostiskt streaming verktyg för Godot. Verktyget fungerar genom att skicka knapptryckningar och speldata från en host till en klient för att synkronisera klientens spel till att matcha hostens spel. Sen kommer data från verktyget och traditionell streaming samlas in för att jämföra skillnaden i bildkvalitet, bandbredd, och processanvändning. Metod. Ett spel-agnostisk streaming verktyg blev implementerade för Godot, som använder sig av state replication och client simulation för att synkronisera spel. Sen samlades data in genom att testa sju spel gjorda med Godot, både för verktyget och traditionell video och ljud streaming. Datan som samlades in innehåll bandbredddata, process användning, och bilddata, datan jämfördes och blev analyserad. Resultat. Jämförd med traditionell streaming så använder den spel-agnostiska streaming verktyget betydligt mindre bandbredd och hade bättre bildkvalitet. Medantraditionell streaming använde mindre process användning och differensen mellanspelen var väldigt liten jämfört med streaming verktyget. Slutsatser. Resultatet visade att det finns en chans för spel streaming med knapp-tryckningar och spellägen att vara ett vettigt alternativ för traditionell streaming. Verktyget är inte helt spel-agnostisk för alla spel gjorda i Godot men det använder mindre bandbredd för de flesta spelen och bildkvaliteten är bättre. Men verktyget kräver bättre hårdvara än vanlig streaming med ljud och bild.
|
19 |
Learning to Learn : Generalizing Reinforcement Learning Policies for Intent-Based Service Management using Meta-LearningDamberg, Simon January 2024 (has links)
Managing a system of network services is a complex and large-scale task that often lacks a trivial optimal solution. Deep Reinforcement Learning (RL) has shown great potential in being able to solve these tasks in static settings. However, in practice, the RL agents struggle to generalize their control policies enough to work in more dynamic real-world environments. To achieve a generality between environments, multiple contributions are made by this thesis. Low-level metrics are collected from each node in the system to help explain changes in the end-to-end delay of the system. To achieve generality in its control policy, more ways to observe and understand the dynamic environment and how it changes are provided to the RL agent by introducing the end-to-end delay of each service in the system to its observation space. Another approach to achieving more generality in RL policies is Model-Agnostic Meta-Learning (MAML), a type of Meta-Learning approach where instead of learning to solve a specific task, the model learns to learn how to quickly solve a new task based on prior knowledge. Results show that low-level metrics yield a much greater generality when helping to explain the delay of a system. Applying MAML to the problem is beneficial in adding generality to a learned RL policy and making the adaptation to a new task faster. If the RL agent can observe the changes to the underlying dynamics of the environment between tasks by itself, the policy can achieve this generality by itself without the need for a more complex method. However, if acquiring or observing the necessary data is too expensive or complex, switching to a Meta-Learning approach might be beneficial to increase generality. / Hanteringen av ett system med nätverksstjänster är ett komplext och stor skaligt problem där den optimal lösning inte är trivial. Djup förstärkningsinlärning har visat stor potential i att kunna lösa dessa problem i statiska miljöer. Dock är det svårt att generalisera lösningarna tillräckligt för att fungera i mer komplicerade och realistiska dynamiska miljöer. För att uppnå mer generella lösningar mellan miljöer presenterar denna masteruppsats flera möjliga lösningar. Lågnivåmetrik samlas in från varje nod i systemet för att hjälpa förklara skillnader i den totala responstiden för varje tjänst i systemet. För att generalisera förstärkningsinlärningsmodellen kan den förses med fler sätt att observera miljön, och därmed lära sig förstå hur den dynamiska miljön förändras. En annan metod för att uppnå mer generalitet inom förstärkningsinlärning är Model-Agnostic Meta-Learning (MAML), en typ av Meta-Learning där istället för att lära sig att lösa en specifik uppgift, modellen lär sig att lära sig att snabbt lösa en ny uppgift baserat på sin tidigare kunskap. Resultaten visar att lågnivåmetriken leder till en mycket högre generalitet i att hjälpa till att förklara responstiden av ett system. Att applicera MAML till problemet hjälper att bidra med generalitet till en förstärkningsinlärningsmodell och gör anpassningen till en ny uppgift snabbare. Om modellen själv kan observera ändringarna i underliggande dynamiken bakom miljön mellan uppgifter kan den uppnå mer generalitet utan ett behov av en mer komplex metod som MAML. Däremot, om det är svårt eller dyrt att få tag på eller observera den nödvändiga datan, kan ett byte till en Meta-Learning baserad metod vara mer fördelaktig för att öka generaliteten.
|
20 |
Natural strange beatitudes : Geoffrey Hill's The Orchards of Syon, poetic oxymoron and post-secular poetics, and, An Atheist's Prayer-BookWooding, Jonathan January 2015 (has links)
Geoffrey Hill’s The Orchards of Syon (2002) occupies a contradictory position in twenty-first century poetry in being a major religious work in a post-religious age. Contemporary secular and atheistic insistence on the fundamentally crafted and flawed nature of religious faith has led Hill not to the abandoning of religious vision, but to a theologically disciplined approach to syntax, grammar and etymology. This dissertation examines Hill’s claim to a poetics of agnostic faith that mediate his alienation from a cynical and debased Anglophone contemporaneity. The oxymoronic nature of a faith co-existent with existential loss is the primary focus. The semantic distinction between paradox and poetic oxymoron is examined, and the agonistic and aporetic dimensions of the oxymoron are considered as affording theological significance. Poetic oxymoron as site of both foolish babbling and Pentecostal exuberance is made explicit, as is Hill’s relation to the oxymoronic nature of beatitudinous expression and the Kenotic Hymn. Hill’s reading of and relation to other theologically engaged poets is outlined. Thomas Hardy’s tragic-comic vision, Gerard Manley Hopkins’ restrained rapture in ‘The Windhover’, and T. S. Eliot’s expression of kenotic dissolution in ‘Marina’ are read as precursors to Hill’s revisionary God-language. William Empson’s significant difficulties with aspects of Hopkins’ and Eliot’s poetics is appraised as evidence of an oxymoronic and theological dimension within poetic ambiguity. Hill’s imperative to embody and enact theological vision and responsibility is tested in a reading of The Orchards of Syon. Paul Ricoeur’s perception of the religious significance of atheism is provocation for my own creative practice, as is the performative theology implicit in both Graham Shaw’s hermeneutic approach, and Hill’s visionary philology. Creative process draws on Simone Weil’s notion of decreation, the kenotic paradigm as exemplified in the life and writings of Dietrich Bonhoeffer, and the continuing secular vitality of the apostrophic lyric mode.
|
Page generated in 0.3102 seconds