L1-նորմ հիմնական բաղադրիչների վերլուծություն

L1-նորմ հիմնական բաղադրիչի վերլուծությունը (L1-PCA) հանդիսանում է բազմաբնույթ տվյալների վերլուծության ընդհանուր մեթոդ^[1]։ L1-PCA հաճախ ավելի նախընտրելի է ստանդարտ L2-նորմ հիմնական բաղադրիչը վերլուծությունից (PCA), երբ վերլուծած տվյալները պարունակում են հեռավոր կետեր(outliers)^[2]^[3]^[4]։

L1-PCA-ի համեմատությունը PCA-ի հետ: Նոմինալ տվյալներ (կապույտ կետեր); հեռավոր կետեր (կարմիր կետ); PC (սև գիծ); L1-PC (կարմիր գիծ); նոմինալ առավելագույն վարիացիայի գիծ (կետագծեր):

Ինչպես L1-PCA- ն, այնպես էլ ստանդարտ PCA- ն փնտրում են ուղղահայաց ուղղություններ հիմնական բաղադրիչների համար, որոնք սահմանում են այն տեղը, որտեղ տվյալների ներկայացուցչությունը առավելագույնի հասցվում է ըստ ընտրված չափանիշի^[5]^[6]^[7]։ Ստանդարտ PCA-ն տվյալների ներկայացումը քանակականացնում է որպես L2- նորմայի տվյալների պրոյեկցիաների ագրեգատ կամ սկզբնական կետերի և նրանց պրոյեկցիաների Էվկլիդյան հեռավորության համարժեք ագրեգատ։ L1-PCA- ն օգտագործում է L1- նորմայի կետերի պրոյեկցիաները^[8]։ PCA և L1-PCA-ում հիմնական բաղադրիչների քանակը ավելի քիչ է, քան վերլուծված մատրիցի ռանգը։ Մատրիցը համընկնում է օրիգինալ կետերի միջոցով սահմանված տարածքի չափողականության հետ։ Այդ պատճառով, PCA- ն կամ L1-PCA- ն սովորաբար օգտագործվում են չափողականության իջեցման համար` տվյալների սեղմման կամ աղմուկը քչացնելու նպատակով։

Այնուամենայնիվ, ժամանակակից մեծ տվյալները հաճախ ներառում են հեռավոր կետեր(outlier)^[3]։ Ստանդարտ PCA- ն զգայուն է հեռավոր կետերի նկատմամբ^[9]։ Պատճառն այն է, որ L2-PCA-ի հիման վրա L2- նորմայի ձևավորումը քառակուսային շեշտադրում է կատարում յուրաքանչյուր կոորդինատի յուրաքանչյուր կետի մեծության վրա՝ ի վերջո գերագնահատելով ծայրամասային կետերը, ինչպիսիք են հեռավոր կետերը։ Մյուս կողմից, L1-norm-ի ձևակերպումից հետո L1-PCA- ն գծային շեշտադրում է կատարում յուրաքանչյուր կետի կոորդինատների վրա՝ արդյունավետորեն ՙՙզսպելով՚՚ հեռավոր կետերը^[10]։

Ձևակերպում խմբագրել

Դիտարկենք ցանկացած մատրիցա՝ $\mathbf {X} =[\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{N}]\in \mathbb {R} ^{D\times N}$ , որը բաղկացած է $N$ հատ $D$ -չափանի կետերից։ Սահմանենք ռանգ՝ $r=rank(\mathbf {X} )$ ։ $K$ ամբողջ թվի համար, որը $1\leq K<r$ , L1-PCA- ն ձևակերպումն է^[1]՝

{\begin{aligned}&{\underset {\mathbf {Q} =[\mathbf {q} _{1},\mathbf {q} _{2},\ldots ,\mathbf {q} _{K}]\in \mathbb {R} ^{D\times K}}{\max }}~~\|\mathbf {X} ^{\top }\mathbf {Q} \|_{1}\\&{\text{subject to}}~~\mathbf {Q} ^{\top }\mathbf {Q} =\mathbf {I} _{K}.\end{aligned}}

$K=1$ համար, ( 1 ) պարզեցնում է L1-norm-ի հիմնական բաղադրիչը (L1-PC) $\mathbf {X}$ գտնելը՝

{\begin{aligned}&{\underset {\mathbf {q} \in \mathbb {R} ^{D\times 1}}{\max }}~~\|\mathbf {X} ^{\top }\mathbf {q} \|_{1}\\&{\text{subject to}}~~\|\mathbf {q} \|_{2}=1.\end{aligned}}

( 1 ) - ( 2 ) բանաձևերում L1-norm $\|\cdot \|_{1}$ վերադարձնում է իր արգումենտների բացարձակ արժեքների գումարը։ L2-norm $\|\cdot \|_{2}$ վերադարձնում է իր արգումենտների քառակուսային արժեքների գումարը։ Եթե փոխարինենք $\|\cdot \|_{1}$ ( 2 ) բանաձևում ` Frobenius / L2-նորմայով $\|\cdot \|_{F}$ -ով, ապա խնդիրը դառնում է ստանդարտ PCA և այն լուծվում է $\mathbf {Q}$ մատրիցով, որ պարունակում է $K$ դոմինանտ եզակի $\mathbf {X}$ վեկտորներ (այսինքն, եզակի վեկտորներ, որոնք համապատասխանում են $K$ առավելագույն եզակի արժեքներին)։

