Cette thèse porte sur l'étude des Systèmes de Recommandation dans un cadre séquentiel, où les retours des utilisateurs sur des articles arrivent dans le système l'un après l'autre. Après chaque retour utilisateur, le système doit le prendre en compte afin d'améliorer les recommandations futures. De nombreuses techniques de recommandation ou méthodologies d'évaluation ont été proposées par le passé pour les problèmes de recommandation. Malgré cela, l'évaluation séquentielle, qui est pourtant plus réaliste et se rapproche davantage du cadre d'évaluation d'un vrai système de recommandation, a été laissée de côté. Le contexte séquentiel nécessite de prendre en considération différents aspects non visibles dans un contexte fixe. Le premier de ces aspects est le dilemme dit d'exploration vs. exploitation: le modèle effectuant les recommandations doit trouver le bon compromis entre recueillir de l'information sur les goûts des utilisateurs à travers des étapes d'exploration, et exploiter la connaissance qu'il a à l'heure actuelle pour maximiser le feedback reçu. L'importance de ce premier point est mise en avant à travers une première évaluation, et nous proposons une approche à la fois simple et efficace, basée sur la Factorisation de Matrice et un algorithme de Bandit Manchot, pour produire des recommandations appropriées. Le second aspect pouvant apparaître dans le cadre séquentiel surgit dans le cas où une liste ordonnée d'articles est recommandée au lieu d'un seul article. Dans cette situation, le feedback donné par l'utilisateur est multiple: la partie explicite concerne la note donnée par l'utilisateur concernant l'article choisi, tandis que la partie implicite concerne les articles cliqués (ou non cliqués) parmi les articles de la liste. En intégrant les deux parties du feedback dans un modèle d'apprentissage, nous proposons une approche basée sur la Factorisation de Matrice, qui peut recommander de meilleures listes ordonnées d'articles, et nous évaluons cette approche dans un contexte séquentiel particulier pour montrer son efficacité. / This thesis is dedicated to the study of Recommendation Systems under a sequential setting, where the feedback given by users on items arrive one after another in the system. After each feedback, the system has to integrate it and try to improve future recommendations. Many techniques or evaluation methods have already been proposed to study the recommendation problem. Despite that, such sequential setting, which is more realistic and represent a closer framework to a real Recommendation System evaluation, has surprisingly been left aside. Under a sequential context, recommendation techniques need to take into consideration several aspects which are not visible for a fixed setting. The first one is the exploration-exploitation dilemma: the model making recommendations needs to find a good balance between gathering information about users' tastes or items through exploratory recommendation steps, and exploiting its current knowledge of the users and items to try to maximize the feedback received. We highlight the importance of this point through the first evaluation study and propose a simple yet efficient approach to make effective recommendation, based on Matrix Factorization and Multi-Armed Bandit algorithms. The second aspect emphasized by the sequential context appears when a list of items is recommended to the user instead of a single item. In such a case, the feedback given by the user includes two parts: the explicit feedback as the rating, but also the implicit feedback given by clicking (or not clicking) on other items of the list. By integrating both feedback into a Matrix Factorization model, we propose an approach which can suggest better ranked list of items, and we evaluate it in a particular setting.

The ring of integers is a very interesting ring, it has the amazing property that each of its elements may be expressed uniquely, up to order, as a product of prime elements. Unfortunately, not every ring possesses this property for its elements. The work of mathematicians like Kummer and Dedekind lead to the study of a special type of ring, which we now call a Dedekind domain, where even though unique prime factorization of elements may fail, the ideals of a Dedekind domain still enjoy the property of unique prime factorization into a product of prime ideals, up to order of the factors. This thesis seeks to establish the unique prime ideal factorization of ideals in a special type of Dedekind domain: the ring of algebraic integers of an imaginary quadratic number field.

