Nhãn

This is default featured slide 1 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

This is default featured slide 2 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

This is default featured slide 3 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

This is default featured slide 4 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

This is default featured slide 5 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

Thứ Sáu, 3 tháng 11, 2017

BÀI TOÁN CỰC ĐẠI HÓA ẢNH HƯỞNG TRÊN MẠNG XÃ HỘI.



Mạng xã hội (MXH), hay gọi là mạng xã hội ảo (tiếng Anh: Social Network) là dịch vụ nối kết các thành viên cùng sở thích trên Internet với nhiều mục đích khác nhau không phân biệt không gian và thời gian. Những người tham gia vào MXH còn được gọi là cư dân mạng.

Người dùng trên mạng có thể giao tiếp với nhau bất chấp khoảng cách địa lý, nhờ đó sự liên kết và tương tác giữa con người với nhau trở nên thường xuyên và nhanh chóng.  Các học giả cho rằng thuật ngữ "xã hội" giải thích cho các tính năng giống như một xã hội thực của mạng.
Một MXH thông thường có những tính năng như: chat, e-mail, phim ảnh, voice chat, chia sẻ file, blog và xã luận. Có nhiều cách để các thành viên tìm kiếm bạn bè, đối tác đó là: dựa theo các nhóm (như tên trường hoặc tên thành phố), dựa trên thông tin cá nhân (như địa chỉ e-mail hoặc screen name), dựa trên sở thích cá nhân (như thể thao, phim ảnh, sách báo, hoặc ca nhạc), lĩnh vực quan tâm (nhu kinh doanh, mua bán). Qua e-mail và tin nhắn tức thời, các cộng đồng trực tuyến được tạo ra để mọi người có thể dễ dàng trao đổi thông tin với nhau. Nhờ đó, MXH có thể kết nối mọi người, chia sẻ sở thích và hoạt động không phân biệt chế độ chính trị, kinh tế và khoảng cách địa lý.

Trong hai thập niêm vừa qua, các mạng xã hội trực tuyến đã cung cấp một nền tảng mạnh mẽ cho sự tương tác, truyền thông cho hàng tỷ người dùng.  Nhờ có chúng, người dùng có thể đăng tin, nhận thông tin và chia sẻ thông tin với nhau bất chấp khoảng cách địa lý. Có rất nhiều người dùng đã tích hợp các trang mạng xã hội phổ biến vào đời sống thường ngày của họ và coi chúng như các nguồn tin chính thức của họ. Chẳng hạn, thông tin Bin Laden bị giết được đăng tải trên Twitter trước khi chính phủ Mỹ chính thức tuyên bố trên các phương tiện truyền thông \cite{news_bld}.  Thêm vào đó, các thông tin trên mạng xã hội có thể ảnh hưởng lớn đến đời sống trong thế giới thực đặc biệt là các xu hướng chính trị xã hội. Ví dụ, Facebook và Twitter có ảnh hưởng lớn trong cuộc bầu cử ở mỹ năm 2008  và sự kiện mùa xuân Arap năm 2010 \cite{us2008, ar2010}.

Trong thực tế để những thông tin có ích được lan truyền trên các MXH một cách hiệu quả cũng như hạn chế các thông tin xấu phát tán, chúng ta cần có những chiến lược nhằm quản lý, điều khiển hay định hướng thông tin để mạng xã hội mang lại nhiều lợi ích cho cộng đồng người dùng hơn nữa.  Trong luận án này, tác giả sẽ tập trung vào hai lớp bài toán sau:
\begin{itemize}
\item Tối ưu trong lan truyền thông tin tốt trên MXH
\item Ngăn chặn thông tin sai lệch và tin đồn trên MXH.
\end{itemize}
Trong các phần tiếp theo, tác giả trình bày tổng quan tình hình nghiên cứu về hai lớp bài toán trên, từ đó rút ra định hướng, phương hướng nghiên cứu của luận án. Ở Việt Nam, theo hiểu biết của tác giả chưa có công trình nghiên cứu nào về các vấn đề trên. Do vậy, tác giả xin trình bày những nghiên cứu liên quan trên thế giới.
\subsection{Bài toán ảnh hưởng cực đại trên mạng xã hội}
Một trong những đặc tính quan trong của mạng xã hội đó là nó cho phép thông tin được lan truyền nhanh chóng. Đặc tính này mang lại nhiều lợi ích cho người dùng trên cộng đồng người dùng trên MXH. Ví dụ, người dùng có thể phát tán các thông tin cho các mục đích như: Tạo ảnh hưởng trong bầu cử, Tiếp thị lan truyền  (viral marketting), vv... Xuất phát từ thực tế trên, một trong các bài toán được các nhà khoa học quan tâm, nghiên cứu rộng rãi là bài toán Cực đại ảnh hưởng \textit{(Influence Maximization-IM)} trên MXH. Bài toán này  xuất phát từ nhu cầu thực tiễn khi cần chọn một số lượng $k$ người dùng (giới hạn nguồn nhân lực) để khởi tạo quá trình lan truyền hoặc bắt đầu ảnh hưởng (gọi là tập hạt giống- seed set) sao cho số người bị ảnh bởi thông tin lan truyền là cực đại. Bài toán này có ý nghĩa lớn trong hoạt động tiếp thị (marketing) đối với các hoạt động kinh doanh trên MXH hiện nay.

