17337

17337

حسگري‌فشرده روي گراف با درنظر گرفتن محدوديت و قيود ساختاري گراف

كارشناسي ارشد

هوش مصنوعي و رباتيك

اسفند‌ماه 1394

دكتر مرتضي آنالوئي

كامپيوتر

چكيده حسگري‌فشرده، يك الگوي جديد در تئوري پردازش سيگنال است كه بوسيله يك روند اندازه‌گيري خطي كمتر از نرخ نايكوئيست، نمونه‌گيري و فشرده‌سازي سيگنال‌هاي تنك را تركيب مي‌كند و حاصل آن بردار خروجي است كه از تعداد اندكي اندازه‌گيري بدست آمده است و سپس با استفاده از الگوريتم بازيابي مناسب، تنك‌ترين سيگنالي كه با اندازه‌گيري‌ها تطابق دارد، بازيابي مي‌شود. حسگري‌فشرده روي گراف، سيگنال‌ها مي‌توانند بوسيله گراف و با نودهايي كه حاوي اطلاعات هستند، تقريب زده شوند بنابراين مي‌توان از حسگري‌فشرده براي جمع‌آوري اطلاعات توزيع شده بروي نودها و يا لينك‌ها استفاده نمود. همچنين به دو دليل هزينه زياد بررسي يك به يك پارامترها و در دسترس نبودن اطلاعات برخي از آنها به صورت مستقيم در گراف، حسگري‌فشرده روي گراف حائز اهميت مي‌گردد. محدوديت‌هاي ساختاري گراف، بين حسگري‌فشرده در گراف با حسگري‌فشرده معمولي تفاوت‌هايي ايجاد مي‌كند از مهمترين اين تفاوت‌ها مي‌توان به ساخت ماتريس اندازه‌گيري اشاره نمود. براي ساخت ماتريس اندازه‌گيري در حسگري‌فشرده معمولي، از ماتريس تصادفي گوسي استفاده مي‌شود اما چون مشاهداتي كه روي گراف داريم همگي ضرايب نامنفي هستند و نمي‌توان از اين ماتريس‌ براي ساخت ماتريس‌اندازه‌گيري در حوزه گراف، استفاده نمود. يكي از روش‌هاي ساخت اين ماتريس در حوزه گراف، روش قدم‌زني تصادفي است كه با احتمال بالائي شرايط لازم براي بازيابي داده بصورت يكتا را فراهم مي‌كند اگرچه كه به دليل ساختار و قيود شبكه، هر مشاهده‌اي روي گراف امكان‌پذير نبوده و اين مشكل مي‌تواند منجر به بازيابي ضعيف بردار اوليه شود. يادگيري فعال، يك زير مجموعه از يادگيري ماشين‌ و بطور عمومي‌تر از هوش مصنوعي است. ايده‌ي كليدي آنست كه اگر به الگوريتم يادگيري اجازه داده شود تا اطلاعاتي را كه بايد بياموزد، خود انتخاب كند آنگاه با آموزش كمتر، عملكرد بهتري خواهد داشت. در اين پايان‌نامه، سعي شده با استفاده از ايده‌ي يادگيري فعال و قدم زن‌تصادفي، روشي براي بهبود ساخت ماتريس اندازه‌گيري در حوزه گراف معرفي شود تا اطلاعاتي از گراف كه در ساخت ماتريس‌اندازه‌گيري(با فرض اينكه ماتريس اندازه‌گيري زيرمعين و غيرفقي است) به روش قدم‌زني تصادفي ممكن است از قلم افتاده‌ باشند، مشخص شده و پس از مشاهده، در ماتريس اندازه‌گيري درج شوند كه نتيجه آن بازيابي قوي‌تر سيگنال اوليه خواهد بود. جهت آزمون اين روش، ابتدا از روي مجموعه داده شامل پانصد نود بعنوان سيگنال اوليه، ماتريس اندازه‌گيري با دو روش قدم‌زني تصادفي و روش پيشنهادي، ساخته مي‌شود و از روي آن بردار خروجي بدست مي‌آيد سپس سيگنال تنك اوليه با دو الگوريتم بازيابي بهينه‌سازي محدب و مدل آيزينگ، بازيابي مي‌شود و در نهايت ميزان خطا و ميزان شباهت چهار سيگنال بازيابي شده را نسبت به سيگنال اوليه محاسبه نموده و از مقايسه آنها مشخص مي‌گردد بازيابي سيگنال تنك از روي ماتريس ساخته شده به روش پيشنهادي و بازيابي با الگوريتم بهينه سازي محدب، داراي بيشترين ميزان شباهت و كمترين مقدار خطا با سيگنال اوليه، نسبت به سه سيگنال بازيابي شده‌ي ديگر است. واژه‌هاي كليدي: حسگري‌فشرده، محدوديت ساختاري گراف، ماتريس اندازه‌گيري، يادگيري فعال.

1396/03/08

1/1/1900 12:00:00 AM

Abstract: Compressive sensing is a new pattern in the field of signal processing which mixes sampling and compressing of sparse signals using a linear measurement procedure less than Nyquist rate so that the result is an output vector consisting of a few number of measurements and afterward, using a proper recovery algorithm the most sparsest signal is recovered which matches the measurements. Compressive sensing on a graph; signals could be estimated by graphs and nodes containing information. There are tow reasons why compressive sensing on graphs is important: because of intense cost of one-by-one checking of parameters and direct inaccessibility to information of some of the parameters in the graph. Structural limitations of graphs cause some differences between conventional and compressive sensing which distinguish them. One of the most important of these differences is the construction of measurement matrix. In order to construct the measurement matrix in conventional sensing, random Gaussian matrix is used. But because all of the observation on the graph we have had are non-negative coefficients, this matrix can’t be used to construct measurement matrix in the field of graph. One of the ways to construct this matrix in the field of graph is the Random Walk although because of the construction and limitations of the network, any observation on the graph is not possible and this problem can lead to weak recovery of initial vector. Family of measurement matrixes which could be applied in compressive sensing on graph, are more limited than matrixes in the field of conventional sensing (video or sound) and need to be proportional to the graph’s (network) construction. Active learning, is a subset of machine vision and generally artificial intelligence. The key idea is that if the learning algorithm is allowed to choose the information that should be learned by itself, then the algorithm will have better performance with less learnings. In the current work, using the idea of active learning, we’ve tried to introduce a method to improve the construction of measurement matrix in the field of graph to recognize the probably missed information of the graph in construction of measurement matrix (assuming that measurement matrix is sub-determined and non-adaptive), by random walk method and after observation, insert those information in the measurement matrix to have a stronger recovery of the initial graph. In order to eva​luate this method, first using five hundred nodes as initial signal, the measurement matrix is constructed by two methods: random walk and our suggested method, and using that we achieve the output vector. Then, the initial sparse signal is reviewed by two algorithms: the convex optimization recovery algorithm and Ising model, and finally calculate the amount of error and amount of similarity of four recovered signal to initial signal and by comparing them we get to know that recovery of sparse signal from the constructed matrix based on our suggested method and based on convex optimization recovery algorithm, has the most amount of similarity and the least amount of error to initial signal, compared to other three recovered signal. Keywords: Compressive sensing, constructional limitation of graph, measurement matrix, active learning.