隨著網路的發達,各式各樣的資訊和商品也在網路上充斥著,使用者尋找資訊或是上網購物時,有的網站有推薦系統(recommender system)能提供使用者相關資訊或商品。若推薦系統能夠讓消費者所搜尋的相關資訊或商品能夠符合他們的習性時,便能讓消費者增加對系統的信賴程度,因此系統是否能準確預測出使用者的偏好就成為一個重要的課題。本研究使用兩筆資料,並以相關研究的三篇文獻進行分析和比較。這三篇文獻分別為IRT模型法(IRT model-based method)、相關係數法(correlation-coefficient method)、以及矩陣分解法(matrix factorization)。 在經過一連串的實證分析後,歸納出以下結論: 1. 模型法在預測方面雖然精確度不如其他兩種方法來的好,但是模型有解釋變數之間的關係以及預測機率的圖表展示,因此這個方法仍有存在的價值。 2. 相關係數法容易因為評分稀疏性的問題而無法預測,建議可以搭配內容式推薦系統的運作方式協助推薦。 3. 矩陣分解法在預測上雖然比IRT模型法還好，但分量的數字只是一個最佳化的結果，實際上無法解釋這些分量和數字的意義。 / With the growth of the internet, websites are full of a variety of information and products. When users find the information or surf the internet to shopping, some websites provide users recommender system to find with which related. Hence, whether the recommender system can predict the users' preference is an important topic. This study used two data,which are "Mondo" and "MovieLens", and we used three related references to analyze and compare them. The three references are following: IRT model-based method, Correlation-coefficient method, and Matrix factorization. After the data analysis, we get the following conclusions: 1. IRT model-based method is worse then other methods in predicting, but it can explain the relationship of variables and display the graph of predicting probabilities. Hence this method still has it's value. 2. Correlation-coefficient method is hard to predict because of sparsity. We can connect it with content filtering approach. 3. Although matrix factorization is better then IRT model-based method in predicting, the vectors is a result of optimization. It may be hard to explain the meaning of the vectors.

近幾年來，華語流行音樂的發展越來越多元，而大眾所接收到的資訊是流行音樂當中的組成元素”曲與詞”，兩者分別具有賦予人類感知的功能，使人能夠深刻體會音樂作品當中所表答的內容與意境。然而，作曲與作詞都是屬於專業的創作藝術，作詞者通常在填詞時，會先對樂曲當中的結構進行粗略的分析，找出整首曲子的曲式，而針對可以填詞的部份，再進行更細部的分析將詞填入最適當的位置。流行音樂當中，曲與詞存在著密不可分的關係，瞭解歌曲結構不僅能降低填詞的門檻，亦能夠明白曲子的骨架與脈絡;在音樂教育與音樂檢索方面亦有幫助。 本研究的目標為，使用者輸入流行音樂歌曲，系統會自動分析出曲子的『曲式結構』。方法主要分成三個部分，分別為主旋律擷取、歌句分段與音樂曲式結構擷取。首先，我們利用Support Vector Machine以學習之方式建立模型後，擷取出符號音樂中之主旋律。第二步驟我們以”歌句”為單位，對主旋律進行分段，對於分段之結果建構出Self-Similarity Matrix矩陣。最後再利用Non-Negative Matrix Factorization針對不同特徵值矩陣進行分解並建立第二層之Self-Similarity Matrix矩陣，以歧異度之方式找出曲式邊界。 我們針對分段方式對歌曲結構之影響進行分析與觀察。實驗數據顯示，事先將歌曲以歌句單位分段之效果較未分段佳，而歌句分段之評測結果F-Score為0.82;將音樂中以不同特徵值建構之自相似度矩進行Non-Negative Matrix Factorization後，另一空間中之基底特徵更能有效地分辨出不同的歌曲結構，其F-Score為0.71。 / Music structure analysis is helpful for music information retrieval, music education and alignment between lyrics and music. This thesis investigates the techniques of music structure analysis for Chinese popular music. Our work is to analyze music form automatically by three steps, main melody finding, sentence discovery, and music form discovery. First, we extract main melody based on learning from user-labeled sample using support vector machine. Then, the boundary of music sentence is detected by two-way classification using support vector machine. To discover the music form, the sentence-based Self-Similarity Matrix is constructed for each music feature. Non-negative Matrix Factorization is employed to extract the new features and to construct the second level Self-Similarity Matrix. The checkerboard kernel correlation is utilized to find music form boundaries on the second level Self-Similarity Matrix. Experiments on eighty Chinese popular music are performed for performance evaluation of the proposed approaches. For the main melody finding, our proposed learning-based approach is better than existing methods. The proposed approaches achieve 82% F-score for sentence discovery while 71% F-score for music form discovery.