Bài toán IM được Kempe và các cộng sự \cite{kem03} lần đầu tiên mô hình hóa và phát biểu trên mô hình toán học vào năm 2003 tại hội nghị KDD. Trong nghiên cứu này Kempe \cite{kem03} đã đưa ra hai mô hình lan truyền thông tin trên MXH đó là: mô hình ngưỡng tuyến tính (Linear Threshold- LT) và mô hình bậc độc lập (Independent Cascade- IC), trong hai mô hình này, ông chỉ ra bài toán IM là bài toán NP-Khó. Đồng thời nhóm tác giả cũng chứng minh được hàm ảnh hưởng (hàm mục tiêu) có tính chất \textit{submodular}, tức là
\begin{align}
\sigma(S \cup \{u\})- \sigma(S) \geq  \sigma(T \cup \{u\})- \sigma(T)
\end{align}
Với $\sigma(.)$ là hàm tính ảnh hưởng $S \subseteq T$ là tập các đỉnh, $u \notin T$. Dựa trên tính chất này, các tác giả đưa ra một thuật toán tham lam có tỷ lệ xấp xỉ là $1- 1/e$. Nghiên cứu này sau đó nhận được nhiều sự quan tâm trong hơn một thập niên trở lại đây. Chen và các cộng sự \cite{chen10,chen12,chen10LT} đã chứng minh việc tính toán chính xác hàm ảnh hưởng trong hai mô hình IC và LT thuộc lớp bài toán \#P- khó, chính vì vậy, hướng tiếp cận cổ điển để áp dụng bài thuật toán tham lam cho bài toán này là sử dụng phương pháp mô phỏng Mote-Carlo để xấp xỉ hàm mục tiêu, phương pháp này cho tỷ lệ xấp xỉ là $1- 1/e- \epsilon$ với $\epsilon$ là sai số của Mote-Carlo.

Sau đó, Leskovec và các cộng sự trong \cite{leskovec07} đề xuất chiến thuật  lazzy forward để cải tiến tốc độ của thuật toán tham lam. Ý tưởng của thuật toán này loại bỏ những đỉnh làm hàm muc tiêu tăng chậm bằng cách sử dụng tính chất submodular. Thực nghiệm chỉ ra thuật toán của Leskovec chạy nhanh hơn thuật toán tham lam tới 700 lần trong khi kết quả đạt được gần như nhau.

Để mở rộng bài toán cho các MXH kích cỡ lớn, Chen \cite{chen10,chen12} sử dụng phương pháp xấp xỉ ảnh hưởng dựa trên việc xây dựng cây ảnh hưởng cực đại để thiết kế thuật toán heuristic có tên là PMIA trên mô hình IC. Đối với mô hình ngưỡng tuyến tính, Chen \cite{chen10LT} và các cộng sự cũng sử dụng phương pháp trên có kết hợp với việc xây dựng đồ thị có hướng không chu trình (directed acyclic graph - DAG) để xấp xỉ hàm ảnh hưởng. Kết quả thực nghiệm cho thấy các thuật toán được đề xuất trong \cite{chen10,chen10LT} có thể áp dụng với các mạng lớn và cho kết quả khả quan so với thuật toán CELF. Ngoài ra có một số phương pháp khác để tìm kiếm lời giải cho bài toán IM như Simpath \cite{simpath}, Degree discount...

Một bước tiến lớn trong việc tìm lời giải của bài toán IM trong những năm gần đây là ý tưởng của  Borg và các cộng sự \cite{borg}. Các tác giả sử dụng phương pháp xây dựng đồ thị đảo ngược trong trong việc lấy mẫu Moter-Carlo, sau đó chuyển bài toán IM trên mô hình lan truyền thông tin có tính ngẫu nhiên (IC và LT) về bài toán Tập phủ cực đại (Maximum Coverage) trên tập vũ trụ xác định. Bổ để then chỗ để áp dụng phương pháp này là:
\begin{lema} Cho đồ thị $G = (V,E,w)$ và một siêu cạnh $E_j$ trên trên đồ thị mẫu sinh ra từ $G$. Với mỗi tập $S\in V$, ta có:
\begin{align}
 \mathbb{I}(S) =n\Pr[S cover S_j]
\end{align}
\end{lema}
Các tác giả đưa ra thuật toán có tỷ lệ xấp xỉ $1-1/e-\epsilon$ với xác xuất ít nhất là $1-n^{-l}$. Trong đó số lần lấy mẫu là $144(m+n) \epsilon^{-3} \log(n)$. Độ phức tạp của thuật toán này là $\mathcal{O}(kl^2(m+n) \log^2n/\epsilon^3)$

Tiếp theo nghiên cứu này, Tang và các cộng sự \cite{tang14,tang15} thiết kế các thuật toán với tỷ lệ xấp xỉ tương tự nhưng số lần lấy mẫu giảm xuống nên có thể áp dụng cho các đồ thị lớn. Độ phức tạp của thuật toán giảm xuống là $\mathcal{O}((k+l)(m+n) \log^2n/\epsilon^2)$.

