Information Theory VS Decision Making VS Optimization etc.

[Flamber]

Ciao a tutti,

devo compilare il piano carriera con degli esami a scelta. Ho delle mie opinioni ovviamente, ma siccome alcuni di questi temi non li ho mai trattati, magari non ho gli strumenti per scegliere. Capisco anche che la risposte "scegli ciò che ti interessa di più" sia la risposta più sensata, ma il mio intento è un altro, è capire cosa scegliereste voi, con le dovute motivazioni (tenendo conto che sono nel contesto di Data Science & Engineering al PoliTo). Le opzioni sono le seguenti, negli "spoiler" trovate gli argomenti principali di ogni corso:

Uno a scelta tra:
1) Computational linear algebra for large scale problems

• Basic linear algebra tools.
• Approximation of data and functions.
• Dense and sparse matrices, matrix operations.
• Eigenvalues and eigenvectors computations: numerical methods and common tools for large scale matrices. Stability and conditioning.
• Vector rotations, orthogonalization, projections.
• Iterative solutions of large scale linear systems.
• Computation and theoretical properties of Singular Value Decomposition (SVD), Lanczos method.
• Randomized SVD.
• Non-negative matrix factorization.
• Generalized inverse matrix and Moore–Penrose inverse.
• Dimensional reduction of a problem and Principal Component Analysis (PCA).
• C/C++ and Python common numerical libraries.

2) Statistical methods in data science

• Review of elementary probability theory and univariate random variables (8 hours)
• Conditional, marginal and joint distributions; conditional expectations (6 hours)
• Important multidimensional distributions (multinormal, multinomial, DAGs) (10 hours)
• Convergence of probability laws and limit theorems (8 hours)
• Sampling distributions and point estimation (12 hours)
• Confidence intervals with applications to basic designs (11 hours)
• Hypothesis testing, including goodness of fit (e.g. chi-square) (11hours)
• Software for statistical analysis (14 hours)

Uno a scelta tra:
1) Decision making and optimization

1. Linear programming: modeling techniques, basic concepts of the Simplex method and duality (10% of the course).
2. Computational complexity: problem classes P, NP, NP-complete, and CoNP-complete (5% of the course).
3. Exact optimization methods: Branch and Bound, Cutting Planes, and Dynamic Programming (20% of the course).
4. Heuristic optimization methods: greedy algorithms, GRASP, Beam Search, meta-heuristics (Tabu Search, Simulated Annealing, Genetic Algorithms, ACO, VNS, RBS), and math-heuristics (30% of the course).
5. Network flow problems: min cost flow and max flow (5% of the course).
6. Decision making under uncertainty: Stochastic Programming with recourse, Measures for Stochastic Programming, Progressive Hedging method (10% of the course).
7. Nonlinear Programming: theoretical conditions for unconstrained and constrained optimization, algorithms for unconstrained and constrained optimization (20%).

2) Information Theory and Applications

Information Theory

1. Entropy of discrete random variables (15 hours)
o Information source
o Information content and measure
o Entropy and relevant inequalities
o Entropy rate of a source
o Markovian source
o Laboratory:
- Computation of entropies
- Test of entropy inequalities
- Computation of entropy rates

2. Source coding (13 hours)
o Fixed-length encoding
o Fixed-to-variable length encoding
o Source code classification
o Kraft inequality
o McMillan theorem
o Shannon theorem for source codes
o Huffman codes
o Laboratory:
- Efficiency of Huffman codes

3. Discrete channels (12 hours)
o Joint and conditional entropies
o Mutual information
o Entropy and mutual information inequalities
o Laboratory:
- Computation of conditional entropies and mutual information
- Test of relevant inequalities
o Markov chain
o Data-Processing Inequality and its interpretation
o Laboratory:
- Verification of the data-processing inequality
o Shannon theorem and the capacity of symmetric channels
o Laboratory:
- Computation of the capacity of a symmetric channel
- Computation of the capacity of a discrete channel
- Blahut-Arimoto algorithm and its implementation

4. Crypto-Information theory and wiretap channels (10 hours)
o Perfect secrecy
o One-time pad
o Maurer cryptosystem
o Unicity distance
o Wiretap channel
o Effective secrecy capacity
o Laboratory:
- Calculation of the effective secrecy capacity

Applications