This thesis concerns methods of reduced complexity for electronic structure calculations.  When quantum chemistry methods are applied to large systems, it is important to optimally use computer resources and only store data and perform operations that contribute to the overall accuracy. At the same time, precarious approximations could jeopardize the reliability of the whole calculation.  In this thesis, the self-consistent field method is seen as a sequence of rotations of the occupied subspace. Errors coming from computational approximations are characterized as erroneous rotations of this subspace. This viewpoint is optimal in the sense that the occupied subspace uniquely defines the electron density. Errors should be measured by their impact on the overall accuracy instead of by their constituent parts. With this point of view, a mathematical framework for control of errors in Hartree-Fock/Kohn-Sham calculations is proposed.  A unifying framework is of particular importance when computational approximations are introduced to efficiently handle large systems. An important operation in Hartree-Fock/Kohn-Sham calculations is the calculation of the density matrix for a given Fock/Kohn-Sham matrix. In this thesis, density matrix purification is used to compute the density matrix with time and memory usage increasing only linearly with system size. The forward error of purification is analyzed and schemes to control the forward error are proposed. The presented purification methods are coupled with effective methods to compute interior eigenvalues of the Fock/Kohn-Sham matrix also proposed in this thesis.New methods for inverse factorizations of Hermitian positive definite matrices that can be used for congruence transformations of the Fock/Kohn-Sham and density matrices are suggested as well. Most of the methods above have been implemented in the Ergo quantum chemistry program. This program uses a hierarchic sparse matrix library, also presented in this thesis, which is parallelized for shared memory computer architectures. It is demonstrated that the Ergo program is able to perform linear scaling Hartree-Fock calculations. / QC 20100908

In this thesis, improving the performance of the automatic recognition of the Doppler radar targets is studied. The radar used in this study is a ground-surveillance doppler radar. Target types are car, truck, bus, tank, helicopter, moving man and running man. The input of this thesis is the output of the real doppler radar signals which are normalized and preprocessed (TRP vectors: Target Recognition Pattern vectors) in the doctorate thesis by Erdogan (2002). TRP vectors are normalized and homogenized doppler radar target signals with respect to target speed, target aspect angle and target range. Some target classes have repetitions in time in their TRPs. By the use of these repetitions, improvement of the target type classification performance is studied. K-Nearest Neighbor (KNN) and Support Vector Machine (SVM) algorithms are used for doppler radar target classification and the results are evaluated. Before classification PCA (Principal Component Analysis), LDA (Linear Discriminant Analysis), NMF (Nonnegative Matrix Factorization) and ICA (Independent Component Analysis) are implemented and applied to normalized doppler radar signals for feature extraction and dimension reduction in an efficient way. These techniques transform the input vectors, which are the normalized doppler radar signals, to another space. The effects of the implementation of these feature extraction algoritms and the use of the repetitions in doppler radar target signals on the doppler radar target classification performance are studied.