Nghiên cứu mới nhất sử dụng phương pháp này với chiến lược dừng lại lấy mẫu (Stop and stare) kết hợp với ước lượng độ chính xác của lời giải được Hung T. Nguyen \cite{ssa} và các cộng sự công bố ở hội nghị SIGMOD 2016.

Một số tác giả đề xuất giải quyết bài toán IM trong các ràng buộc khác nhau hoặc đề xuất các biến thể khác nhau của IM. Huy Huyen \cite{huy2013} và các cộng sự đề xuất bài toán Budgeted Imfluence Maximization với chi phí khác nhau đối với việc chọn một đỉnh trong tập hạt giống. Zhang giải quyết bài toán tối đa hóa việc lan tuyền ý kiến, quan điểm thay vì ảnh hưởng \cite{zhang13}, họ sử dụng mô hình ngưỡng xác định để mô hình hóa việc lan truyền quan điểm trên MXH.
\subsection{Ngăn chặn thông tin sai lệch và tin đồn trên mạng xã hội}
Thật không may, đặc tính phát tán thông tin nhanh chóng của MXH có thể được sử dụng để lan truyền thông tin sai lệch hoặc các thông tin tiêu cực tới một bộ phận lớn cộng đồng người dùng. Điều này dẫn tới các thiệt hại lớn về kinh tế cũng như ảnh hưởng tiêu cực đến cộng đồng người dùng trong đời sống thực. Ví dụ, thông tin về việc tổng thống Obama bị ám sát đã gián tiếp gây ra thiệt hại 136.5 tỷ đô la đến thị trường tài chính \cite{news1}, hay thông tin giả trên các mạng xã hội có ảnh hưởng đáng kể đến cuộc bầu cử ở Mỹ năm 2016 \cite{news3}. Để các MXH có thể phục vụ người dùng như một kênh thông tin đáng tin cậy, cần có những giải pháp hiệu quả để phát hiện nguồn phát tán; và hạn chế sự lây lan của chúng. Đây cũng là một chủ đề nóng được quan tâm trong thập trong thập niên vừa qua.
Tài liệu tham khảo
\bibitem{bhagat12} Bhagat S, Goyal A, Lakshmanan LV (2012) Maximizing product adoption in social networks. In: Proceedings of the fifth ACM international conference on Web search and data mining, Seattle, Washington, pp 603-612
\bibitem{bud11} Budak C, Agrawal D, Abbadi AE (2011) Limiting the spread of misinformation in social networks, In: Proceedings of the 20th International Conference on World Wide Web, WWW '11, ACM, New York, NY, USA. doi:10.1145/1963405.1963499

\bibitem{borg} C. Borgs, M. Brautbar, J. Chayes, and B. Lucier (2014) Maximizing social influence in nearly optimal time, in SODA. SIAM, 2014, pp. 946-957.
\bibitem{song15} Chonggang Song, Wynne Hsu, and Mong Li Lee. Mining brokers in dynamic social networks. In ACM CIKM, pages 523–532, 2015.
\bibitem{song15_imu} Chonggang Song, Wynne Hsu, and Mong Li Lee. Node immunization over infectious period. In ACM CIKM, pages 831–840, 2015.
\bibitem{song16}  Chonggang Song, Wynne Hsu, and Mong Li Lee. Targeted influence maximization in social networks. In ACM CIKM, pages 1683–1692, 2016.
\bibitem{song17}  Chonggang Song, Wynne Hsu, and Mong Li Lee. Temporal influence blocking: Minimizing the effect of misinformation in social networks. In IEEE ICDE,
2017.
\bibitem{tang14} Y. Tang, X. Xiao, and Y. Shi, “Influence maximization: Nearoptimal
time complexity meets practical efficiency,” in SIGMOD.
ACM, 2014, pp. 75–86.

\bibitem{tang15} Y. Tang, Y. Shi, and X. Xiao, “Influence maximization in near-linear time: A martingale approach,” in SIGMOD. ACM, 2015, pp. 1539–
1554.

\bibitem{nguyen16} H. T. Nguyen, T. N. Dinh, and M. T. Thai (2016) Cost-aware targeted
viral marketing in billion-scale networks, in INFOCOM. IEEE,
2016, pp. 1–9.

\bibitem{ssa} Hung T. Nguyen,  My T. Thai, and Thang N. Dinh (2016) SIGMOD '16 Proceedings of the 2016 International Conference on Management of Data
Pages 695-710