6. Algorithms for applied information theory (10 hours)
o Viterbi algorithm
o Belief propagation algorithm
o Decision trees
o Laboratory:
- Basic Viterbi algorithm implementation
- Decision tree algorithm implementation

7. Cryptosystems (10 hours)
o Enciphering, authentication, integrity, attacks
o Private key vs. Public key
o Basic enciphering techniques
o Laboratory:
- Basic enciphering, frequency analysis attack

8. Algorithms for cryptography (10 hours)
o Introduction to RSA
o Notions of AES/DES, Blowfish/Twofish
o Hash functions
o Homomorphic encryption and applications to privacy preserving analytics
o Laboratory:
- Basic example of homomorphic encryption

3) Numerical optimization for large scale problems and Stochastic Optimization

• Convex optimization:
- gradient descent method; conjugate gradient method
- Numerical differentiation
- Newton and quasi-Newton methods
- Globalization techniques
- Alternating direction method of multipliers (ADMM)
• Constrained optimization:
- Interior point methods
- Projected gradient method
- Active set
• Stochastic optimization
- Static simulation-based optimization (parametric optimization)
- Dynamic simulation-based optimization (control optimization)

Ognuno di questi esami è composto da una parte teorica ed una parte di laboratorio, che ha il fine di produrre un progetto finale in R / Python / Matlab a seconda del corso. Quali sono secondo voi i corsi più interessanti? Devo dire che in ogni corso c'è almeno un argomento che mi interesserebbe approfondire. Aspetto vostre opinioni!

P.S. La lista completa degli esami è qui
https://didattica.polito.it/pls/portal3 ... oorte=2020

[Flamber]

Grazie per la risposta.

Per quanto riguarda la prima scelta è un pò quello che avevo pensato anche io, tuttavia diciamo che con Statistica andrei un pò a ripetere argomenti che ho già visto abbastanza approfonditamente in triennale. Però penso che alla fine sceglierò quello perchè c'è un esame obbligatorio di "Mathematics for machine learning" dove alcuni argomenti avanzati di algebra lineare vengono trattati abbastanza dettagliatamente.

Peril consiglio finale, invece, purtroppo non posso seguire il tuo consiglio dato che è un corso di laurea magistrale inaugurato quest'anno e non c'è m,olto materiale in giro. Quello che posso dire è che ho visto il materiale di Informatio Theory e sembra fatto davvero bene, e i libri consigliati sembrano interessanti.

P.S. Sono comunque degli esami a scelta, e quindi non trattano gli argomenti al massimo livello di profondità, ma penso abbiano lo scopo di fornire alcuni strumenti utili per i corsi del secondo anno

[Intermat]

Secondo me i primi due sono molto interessanti entrambi (probabilmente sarebbe utile farli tutti e due perché affrontano questioni diverse ma comunque interessanti in ambito data science), se dovessi consigliarti in base a una possibile futura utilità lavorativa direi il 2.

Tra gli altri tre invece io ti suggerirei il primo, forse però qui sono di parte perché (alcune) sono cose di cui mi occupo nel mio dottorato. Detto questo anche il 3° è interessante. Diciamo che il problema del 1° sta nel fatto che mi risulta complicato immaginare un corso ben fatto che affronta così tanti problemi tutti insieme, io quegli argomenti li avrò visti in 3/4 corsi per un totale di almeno 24 cfu. L'ultimo mi sembra più credibile farlo in un numero limitato di ore. Diciamo che entrambi sono molto teorici e poco applicativi dal punto di vista di un futuro lavoro. Il 2° mi sembra abbia un taglio completamente diverso.

Il suggerimento che mi sentirei di darti è il seguente: parla con qualche collega affidabile che ha già studiato in uno di questi corsi e capisci come è il docente. Tutti e quattro i corsi che ti ho detto ti potranno essere utili ma lo saranno tanto più il professore sarà bravo ad affrontarli e a farteli capire. Quando ero alla magistrale dovevo scegliere un corso a scelta e ne volevo fare uno di machine learning, parlando con un bel po' di colleghi e guardando il sito web del professore ho capito che il corso sarebbe stato un disastro sia dal punto di vista dei contenuti che avrei appreso sia dal punto di vista della valutazione finale. In conclusione: ho scelto altro. Vedi bene i materiali forniti e fatti un'idea sul docente, detto questo scegli in serenità perché sono tutti corsi interessanti.

Buono studio!