( 2 ) բանաձևում առավելագույնի չափումը կարելի է ընդլայնել՝

\|\mathbf {X} ^{\top }\mathbf {Q} \|_{1}=\sum _{k=1}^{K}\sum _{n=1}^{N}|\mathbf {x} _{n}^{\top }\mathbf {q} _{k}|.

Լուծում խմբագրել

Ցանկացած մատրիցայի համար՝ $\mathbf {A} \in \mathbb {R} ^{m\times n}$ , որտեղ $m\geq n$ , սահմանել $\Phi (\mathbf {A} )$ որպես ամենամոտ (L2-norm իմաստով) մատրից $\mathbf {A}$ , որն ունի օրթոնորմալ սյուներ։ Այսինքն՝

{\begin{aligned}\Phi (\mathbf {A} )=&{\underset {\mathbf {Q} \in \mathbb {R} ^{m\times n}}{\text{argmin}}}~~\|\mathbf {A} -\mathbf {Q} \|_{F}\\&{\text{subject to}}~~\mathbf {Q} ^{\top }\mathbf {Q} =\mathbf {I} _{n}.\end{aligned}}

Procrustes թեորեմն^[11]^[12] ասում է, որ եթե $\mathbf {A}$ ունի SVD $\mathbf {U} _{m\times n}{\boldsymbol {\Sigma }}_{n\times n}\mathbf {V} _{n\times n}^{\top }$ , ապա $\Phi (\mathbf {A} )=\mathbf {U} \mathbf {V} ^{\top }$ .

Մարկոպուլոսը, Կարիստինոսը և Պադոսը^[1] ցույց տվեցին, որ, եթե $\mathbf {B} _{\text{BNM}}$ երկուական միջուկային նորմայի առավելագույնի բարձրացման (BNM) խնդրի ճշգրիտ լուծումն է, ապա՝

{\begin{aligned}{\underset {\mathbf {B} \in \{\pm 1\}^{N\times K}}{\text{max}}}~~\|\mathbf {X} \mathbf {B} \|_{*}^{2},\end{aligned}}

ապա

{\begin{aligned}\mathbf {Q} _{\text{L1}}=\Phi (\mathbf {X} \mathbf {B} _{\text{BNM}})\end{aligned}}

( 2 )-ում L1-PCA- ի ճշգրիտ լուծումն է։ Միջուկային նորմ $\|\cdot \|_{*}$ ( 2 )-ում վերադառնում է իր մատրիցային արգումենտի եզակի արժեքների ամփոփումը և կարող է հաշվարկվել ստանդարտ SVD- ի միջիններով։ Ավելին, այն պնդում է, որ հաշվի առնելով L1-PCA լուծումը, $\mathbf {Q} _{\text{L1}}$ , BNM- ի լուծումը կարելի է ստանալ հետևյալ կերպ՝

{\begin{aligned}\mathbf {B} _{\text{BNM}}={\text{sgn}}(\mathbf {X} ^{\top }\mathbf {Q} _{\text{L1}})\end{aligned}}