\bibitem{cha09} Cha M, Mislove A, Gummadi KP (2009) A measurement-driven analysis of information propagation in the Flickr social network. In: Proceedings of the 18th international conference on World wide web, New York, USA, pp 721-730
\bibitem{chen-book} Chen W, Lakshmanan LVS, Castillo C (2013) Information and Influence Propagation in Social Networks. Morgan and Claypool
\bibitem{chen12} Chen W, Lu W, and Zang N (2012) Time-critical influence maximization in social networks with time-delayed diffusion process. In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, Ontario, pp 592-598
\bibitem{chen10}Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, Washington, DC, pp 1029-1038
\bibitem{chen10LT} Chen W, Wang C, Wang Y (2010) Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In: Proceedings of the 2010 IEEE International Conference on Data Mining, Washington, pp 88-97
\bibitem{chris10} Christakis NA, Fowler JH (2010) Social network sensors for early detection of contagious outbreak. PloS one. doi:10.1371/journal.pone.0012948
\bibitem{news2} Coursey D (2009) Swine Flu Frenzy Demonstrates Twitter's Achilles Heel. PCWorld Web. http://www.pcworld.com/businesscenter/article/163920/
\bibitem{cui13} Cui P, Jin S, Yu L, Wang F, Zhu W, Yang S (2013) Cascading outbreak prediction in network: a data-driven approach. In: Proceeding of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, Chicago, pp 901-909
\bibitem{propa} Domingos P,Richardson M (2001) Mining the network value of customers. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, USA, pp 57-66
\bibitem{news1} Domm P (2013) False Rumor of Explosion at White House Causes Stocks to Briefly Plunge; AP Confirms Its Twitter Feed Was Hacked CNBC. http://www.cnbc.com/id/100646197(2013). Accessed 23 April 2013
\bibitem{news3}Gentzkow M (2017) Social Media and Fake News in the 2016 Election.Stanford Web. http://news.stanford.edu/2017/01/18/stanford-study-examines-fake-news-2016-presidential-election/ (2017). Accessed 24 June 2017
\bibitem{simpath}Goyal A, Lu W, Lakshmanan LVS (2012) SIMPATH: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model. In: Proceeding IEEE 11th International Conference on Data Mining,  Vancouver, BC, pp 211-220
\bibitem{he11} He X, Song G, Chen W, Jiang Q (2011) Influence blocking maximization in social networks under the competitive linear threshold model technical report, CoRR abs/1110.4723
\bibitem{us2008} Hughes AL, Palen L (2009) Twitter adoption and use in mass convergence and emergency events. International Journal of Emergency Management 6(3):248-260
\bibitem{leskovec07} Leskovec J, Adamic LA, Huberman BA (2007) The dynamics of viral marketing. ACM Transactions on the Web. doi:10.1145/1232722.1232727
\bibitem{kem03} Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of  influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. doi:10.1145/956750.956769
\bibitem{khalil} Khalil EB, Dilkina B,Song L (2014) Scalable diffusion-aware optimization of network topology. In: Proceedings of the  ACM SIGKDD international conference on Knowledge discovery and data mining, New York, pp. 1226-1235
\bibitem{bg_max} Khuller S, Moss A, Naor JS (1999) The budgeted maximum coverage problem. Information Processing Letters 70(1):39-45
\bibitem{kimura2} Kimura M, Saito K, Motoda H (2009) Blocking links to minimize contamination spread in a social network. In: ACM Transactions on Knowledge Discovery from Data. doi:10.1145/1514888.1514892
\bibitem{kimura}Kimura M,Saito K, Motoda H (2008) Solving the contamination minimization problem on networks for the linear threshold model.: In: Pacific Rim International Conference on Artificial Intelligence. doi: 10.1007/978-3-540-89197-0\_94
\bibitem{ivan} Kottasová I (2017) Facebook targets 30,000 fake accounts in France. CNN media Web. http://money.cnn.com/2017/04/14/media/facebook-fake-news-france-election/index.html.Accessed 24 June 2017
\bibitem{won} Kwon S, Cha M, Jung K, Chen W, and Wang Y (2013) Prominent features of rumor propagation in online social media. In: Proceeding of IEEE 13th International Conference on  Data Mining. doi: 10.1109/ICDM.2013.61
\bibitem{ore} Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. In Proceeding of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. doi:10.1145/1081870.1081893
\bibitem{gnu} Leskovec J, Kleinberg J, Faloutsos C (2007) Graph Evolution: Densification and Shrinking Diameters. ACM Transactions on Knowledge Discovery from Data 1(1)
\bibitem{Lui} Liu B, Cong G, Xu D, Zheng Y (2012) Time Constrained Influence Maximization in Social Networks. In: Proceeding of IEEE 12th International Conference on Data Mining, Brussels, Belgium, pp 439-448
\bibitem{lu_dlt} Lu z, Zhang W, Wu W, Kim J ,Fu B (2012) Complexity of influence maximization problem in the deterministic linear threshold model. Journal of Combinatorial Optimization 24: 374-378
\bibitem{huy2013} Nguyen H,  Zheng R (2013) On Budgeted Influence Maximization in Social Networks. IEEE Journal on Selected Areas in Communications 31(6): 1084-1094
\bibitem{nguyen2012} Nguyen NP, Yan G, Thai MT (2013) Analysis of misinformation containment in online social networks. Computer Networks 57: 2133–2146
\bibitem{qaz} Qazvinian V, Rosengren E, Radev DR, Mei Q (2011) Rumor has it: Identifying misinformation in microblogs. In: Proceedings of the Conference on Empirical Methods in Natural Language Processing, Edinburgh, United Kingdom, pp. 1589-1599
\bibitem{epi} Richardson M and Agrawal R, Domingos P (2003)Trust Management for the Semantic Web. In: Proceeding of International Semantic Web Conference. doi:10.1007/978-3-540-39718-2\_23
\bibitem{news_bld}Sutter JD (2017) How bin Laden news spread on Twitter. CNN Web. http://edition.cnn.com/2011/TECH/social.media/05/02/osama.bin.laden.twitter/index.html. Accessed 23 June 2017
\bibitem{news4} The Guardian Web (2011) Fox News's hacked Twitter feed declares Obama dead. . https://www.theguardian.com/news/blog/2011/jul/04/fox-news-hacked-twitter-obama-dead. Accessed 24 June 2017
\bibitem{vali} Valiant LG (1979) The complexity of enumeration and reliability problems. SIAM Journal on Computing 8(3):410-421
\bibitem{ar2010} Wolfsfeld G, Segev E, Sheafer T (2013) Social media and the Arab Spring: Politics comes first. The International Journal of Press/Politics 18(2): 115-137
\bibitem{twit} Yadron D (2017) Twitter deletes 125,000 Isis accounts and expands anti-terror teams. The Guardian Web. https://www.theguardian.com/technology/2016/feb/05/twitter-deletes-isis-accounts-terrorism-online. Accessed 24 June 2017
\bibitem{zhang16} Zhang H, Alim M,  Li X, My TT, Nguyen H (2016) Misinformation in Online Social Networks: Catch Them All with Limited Budget. ACM Transactions on Information Systems 34 (3)
\bibitem{zhang13} Zhang H, Dinh TN, Thai MT (2013) Maximizing the spread of positive influence in online social networks. In: Proceeding IEEE 33rd International Conference on Distributed Computing Systems, Philadelphia, PA, pp 317-326
\bibitem{zhang_mis16} Zhang H, Kuhnle A, Zhang H, Thai MT (2016) Detecting misinformation in online social networks before it is too late. In: Proceeding IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). doi: 10.1109/ASONAM.2016.7752288
\bibitem{yao16}Zhang Y ,Adigay A, Saha S,Vullikanti A,Prakash A (2016)Near-optimal Algorithms for Controlling Propagation at Group Scale on Networks. IEEE Transactions on Knowledge and Data Engineering. doi: 10.1109/TKDE.2016.2605088
\bibitem{dava} Zhang Y and Prakash B (2015) Dava : Data-Aware Vaccine Allocation over Large Networks. ACM Transactions on Knowledge Discovery from Data. doi:10.1145/2803176
\bibitem{yao14} Zhang Y, Prakash BA (2014) Scalable Vaccine Distribution in Large Graphs given Uncertain Data. In: Proceeding of the ACM International Conference on Information and Knowledge Management, Shanghai, pp 1719-1728