Approximately 2000 daily aerosol samples were collected at Antalya (30&deg / 34&amp / #900 / 30.54 E, 36&deg / 47&amp / #8217 / 30.54N) on the Mediterranean coast of Turkey between 1993 and 2001. High volume PM10 sampler was used for the collection of samples on Whatman&amp / #8211 / 41 filters. Collected samples were analyzed by a combination of analytical techniques. Energy Dispersive X-Ray Fluorescence (EDXRF) and Inductively Coupled Plasma Mass Spectrometry (ICPMS) was used to measure trace element content of the collected samples from Li to U. Major ions, namely, SO42- and NO3-, were determined by employing Ion Chromatography (IC). Samples were analyzed in terms of their NH4+ contents by means of Colorimetry. Evaluation of short term trends of measured parameters have been shown that elements with marine and crustal origin are more episodic as compared to anthropogenic ones. Most of the parameters showed well defined seasonal cycles, for example, concentrations of crustal elements increased in summer season while winter concentrations of marine elements were considerably higher than associated values for summer. Seasonal Kendall statistic depicted that there was a decreasing trend for crustal elements such as Be, Co, Al, Na, Mg, K, Dy, Ho, Tm, Cs and Eu. Lead, As, Se and Ge were the anhtropogenic elements that decreasing trend was detected in the course of study period. Cluster and Residence time analysis were performed to find the origin of air masses arrving to Eastern Mediterranena Basin. It has been found that air masses reaching to our station resided more on Balkans and Eastern Europe. Positive Matrix Factorization (PMF) resolved eight factors influencing the chemical composition of Eastern Mediterranean aerosols as local dust, Saharan dust, oil combustion, coal combustion, crustal-anthropogenic mixed, sea salt, motor vehicle emission, and local Sb factor.

Nonnegative matrix factorization (NMF) is a useful dimension reduction method that has been investigated and applied in various areas. NMF is considered for high-dimensional data in which each element has a nonnegative value, and it provides a low-rank approximation formed by factors whose elements are also nonnegative. The nonnegativity constraints imposed on the low-rank factors not only enable natural interpretation but also reveal the hidden structure of data. Extending the benefits of NMF to multidimensional arrays, nonnegative tensor factorization (NTF) has been shown to be successful in analyzing complicated data sets. Despite the success, NMF and NTF have been actively developed only in the recent decade, and algorithmic strategies for computing NMF and NTF have not been fully studied. In this thesis, computational challenges regarding NMF, NTF, and related least squares problems are addressed. First, efficient algorithms of NMF and NTF are investigated based on a connection from the NMF and the NTF problems to the nonnegativity-constrained least squares (NLS) problems. A key strategy is to observe typical structure of the NLS problems arising in the NMF and the NTF computation and design a fast algorithm utilizing the structure. We propose an accelerated block principal pivoting method to solve the NLS problems, thereby significantly speeding up the NMF and NTF computation. Implementation results with synthetic and real-world data sets validate the efficiency of the proposed method. In addition, a theoretical result on the classical active-set method for rank-deficient NLS problems is presented. Although the block principal pivoting method appears generally more efficient than the active-set method for the NLS problems, it is not applicable for rank-deficient cases. We show that the active-set method with a proper starting vector can actually solve the rank-deficient NLS problems without ever running into rank-deficient least squares problems during iterations. Going beyond the NLS problems, it is presented that a block principal pivoting strategy can also be applied to the l1-regularized linear regression. The l1-regularized linear regression, also known as the Lasso, has been very popular due to its ability to promote sparse solutions. Solving this problem is difficult because the l1-regularization term is not differentiable. A block principal pivoting method and its variant, which overcome a limitation of previous active-set methods, are proposed for this problem with successful experimental results. Finally, a group-sparsity regularization method for NMF is presented. A recent challenge in data analysis for science and engineering is that data are often represented in a structured way. In particular, many data mining tasks have to deal with group-structured prior information, where features or data items are organized into groups. Motivated by an observation that features or data items that belong to a group are expected to share the same sparsity pattern in their latent factor representations, We propose mixed-norm regularization to promote group-level sparsity. Efficient convex optimization methods for dealing with the regularization terms are presented along with computational comparisons between them. Application examples of the proposed method in factor recovery, semi-supervised clustering, and multilingual text analysis are presented.

現今許多網路商店或電子商務將產品銷售給消費者的過程中，皆使用推薦系統的幫助來提高銷售量。如亞馬遜公司(Amazon)、Netflix，深入了解顧客的使用習慣，建構專屬的推薦系統並進行個性化的推薦商品給每一位顧客。 推薦系統應用的技術分為協同過濾和內容過濾兩大類，本研究旨在探討協同過濾推薦系統中潛在因子模型方法，利用矩陣分解法找出評分矩陣。在Koren等人(2009)中，將矩陣分解法的演算法大致分為兩種，隨機梯度下降法(Stochastic gradient descent)與交替最小平方法(Alternating least squares)。本研究主要研究目的有三項，一為比較交替最小平方法與隨機梯度下降法的預測能力，二為兩種矩陣分解演算法在加入偏誤項後的表現，三為先完成交替最小平方法與隨機梯度下降法，以其預測值對原始資料之遺失值進行資料插補，再利用奇異值分解法對完整資料做矩陣分解，觀察其前後方法的差異。 研究結果顯示，隨機梯度下降法所需的運算時間比交替最小平方法所需的運算時間少。另外，完成兩種矩陣分解演算法後，將預測值插補遺失值，進行奇異值分解的結果也顯示預測能力有提升。 / Recommender system has been largely used by Internet companies such Amazon and Netflix to make recommendations for Internet users. Techniques for recommender systems can be divided into content filtering approach and collaborative filtering approach. Matrix factorization is a popular method for collaborative filtering approach. It minimizes the object function through stochastic gradient descent and alternating least squares. This thesis has three goals. First, we compare the alternating least squares method and stochastic gradient descent method. Secondly, we compare the performance of matrix factorization method with and without the bias term. Thirdly, we combine singular value decomposition and matrix factorization. As expected, we found the stochastic gradient descent takes less time than the alternating least squares method, and the the matrix factorization method with bias term gives more accurate prediction. We also found that combining singular value decomposition with matrix factorization can improve the predictive accuracy.

In this dissertation, we present our work on fault management in distributed systems, with motivating application roots in monitoring fault and abrupt change of large computing systems like the grid and the cloud. Instead of building a complete a priori knowledge of the software and hardware infrastructures as in conventional detection or diagnosis methods, we propose to use appropriate techniques to perform end-to-end monitoring for such large scale systems, leaving the inaccessible details of involved components in a black box.For the fault monitoring of a distributed system, we first model this probe-based application as a static collaborative prediction (CP) task, and experimentally demonstrate the effectiveness of CP methods by using the max margin matrix factorization method. We further introduce active learning to the CP framework and exhibit its critical advantage in dealing with highly imbalanced data, which is specially useful for identifying the minority fault class.Further we extend the static fault monitoring to the sequential case by proposing the sequential matrix factorization (SMF) method. SMF takes a sequence of partially observed matrices as input, and produces predictions with information both from the current and history time windows. Active learning is also employed to SMF, such that the highly imbalanced data can be coped with properly. In addition to the sequential methods, a smoothing action taken on the estimation sequence has shown to be a practically useful trick for enhancing sequential prediction performance.Since the stationary assumption employed in the static and sequential fault monitoring becomes unrealistic in the presence of abrupt changes, we propose a semi-supervised online change detection (SSOCD) framework to detect intended changes in time series data. In this way, the static model of the system can be recomputed once an abrupt change is detected. In SSOCD, an unsupervised offline method is proposed to analyze a sample data series. The change points thus detected are used to train a supervised online model, which gives online decision about whether there is a change presented in the arriving data sequence. State-of-the-art change detection methods are employed to demonstrate the usefulness of the framework.All presented work is verified on real-world datasets. Specifically, the fault monitoring experiments are conducted on a dataset collected from the Biomed grid infrastructure within the European Grid Initiative, and the abrupt change detection framework is verified on a dataset concerning the performance change of an online site with large amount of traffic.