որտեղ ${\text{sgn}}(\cdot )$ վերադարձնում է իր մատրիցի արգումենտի $\{\pm 1\}$ նշանի մատրից (ընդհանուր կորստի բացակայության դեպքում մենք կարող ենք դիտարկել, որ ${\text{sgn}}(0)=1$ ): Բացի այդ, դրանից հետևում է, որ $\|\mathbf {X} ^{\top }\mathbf {Q} _{\text{L1}}\|_{1}=\|\mathbf {X} \mathbf {B} _{\text{BNM}}\|_{*}$ . BNM- ը ( 5 ) -ում կոմբինատորիկայի խնդիր է՝ կապված անտիպոդալ երկուական փոփոխականների հետ։ Հետևաբար, դրա ճշգրիտ լուծումը կարելի է գտնել բոլոր $2^{NK}$ էլեմենտների սպառիչ գնահատման միջոցով ${\mathcal {O}}(2^{NK})$ ասիմպտոտիկ արժեքով։ Հետևաբար, L1-PCA- ն նույնպես կարող է լուծվել BNM- ի միջոցով` ${\mathcal {O}}(2^{NK})$ -ով։ Պարզվում է, որ L1-PCA- ն հնարավոր է օպտիմալ կերպով (ճշգրիտ) լուծել` $N$ -ում պոլինոմիալ բարդության դեպքում ֆիքսված $D$ չափողականության համար , ${\mathcal {O}}(N^{rK-K+1})$ .^[1]

Հատուկ դեպքում, երբ $K=1$ ( $\mathbf {X}$ միակ L1-PC), BNM- ն ընդունում է երկուական-քառակուսային-մաքսիմումի (BQM) ձևը

{\begin{aligned}&{\underset {\mathbf {b} \in \{\pm 1\}^{N\times 1}}{\text{max}}}~~\mathbf {b} ^{\top }\mathbf {X} ^{\top }\mathbf {X} \mathbf {b} .\end{aligned}}

Անցումը ( 5 ) -ից ( 8 ) -ին, երբ $K=1$ , ճշմարիտ է, քանի որ $\mathbf {X} \mathbf {b}$ -ի եզակի արժեքը հավասար է $\|\mathbf {X} \mathbf {b} \|_{2}={\sqrt {\mathbf {b} ^{\top }\mathbf {X} ^{\top }\mathbf {X} \mathbf {b} }}$ , յուրաքանչյուրի $\mathbf {b}$ համար . Հետո, եթե $\mathbf {b} _{\text{BNM}}$ BQM-ի լուծումն է ( 7 ) -ում, այն ընդունում է հետևյալ տեսքը.

{\begin{aligned}\mathbf {q} _{\text{L1}}=\Phi (\mathbf {X} \mathbf {b} _{\text{BNM}})={\frac {\mathbf {X} \mathbf {b} _{\text{BNM}}}{\|\mathbf {X} \mathbf {b} _{\text{BNM}}\|_{2}}}\end{aligned}}

որը $\mathbf {X}$ -ի ճիշտ L1-PC- ն է, ինչպես սահմանված է ( 1 ) -ում։ Բացի այդ, $\mathbf {b} _{\text{BNM}}={\text{sgn}}(\mathbf {X} ^{\top }\mathbf {q} _{\text{L1}})$ և $\|\mathbf {X} ^{\top }\mathbf {q} _{\text{L1}}\|_{1}=\|\mathbf {X} \mathbf {b} _{\text{BNM}}\|_{2}$ .

Ալգորիթմներ խմբագրել

Էքսպոնենցիալ բարդության ճիշտ լուծում խմբագրել