\bibitem{thangToN} T. N. Dinh, H. Zhang, D. T. Nguyen, and M. T. Thai.: Cost-effective
Viral Marketing for Time-critical Campaigns in Large-scale Social
Networks, IEEE/ACM Transactions on Networking (ToN), pages 2001
– 2011, 2013.

Thứ Sáu, 21 tháng 7, 2017

Giới thiệu về IPython Notebook – Sự kết hợp hoàn hảo giữa Python và LaTeX

Trong bài viết này, mình sẽ giới thiệu những thông tin cơ bản nhất về IPython Notebook. Bài viết này phù hợp với những ai chưa hề biết đến IPython Notebook và muốn tìm hiểu về công cụ này.

IPython Notebook là gì?

Chắc hẳn chúng ta ai cũng biết Python – một ngôn ngữ lập trình rất phổ biến trong thời gian gần đây vì sự mạnh mẽ và tiện dụng của nó. Ipython Notebook trang bị thêm cho Python một công cụ hữu hiệu để ghi chú, soạn thảo văn bản một cách chuyên nghiệp. Bạn hoàn toàn có thể định dạng văn bản, chèn hình ảnh, soạn thảo văn bản một cách tự động như LaTeX (nếu bạn chưa biết về LaTeX có thể search Google). Nói chung, với IPython Notebook bạn sẽ có một file code python bình thường có thể biên dịch và chạy được nhưng có định dạng văn bản đẹp như một bài báo của một hội nghị khoa học.
ipython-f21
Giao diện của IPython Notebook trên trình duyệt Nguồn: http://blog.cloudera.com/

1. Download và cài đặt

Để có thể sử dụng IPython Notebook, bạn cần download anaconda tại đâyAnaconda là một bản phân phối của Python có chứa các gói giúp bạn lập trình về các lĩnh vực: toán học, khoa học, phân tích dữ liệu… và anaconda hoàn toàn miễn phí. Sau khi download xong các bạn cài đặt như bình thường.
Sau khi cài xong, các bạn mở IPython Notebook lên. Đầu tiên, mở công cụ PowerShell của Windows lên bằng cách dùng tổ hợp phím alt + R sau đó gõ từ khóa powershell và sau đó nhấn Enter. Tại cửa sổ PowerShell, gõ lênh ipython notebook rồi Enter.
Màn hình PowerShell
Màn hình PowerShell
Đợi khoảng 2s sau, IPython Notebook sẽ được mở trên trình duyệt mặc định của bạn với tab Home. Nếu muốn mở bằng trình duyệt khác, chỉ cần copy url và dán vào trình duyệt nào bạn muốn.
Tại tab Home này bạn sẽ thấy rất nhiều file và thư mục, đó chính là những gì nằm trong thư mục lúc bạn gọi lệnh ngoài PowerShell. Bây giờ, hãy chọn New → Python 2 để tạo một file mới. Tập tin IPython Notebook có phần mở rộng là *.ipynb, phần sau mình sẽ nói về cấu trúc của file *.ipynb này.

2. Cấu trúc của file *.ipynb

Mỗi tập tin IPython Notebook được cấu tạo từ các cell. Ở mỗi cell bạn có thể viết và thực thi câu lệnh. Như đã biết IPython Notebook mạnh mẽ ở khả năng viết code và soạn thảo văn bản do đó có 2 loại cell tương ứng với tên gọi là Code Cell  Markdown Cell.
Markdown Cell và Code Cell
Markdown Cell và Code Cell
Khi tạo một tập tin mới, một cell được tạo sẵn (cell có dòng In[]: phía trước) đó là Code cell, để có thể chuyển sang Markdown cell, bạn chỉ cần nhấn Esc mất con trỏ nhấp nháy sau đó nhấn phím M. Để chuyển ngược lại sang Code Cell, bạn hãy nhấn phím Y. Đó là 2 trong số rất nhiều thao tác thường xuyên sử dụng, bạn hãy nhấn phím H để xem tất cả các phím tắt.
Các phím tắt trong IPython Notebook
Các phím tắt trong IPython Notebook

3. Thực hành

Sau đây mình sẽ demo một vài cú pháp thông dụng cho các bạn dễ nắm bắt, để nắm rõ ràng và đầy đủ bạn hãy tìm hiểu thêm tại đây nhé!
Nào, hãy bắt đầu bằng việc tạo một cell mới bằng cách nhấn phím B và chuyển cell đó thành Markdown Cell bằng cách nhấn phím M. Bây giờ hãy gõ vào cell này dòng: #Heading, bạn đã thấy điều gì khác biệt chưa?? Đó chính là cú pháp tạo heading cho văn bản, để tạo heading cấp 2,3 bạn hãy thử thêm vài dấu # vào trước thay vì chỉ 1 dấu #.
Cú pháp tạo heading
Cú pháp tạo heading
Để hiện thị heading đó lên bạn hãy nhấn tổ hợp phím Ctrl + Enter, đây cũng là cú pháp để thực thi (run) một cell bất kỳ kể cả Code Cell.
Markdown Cell sau khi run
Markdown Cell sau khi run
Để có thể thực thi toàn bộ cell, bạn hãy chọn Cell → Run All.

Thứ Tư, 12 tháng 10, 2016

Submodular Function (Phần 1)