Ինչպես ցույց է տրված վերևում, L1-PCA-ի ճշգրիտ լուծումը կարելի է ստանալ հետևյալ երկաստիճան գործընթացով.

 1. Լուծեք խնդիրը ( 5 )-ում` ստանալու համար  $\mathbf {B} _{\text{BNM}}$  .
 2. Կիրառել SVD   $\mathbf {X} \mathbf {B} _{\text{BNM}}$ -ի վրա և ստանալ  $\mathbf {Q} _{\text{L1}}$  .

Պոլինոմիալ բարդության ճշգրիտ լուծում խմբագրել

L1-PCA- ն հնարավոր է օպտիմալ կերպով լուծել ${\mathcal {O}}(N^{rK-K+1})$ , երբ $r=rank(\mathbf {X} )$ հաստատուն է $N$ -ի նկատմամբ (միշտ ճիշտ է սահմանափակ $D$ չափողականության համար)^[1]^[13]։

Կոմպլեքս տվյալներ խմբագրել

L1-PCA- ն ընդհանրացվել է նաև կոմպլեքս տվյալների մշակման համար։ Կոմպլեքս L1-PCA-ի համար 2018-ին առաջարկվել է երկու արդյունավետ ալգորիթմ^[14]։

Կոդ խմբագրել

L1-PCA-ի համար MATLAB կոդը հասանելի է MathWorks- ում^[15] և այլ պահոցներում^[16]։

Ծանոթագրություններ խմբագրել

↑ ^1,0 ^1,1 ^1,2 ^1,3 ^1,4 Markopoulos, Panos P.; Karystinos, George N.; Pados, Dimitris A. (2014 թ․ հոկտեմբեր). «Optimal Algorithms for L1-subspace Signal Processing». IEEE Transactions on Signal Processing. 62 (19): 5046–5058. arXiv:1405.6785. Bibcode:2014ITSP...62.5046M. doi:10.1109/TSP.2014.2338077.
↑ Barrodale, I. (1968). «L1 Approximation and the Analysis of Data». Applied Statistics. 17 (1): 51–57. doi:10.2307/2985267. JSTOR 2985267.
↑ ^3,0 ^3,1 Barnett, Vic; Lewis, Toby (1994). Outliers in statistical data (3. ed.). Chichester [u.a.]: Wiley. ISBN 978-0471930945.
↑ Kanade, T.; Ke, Qifa (2005 թ․ հունիս). Robust L1 Norm Factorization in the Presence of Outliers and Missing Data by Alternative Convex Programming. Vol. 1. IEEE. էջ 739. CiteSeerX 10.1.1.63.4605. doi:10.1109/CVPR.2005.309. ISBN 978-0-7695-2372-9. {{cite book}}: |work= ignored (օգնություն)
↑ Jolliffe, I.T. (2004). Principal component analysis (2nd ed.). New York: Springer. ISBN 978-0387954424.
↑ Bishop, Christopher M. (2007). Pattern recognition and machine learning (Corr. printing. ed.). New York: Springer. ISBN 978-0-387-31073-2.
↑ Pearson, Karl (2010 թ․ հունիսի 8). «On Lines and Planes of Closest Fit to Systems of Points in Space» (PDF). The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science. 2 (11): 559–572. doi:10.1080/14786440109462720.
↑ Markopoulos, Panos P.; Kundu, Sandipan; Chamadia, Shubham; Pados, Dimitris A. (2017 թ․ օգոստոսի 15). «Efficient L1-Norm Principal-Component Analysis via Bit Flipping». IEEE Transactions on Signal Processing. 65 (16): 4252–4264. arXiv:1610.01959. Bibcode:2017ITSP...65.4252M. doi:10.1109/TSP.2017.2708023.
↑ Candès, Emmanuel J.; Li, Xiaodong; Ma, Yi; Wright, John (2011 թ․ մայիսի 1). «Robust principal component analysis?». Journal of the ACM. 58 (3): 1–37. arXiv:0912.3599. doi:10.1145/1970392.1970395.
↑ Kwak, N. (2008 թ․ սեպտեմբեր). «Principal Component Analysis Based on L1-Norm Maximization». IEEE Transactions on Pattern Analysis and Machine Intelligence. 30 (9): 1672–1680. doi:10.1109/TPAMI.2008.114. PMID 18617723.
↑ Eldén, Lars; Park, Haesun (1999 թ․ հունիսի 1). «A Procrustes problem on the Stiefel manifold». Numerische Mathematik. 82 (4): 599–619. doi:10.1007/s002110050432.
↑ Schönemann, Peter H. (1966 թ․ մարտ). «A generalized solution of the orthogonal procrustes problem». Psychometrika. 31 (1): 1–10. doi:10.1007/BF02289451.
↑ Markopoulos, PP; Kundu, S; Chamadia, S; Tsagkarakis, N; Pados, DA (2018). Outlier-Resistant Data Processing with L1-Norm Principal Component Analysis. էջ 121. doi:10.1007/978-981-10-6704-4_6. ISBN 978-981-10-6703-7. {{cite book}}: |work= ignored (օգնություն)
↑ Tsagkarakis, Nicholas; Markopoulos, Panos P.; Sklivanitis, George; Pados, Dimitris A. (2018 թ․ հունիսի 15). «L1-Norm Principal-Component Analysis of Complex Data». IEEE Transactions on Signal Processing. 66 (12): 3256–3267. arXiv:1708.01249. Bibcode:2018ITSP...66.3256T. doi:10.1109/TSP.2018.2821641.
↑ «L1-PCA TOOLBOX». Վերցված է 2018 թ․ մայիսի 21-ին.
↑ Markopoulos, PP. «Software Repository». Վերցված է 2018 թ․ մայիսի 21-ին.(չաշխատող հղում)

[mark2014-1] 1,0 ^1,1 ^1,2 ^1,3 ^1,4 Markopoulos, Panos P.; Karystinos, George N.; Pados, Dimitris A. (2014 թ․ հոկտեմբեր). «Optimal Algorithms for L1-subspace Signal Processing». IEEE Transactions on Signal Processing. 62 (19): 5046–5058. arXiv:1405.6785. Bibcode:2014ITSP...62.5046M. doi:10.1109/TSP.2014.2338077.

[2] Barrodale, I. (1968). «L1 Approximation and the Analysis of Data». Applied Statistics. 17 (1): 51–57. doi:10.2307/2985267. JSTOR 2985267.

[Barnett_1994-3] 3,0 ^3,1 Barnett, Vic; Lewis, Toby (1994). Outliers in statistical data (3. ed.). Chichester [u.a.]: Wiley. ISBN 978-0471930945.

[4] Kanade, T.; Ke, Qifa (2005 թ․ հունիս). Robust L1 Norm Factorization in the Presence of Outliers and Missing Data by Alternative Convex Programming. Vol. 1. IEEE. էջ 739. CiteSeerX 10.1.1.63.4605. doi:10.1109/CVPR.2005.309. ISBN 978-0-7695-2372-9. {{cite book}}: |work= ignored (օգնություն)

[5] Jolliffe, I.T. (2004). Principal component analysis (2nd ed.). New York: Springer. ISBN 978-0387954424.

[6] Bishop, Christopher M. (2007). Pattern recognition and machine learning (Corr. printing. ed.). New York: Springer. ISBN 978-0-387-31073-2.

[7] Pearson, Karl (2010 թ․ հունիսի 8). «On Lines and Planes of Closest Fit to Systems of Points in Space» (PDF). The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science. 2 (11): 559–572. doi:10.1080/14786440109462720.

[mark2017-8] Markopoulos, Panos P.; Kundu, Sandipan; Chamadia, Shubham; Pados, Dimitris A. (2017 թ․ օգոստոսի 15). «Efficient L1-Norm Principal-Component Analysis via Bit Flipping». IEEE Transactions on Signal Processing. 65 (16): 4252–4264. arXiv:1610.01959. Bibcode:2017ITSP...65.4252M. doi:10.1109/TSP.2017.2708023.

[9] Candès, Emmanuel J.; Li, Xiaodong; Ma, Yi; Wright, John (2011 թ․ մայիսի 1). «Robust principal component analysis?». Journal of the ACM. 58 (3): 1–37. arXiv:0912.3599. doi:10.1145/1970392.1970395.

[kwak2008-10] Kwak, N. (2008 թ․ սեպտեմբեր). «Principal Component Analysis Based on L1-Norm Maximization». IEEE Transactions on Pattern Analysis and Machine Intelligence. 30 (9): 1672–1680. doi:10.1109/TPAMI.2008.114. PMID 18617723.

[11] Eldén, Lars; Park, Haesun (1999 թ․ հունիսի 1). «A Procrustes problem on the Stiefel manifold». Numerische Mathematik. 82 (4): 599–619. doi:10.1007/s002110050432.

[12] Schönemann, Peter H. (1966 թ․ մարտ). «A generalized solution of the orthogonal procrustes problem». Psychometrika. 31 (1): 1–10. doi:10.1007/BF02289451.

[13] Markopoulos, PP; Kundu, S; Chamadia, S; Tsagkarakis, N; Pados, DA (2018). Outlier-Resistant Data Processing with L1-Norm Principal Component Analysis. էջ 121. doi:10.1007/978-981-10-6704-4_6. ISBN 978-981-10-6703-7. {{cite book}}: |work= ignored (օգնություն)

[14] Tsagkarakis, Nicholas; Markopoulos, Panos P.; Sklivanitis, George; Pados, Dimitris A. (2018 թ․ հունիսի 15). «L1-Norm Principal-Component Analysis of Complex Data». IEEE Transactions on Signal Processing. 66 (12): 3256–3267. arXiv:1708.01249. Bibcode:2018ITSP...66.3256T. doi:10.1109/TSP.2018.2821641.

[toolbox-15] «L1-PCA TOOLBOX». Վերցված է 2018 թ․ մայիսի 21-ին.

[markCodes-16] Markopoulos, PP. «Software Repository». Վերցված է 2018 թ․ մայիսի 21-ին.(չաշխատող հղում)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]