Xin phép được đăng lại bài của cô Thái Trà My để mọi người tham khảo ak!
Submodular function được định nghĩa như sau:
Định nghĩa 1: Cho một set function f trên mọi tập con của tập E. Hàm f được gọi là submodular function khi với bất kỳ hai tập con A, B \subseteq E, ta có:
f(A) + f(B) \ge f(A \cup B) + f(A \cap B)
Ví dụ: f(A) = |A| là một submodular function.
Định nghĩa trên còn tương đương với định lý sau:
Định lý 1: Xét một set function f. Nếu f là submodular function thì với mọi A \subseteq B \subseteq E và x \in E \setminus B, ta có:
f(A \cup {x}) - f(A) \ge f(B \cup {x}) - f(B)
Định lý 1 ngụ ý rằng thêm một phần tử vào tập A sẽ có lợi hơn thêm nó vào mộ tập lớn hơnA. Nghĩa là, càng sớm càng tốt.
Tại sao chúng ta lại quan tâm đến submodular function? Bởi chúng đóng một vai trò rất quan trọng trong toán tối ưu và thuật toán xấp xỉ (approximation algorithms)
Có rất nhiều phương pháp trong thuật toán xấp xỉ, từ thuật toán tổ hợp (combinatorics) tới quy hoạch tuyến tính (linear programming) và semi-definite programming. Trong đó, thuật toán tham lam (greedy algorithms) là một trong những thuật toán phổ biến nhất và tính ứng dụng rất cao bởi độ đơn giản của nó cùng với độ phức tạp thấp về thời gian.
Tuy nhiên, phân tích tỉ lệ xấp xỉ (approximation ratio) của thuật toán tham lam vô cùng tricky và thú vị. Nếu hàm tham lam (greedy function) của một thuật toán tham lam là submodular function thì việc phân tích tỉ lệ xấp xỉ trở nên đơn giản hơn nhiều. Chúng ta hãy xét một vài ví dụ sau đây.
Set Cover: Cho trước một tập vũ trụ U có n phần tử và một họ \mathcal{C} tập con của U. Tìm họ con nhỏ nhất \mathcal{C}' \subseteq \mathcal{C} phủ tất cả các phần tử của U.
Define f(\mathcal{C}') = |\bigcup_{S \in \mathcal{C}'}S| (i.e. tổng số phần tử trong \mathcal{C}'). Xét thuật toán tham lam sau:
Algorithm 1:
\mathcal{C}' \leftarrow \emptyset
while |U| > f(\mathcal{C}') do
\hspace{10pt} choose S \in \mathcal{C} to maximize f(\mathcal{C}' \cup S)
\hspace{10pt} \mathcal{C}' \leftarrow \mathcal{C}' \cup S
return \mathcal{C}'
Trong Algorithm 1, cho mỗi iteration, chúng ta chọn một tập con sao cho phủ được nhiều phần tử chưa được phủ tại thời điểm đó. Chúng ta sẽ chứng minh rằng Algorithm 1 có tỉ lệ xấp xỉ là (1 + \ln n) với n = |U|. (Chú ý rằng với bài toán minimization, thì tỉ lệ xấp xỉ \rho được định nghĩa như sau: \rho = opt/sol trong đó opt là giá trị tối ưu và sol là giá trị lời giải.)
Trước tiên, chúng ta chứng minh hai bổ đề sau:
Bổ đề 1: Hàm f là submodular function  monotone increasing.
Chứng minh: Bài tâp.
\Box
Bổ đề 2: Giả sử  S_1, S_2, \dots, S_k được chọn bởi Algorithm 1. Ký hiệu \mathcal{C}_i = \{ S_1, S_2, \dots, S_i\} và opt là giá trị tối ưu (optimal value), ta có:
f(\mathcal{C}_{i+1}) \ge f(\mathcal{C}_i) + (n - f(\mathcal{C}_i))/opt
Chứng minh: Ký hiệu \Delta_Xf(A) = f(A \cup X) - f(A). Gọi \mathcal{C}^* = \{X_1, X_2, \dots, X_{opt}\} là lời giải tối ưu (optimal solution). Và ký hiệu \mathcal{C}_j^* = \{X_1, X_2, \dots, X_j\}. Tại mỗi iteration i, theo Algorithm 1, ta có:
\Delta_{S_{i+1}} f(\mathcal{C}_i) \ge \Delta_{X_{j+1}} f(\mathcal{C}_i) \forall j, 0 \le j \le opt - 1
Suy ra,
\Delta_{S_{i+1}}f(\mathcal{C}_i) \ge (\sum_{0 \le j \le opt -1} \Delta_{X{j+1}} f(\mathcal{C}_i))/opt
\ge (\sum_{0 \le j \le opt -1} \Delta_{X{j+1}} f(\mathcal{C}_i \cup \mathcal{C}_j^*))/opt (theo Bổ đề 1)
Do đó, ta có:
\Delta_{S_{i+1}}f(\mathcal{C}_i) \ge (f(\mathcal{C}_i \cup \mathcal{C}^*) - f(\mathcal{C}_i))/opt = (n - f(\mathcal{C}_i))/opt
\Box
Từ bổ đề 2, chúng ta dễ dàng chứng minh Định lý sau:
Định lý 2: Algorithm 1 có tỉ lệ xấp xỉ là (1 + \ln n)
Chứng minh: Theo Bổ đề 2, ta có:
n - f(\mathcal{C}_{i+1})  \le (n - f(\mathcal{C}_i))(1 -1/opt) \le (n - f(\mathcal{C}_{i-1}))(1 -1/opt)^2
\le \dots \le n(1-1/opt)^{i+1}
Chọn i là số nguyên dương lớn nhất thỏa mãn: opt \le n - f(\mathcal{C}_i).  Ta có:
k - i \le opt, nên opt \le n(1 - 1/opt)^i \le n e^{-i/opt} (vì 1 + x \le e^x)
Do đó, i \le opt \ln(n/opt). Suy ra k \le opt + 1 \le opt(1 + \ln(n/opt))
\Box
Bây giờ, giả sử mỗi tập con của U có một khối lượng và ta muốn tìm họ con với khối lượng nhỏ nhất.  Ta cần phải làm gì?
Weighted Set Cover: Cho trước một tập vũ trụ U có n phần tử , một họ \mathcal{C} tập con của U với weight function w: \mathcal{C} \rightarrow \mathbb{Q}^+. Tìm họ con có khối lượng nhỏ nhất \mathcal{C}' \subseteq \mathcal{C}phủ tất cả các phần tử của U.
Sử dụng hàm f ở trên, thay đổi Algorithm 1 một tí, ta có:
Algorithm 2:
\mathcal{C}' \leftarrow \emptyset
while |U| > f(\mathcal{C}') do
\hspace{10pt} choose S \in \mathcal{C} to maximize \Delta_S f(\mathcal{C}')/w(S)
\hspace{10pt} \mathcal{C}' \leftarrow \mathcal{C}' \cup S
return \mathcal{C}'
Định lý 3: Algorithm 2 có tỉ lệ xấp xỉ là (1 + \ln n)
Chứng minh: Bài tập.
\Box
Tổng quát hóa, ta có:
Bài toán tổng quát : Xét một hàm monotone increasing và submodular function f trên tất cả tập con của tập E và một cost function c: E \rightarrow \mathbb{Q}^+. Định nghĩa \Omega(f) = \{A \ | \ \forall x \in E, \Delta_{\{x\}}f(A) = 0\}. Xét bài toán sau:
minimize c(A) = \sum_{x \in A} c(x) sao cho A \in \Omega(f)
Lời giảiĐể giải bài toán tổng quát trên, ta có thuật toán tham lam như sau:
Algorithm 3:
A \leftarrow \emptyset
while  tồn tại x \in E sao cho \Delta_{\{x\}} f(A) > 0 do
\hspace{10pt} choose x \in E to maximize \Delta_{\{x\}} f(A)/c(x)
\hspace{10pt} A \leftarrow A \cup \{x\}
return A
Định lý 4: Nếu f(\emptyset) = 0f là hàm số dương (integer function), monotone increasing, submodular function, và c(x) \ge 0, \forall x \in E, Algorithm 3 sẽ có tỉ lệ xấp xỉ là (1 + \ln \gamma) với \gamma = \max_{x \in E} f(\{x\}).
Chứng minh: Giả sử x_1, x_2, \dots, x_k là các phần tử được Algorithm 3 chọn theo thứ tự như vậy. Ký
hiệu A_i = \{x_1, \dots, x_i\} và r_i = \Delta_{x_i}f(A_{i - 1}).
Gọi A^* = \{y_1, \dots, y_h\} là lời giải tối ưu. Với mỗi y_e \in A^*, đặt z_{ei} = \Delta_{ye}f(A_{i-1}). Cho đơn giản, ký hiệu c_i = c(x_i) và w(e) = \sum_{i=1}^{k-1}(z_{ei} - z_{e, i+1})\frac{c_i}{r_i} + z_{ek}\frac{c_k}{r_k} = \frac{c_1}{r_1}z_{e1} + \sum_{i=2}^k(\frac{c_i}{r_i}-\frac{c_{i - 1}}{r_{i -1}})z_{ei}
Trước tiên, ta chứng minh hai mệnh đề sau:
Mệnh đề 1: c(A) \le \sum_{y_e \in A^*}w(e)
Để chứng minh Mệnh đề 1, ta có:
c(A) = \sum_{i=1}^k \frac{r_i}{r_i}c_i = \sum_{i=1}^{k-1}\frac{c_i}{r_i}(\sum_{j=1}^k r_j - \sum_{j=i+1}^{k}r_j) + \frac{c_k}{r_k}\sum_{j=k}^k r_j
= \frac{c_1}{r_1} \sum_{j=1}^k r_j + \sum_{i=2}^k (\frac{c_i}{r_i} - \frac{c_{i-1}}{r_{i-1}}) \sum_{j=i}^k r_j
Hơn nữa, hàm f là submodular và monotone increasing, ta có:
r_1/c_1 \ge r_2/c_2 \ge \dots \ge r_k/c_k
Vì vậy, để chứng minh Mệnh đề 1, chúng ta chỉ cần chứng minh
\sum_{j=1}^k r_j \le \sum_{y_e \in \mathcal{C}^*} z_{ei} \ \forall i = 1, \dots, k là xong.
Ta có,
\sum_{j=i}^k r_j = f(A) - f(A_{i-1}) = f(A^*) - f(A_{i-1})
= f(A^* \cup A_{i-1}) - f(A_{i-1}) = \Delta_{A^*}f(A_{i-1})
\le \sum_{y_e \in A^*} \Delta_{y_e}f(A_{i-1}) = \sum_{y_e in A^*} z_{ei}
Vậy là chúng ta đã chứng minh xong Mệnh đề 1.
Mệnh đề 2: \forall y_e \in A^*, ta có:
w(e) \le c(y_e) \sum_{i=1}^\gamma \frac{1}{i}
Chứng minh Mệnh đề 2 khá đơn giản. Chú ý rằng \frac{c_i}{r_i} \le \frac{e(y_e)}{z_{ei}} (theo Algorithm 3} và z_{ei} \ge z_{e, i+1} (f là monotone increasing và submodular)
Vì vậy, chúng ta dễ dàng có:
w(e) = \sum_{i=1}^{k-1}(z_{ei} - z_{e,i+1}) \frac{c_i}{r_i} + z_{ek}\frac{c_k}{r_k}
\le \sum_{i=1}^{k-1}(z_{ei} - z_{e,i+1}) \frac{c(y_e)}{z_{ei}} + z_{ek}\frac{c(y_e)}{z_{ek}} \le c(y_e) \sum_{i=1}^{z_{e1}} \frac{1}{i}
Có được bước cuối cùng vì z_{ei} là số nguyên. Chú ý rằng z_{e1} \le \gamma \ \forall y_e \in A^*. Nên từ hai mệnh đề, ta chứng minh xong định lý 4.
\Box
Ghi chú: Nếu f(\emptyset) \neq 0, chúng ta đặt g(A) = f(A) - f(\emptyset). Lúc đó, g là hàm nguyên, monotone increasing, submodular, và g(\emptyset) = 0. Suy ra, \gamma = \max_{x \in E} f(\{x\} - f(\emptyset)).
Vậy cho mỗi bài minimization, nếu ta tìm được hảm f thỏa mãn các điều kiện trên thì ta có một thuật toán xấp xỉ với tỉ lệ 1 + \ln \gamma).

Bài tập:
Bài tập 1: Chứng minh Định lý 1.
Bài tập 2: Chứng minh Bổ đề 1.
Bài tập 3: Trong chứng minh Bổ đề 2, tại bước gần cuối, ta dựa theo Bổ đề 1. Tại sao ta cần f là monotone increasing. Nếu f chỉ là submodular function thì chuyện gì xảy ra?
Bài tập 4: Chứng minh Định lý 3.
Bài tập 5: Nếu f không là hàm số nguyên, thì Định lý 4 sẽ thay đổi như thế nào?
Nguồn: https://thaitramy.wordpress.com/2010/01/11/submodular-function/